Lenguajes Regulares
Autómatas Finitos
Un autómata finito es una máquina capaz de reconocer palabras creadas con una gramática regular. Según sea su función de transición podemos distinguir dos tipos de autómatas: Deterministas y no deterministas.
En los autómatas deterministas sólo hay un posible estado dada una entrada y estando en un determinado estado.
Autómata finito determinista: está formado por una quíntupla (Σ, Q, f, q0, F), donde:
- Σ es un alfabeto de entrada.
- Q es un alfabeto de estados.
- f es la funcion de transicion: f: Q x Σ -> Q
- q0 es el estado inicial.
- F ⊂ Q es el conjunto de estados finales o estados de aceptación
Autómata finito no determinista: está formado por una quíntupla (Σ, Q, f, q0, F), donde:
- Σ es un alfabeto de entrada.
- Q es un alfabeto de estados.
- f es la funcion de transicion: f: Q x (Σ -> Ε) -> P(Q)
- q0 es el estado inicial.
- F -> Q es el conjunto de estados finales o estados de aceptación
La parte fundamental de un autómata finito es su función de transición por eso es frecuente representarlo mediante una tabla donde se uestra o mediante un grafo dirigido.
| |
a |
b |
| -> q0 |
q1 |
q3 |
| (q1) |
q2 |
q1 |
| q2 |
q1 |
q3 |
| (q3) |
q3 |
q3 |
Extensión de f a palabras: la función de transición f toma como argumento un estado y un símbolo (carácter), pero se puede definir una función que tome un estado y una palabra:
f ' : Q x Σ -> Q
f '(q, e) = f(q, e)
Teniendo en cuenta e->Σ x->Σ*
f '(q, ex) = f '(f(q,e), x)
La función f'(q, w) da el estado al que se puede llegar partiendo de q y siguiendo las transiciones según w.
El lenguaje reconocido por un autómata M = (Σ, Q, f, q0, F) se define como:
AFD: L(M) = {w -> Σ* : f '(q0, w) -> F}
AFND: L(M) = {w -> Σ : f '(q0, w) -> F ≠ Ø}
Paso de un AFND a un AFD
Para cada Autómata finito no determinista existe un Autómata finito determinista equivalente y viceversa. Por ello existe un método para pasar construir un AFD a partir de un AFND.
El algoritmo es el de construcción de subconjuntos y para entenderle vamos a explicar el concepto de cerradura épsilon:
cerr-Ε(q) = {f ' (q, Ε)} -> {q}. Es decir el conjunto de stados alos que puedo llegar a partir del estado q mediante transiciones Ε; es decir, sin consumir entrada.
D -> cerr-Ε(q0);
while haya un estado T sin marcar en D do {
marcar T;
for cada simbolo de entrada a -> Σ do{
U -> cerr-Ε(mueve(T, a));
if U -> D then añadir U sin marcar a D
tranD[T, a] -> U;
}
}
Tras haber aplicado el algoritmo de construcción de subconjuntos al autómata AFND( Σ,Q, f, q0, F ) el autómata determinista resultante es AFD ( Σ, D, tranD, cerr-Ε(q0), F ) F={U -> D: U -> F ≠ Ø}
Aplicando conocimientos
Ahora puedes comprobar cómo funciona el método de construcción de subconjuntos y utilizarle para eliminar el no determinismo de un autómata finito.
En el siguiente applet se pueden introducir autómatas finitos y convertirles a deterministas mediante el método visto anteriormente.
En el panel se muestra los estados del antiguo autómata que engloba cada nuevo estado. Va construyendo paso a paso la función de transición del nuevo autómata.
En el applet aparece un autómata de ejemplo pero puede ser modificado y/o rediseñado totalmente y después eliminar el no determinismo.
Teoremas de análisis y síntesis
Teorema de síntesis: Todo conjunto regular es un lenguaje aceptado por un reconocedor finito. El paso de una expresión regular a un autómata finito se puede hacer por diversos procedimientos:
- Método de Thompson
- Método de Aho Sethi Ullman
- Método de las derivadas
Teorema de análisis: Todo lenguaje aceptado por un reconocedor finito es un conjunto regular. El paso de autómata finito a expresión regular se puede hacer por diversos procedimientos:
- Método 1
- Método de las ecuaciones características