Automatas, Gramaticas y Lenguajes

UNIDAD V. AUTÓMATAS, GRAMÁTICAS Y LENGUAJES.


5.1 EXPRESIONES REGULARES Y LENGUAJES REGULARES

Un lenguaje formal es un lenguaje cuyos símbolos primitivos y reglas para unir esos símbolos están formalmente especificados. Al conjunto de los símbolos primitivos se le llama alfabeto del lenguaje.

A una cadena de símbolos formada de acuerdo a la gramática se le llama una fórmula dellenguaje. Un lenguaje formal es idéntico al conjunto de todas sus fórmulas bien formadas.

Entonces, algunas fórmulas bien formadas del lenguaje serían: ab, ba, abab, ababba, etc.; y el lenguaje formal sería el conjunto de todas esas fórmulas bien formadas.


LENGUAJE REGULAR

Un lenguaje regular es un tipo de lenguaje formal que satisface las siguientes propiedades:

Los lenguajes mássencillos que se considerarán son los lenguajes regulares, es decir, los que se pueden generar a partir de lenguajes básicos, con la aplicación de las operaciones de unión, concatenación y * de Kleene un número finito de veces.
Con el alfabeto ∑ es posible formar una gran cantidad de lenguajes, pero no existe un método efectivo para saber cuántos de ellos son regulares. Todos los lenguajes sobre ∑ sonsublenguajes del lenguaje universo ∑*, en lugar de ello se utilizaran propiedades de los lenguajes para determinar cuáles de ellos son regulares.
El conjunto de lenguajes regulares de ∑ son:
El lenguaje vacíoΦ
El lenguaje que contiene la cadena vacía como único elemento {ε}.
El lenguaje unitario {a} es regular

Si L y M son lenguajes regulares, entonces también los lenguajes que resultan dela unión (L U M), la concatenación (LM), la potenciación (Ln Mn) y la cerradura de Kleene (l*).

Ningún otro lenguaje sobre ∑ es regular.

Se puede concluir que a partir del alfabeto ∑ los lenguajes obtenidos con las operaciones unión, concatenación, potenciación y cerradura de Kleene son lenguajes regulares, además de los lenguajes de un solo elemento, incluyendo la cadena vacía y ellenguaje vacío.



EXPRESIONES REGULARES

Las expresiones regulares representan lenguajes regulares y su propósito es simplificar la escritura de los lenguajes regulares.

Es una nueva forma de expresar los lenguajes regulares y tiene como finalidad facilitar la manipulación y simplificación de los mismos. La equivalencia entre lenguajes regulares y expresiones regulares es como se indica en lasiguiente tabla:


Lenguaje regular
Expresión regular
{a}
a
{ε}
ε
Φ*
ε
{a}+
a+
{a}*
a*
{ab}
ab
{a} U {b} = {a,b}
a U b


Los lenguajes regulares se derivan de los lenguajes formales (símbolos primitivos que son llamados alfabetos), pero a diferencia de los lenguajes formales, los lenguajes regulares deben cumplir con ciertas características como: el lenguaje vacío Φ, ellenguaje que contiene la cadena vacía como único elemento {ε}, etc. Y a su vez presentan propiedades como la unión, concatenación y potenciación.

Las expresiones regulares son derivadas de los lenguajes regulares y su propósito es simplificar la escritura de los lenguajes regulares para así poder manipularlas de manera más sencilla.



5.2 AUTÓMATA FINITO DETERMINISTA AFD

Un autómata finito(AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida.

Los autómatas finitos (AF) son de dos tipos:

Deterministas (AFD)
No Deterministas (AFND)


5.2.1. DEFINICIONES Y REPRESENTACIONES.

AUTOMATAS FINITOS DETERMINISTAS (AFD)

Un autómata finito determinista (abreviado AFD) es un autómata finito queademás es un sistema determinista; es decir, para cada estado en que se encuentre el autómata y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con ese símbolo. Cada combinación (estado, símbolo de entrada) produce un solo estado (estado).


REPRESENTACION DE UN AFD

Un autómata finito determinista se puede representar mediante:...