EJEMPLO DE UN AFD
La construcción de AFD’s es esencial para entender el comportamiento de las expresiones regulares. Dado un alfabeto y una serie de condiciones, se puede elaborar un AFD que satisfaga dichas condiciones, mediante ensayo y error.
Ejemplo:
Dado el alfabeto en {0,1}, elaborar un AFD que acepte solamente palabras
a) con un número par de ceros
A continuación se realiza el automata resultante para este enunciado:
A diferencia de los AFD, los AFN permiten que salga un número de ligas arbitrario de cada estado. Los Autómatas Finitos No Deterministas (AFN) varían un poco con respecto a los AFDs, ya que las transiciones que salen de un estado pueden ser muchas porque una palabra del alfabeto puede repetirse. Por tal motivo, las operaciones que se realizan son más flexibles y por tanto el análisis varía un poco.
La relación de transición es la parte variable de la definición formal de un AFN, ya que en los AFD, se maneja una función. La flexibilidad permitida a las transiciones hace más poderosos a estos autómatas, pero también más peligrosos en cuanto al control del reconocimiento de un lenguaje.
Definición 1.- Un AFN es un quíntuplo (K, S, D,s, F ) donde K, S, s, F tienen el mismo significado que para el caso de los AFD, y D, llamada la relación de transición, es un subconjunto finito de k xS*x k.
Definición 2.- Una palabra w es aceptada por AFN si existe una trayectoria en su diagrama de estados, que parte del estado inicial y llega a un estado final, tal que la concatenación de las etiquetas de las flechas es igual a w.
Definición 3.- La cerradura al vacío de cerr-e(q) de un estado q es el conjunto más pequeño que contiene
al estado q,
a todo estado r ' $ una transición (p,e,r) Î D, con cerr-e(q).
Ejemplo de un AFN
Se muestra en la siguiente gráfica el comportamiento de las transiciones de los AFN’s. Observamos que podría darse el caso en que no salgan transiciones de un estado,
también que salga una transición vacía. Esto nos indica la gran flexibilidad de los AFN’s con respecto a los AFD’; sin embargo, hay ventajas y desventajas para cada uno.
La transición en los Autómatas Finitos es de cuidado, ya que debemos distinguir las características de cada Autómata, así como del alfabeto. En un AF se definen dos conceptos, la transición e en un AFD que significa estar en un estado sin transición, pero en un AFN se define con la cerradura al vacío.
Teorema. Sea M=(K, S, D,s, F ) un AFN. Entonces existe un AFD M’= (K’, S‘, d,s’, F’ ) que es equivalente a M.
Teorema. Si L es aceptado por un AFN con transiciones e, entonces L es aceptado por un AFN sin transiciones e.
Se dice que dos autómatas son equivalentes si aceptan el mismo lenguaje. Un AFD es un AFN, pero no viceversa. Sin embargo, existe un procedimiento para convertir un AFN en un AFD.
Un AFD define un único lenguaje, pero lo inverso no es verdadero. Se puede reducir el número de estados en un AF.
Las ER pueden ser usadas para describir algunos lenguajes. Si r es una ER, L( r ) denota el lenguaje asociado con r. Este lenguaje se define como sigue:
Æ es una ER que denota el conjunto vacío
e es una ER que denota {e}
para cada a Î S, a es una ER que denota {a}
si r1 y r2 son ER, entonces
L(r1 + r2) = L(r1) + L(r2)
L(r1 r2) = L(r1) L(r2)
L(r1*) = (L(r1) )*
Un AFD es un AFN debido a que cumple las características de sus parámetros, sin embargo cuando queremos transformar un AFN en un AFD, debemos cuidar las transiciones. Es válida la transformación y siempre se puede realizar. El número de estados obtenidos es igual a la cardinalidad del conjunto potencia de los estados del AFN.