Automatas Finitos Deterministicos

Consideramos el lenguaje regular A representado por c* (a U bc*). Si dada una cadena w se nos pregunta si w pertenece a A, debemos analizar no solo los caracteres que aparecen en w, sino también sus posiciones relativas. Por ejemplo, la cadena abc⁵ c³ ab está en A, sin embargo cabac³ bc no lo está. Podemos construir un diagrama que nos ayude a determinar los distintos miembros del lenguaje.

Tal diagrama tiene la forma de un grafo dirigido con información adicional añadida, y se llama diagrama de transición. Los nodos del grafo se llaman estados  y se usan señalar, en ese momento, hasta que lugar se ha analizado la cadena. Las aristas del grafo se etiquetan con caracteres del alfabeto y se llaman transiciones.

Si el siguiente carácter a reconocer concuerda con la etiqueta de alguna transición, que parta del estado actual, nos desplazamos al estado al que nos lleve la arista correspondiente. Naturalmente, nosotros debemos comenzar por un estado inicial, y cuando se hayan tratado todos los caracteres de la cadena correspondiente, necesitamos saber si la cadena es “legal”. Para ello se marcan ciertos estados como estados de aceptación o estados finales. Si cuando ha sido tratada la cadena en su totalidad, terminamos en un estado inicial con una flecha ( ===>) y alrededor de los estado de aceptación trazaremos un circulo.

Por ejemplo, el siguiente diagrama acepta todas las cadenas que están formadas por 0 ó más aes seguidas por una única b. Para toda cadena de la forma a^k  b, para  K > 0, el recorrido del diagrama termina en un estado de aceptación. El recorrido del mismo con cualquier otra cadena de aes y bes (incluida la cadena vacia) termina en cualquier otro estado, pero este no es de aceptación.

Considérese el lenguaje A  =  {  (ab)  i  >  1 }, el cual está representado por la expresión regular (ab)+. Obsérvese que una cadena de este lenguaje ha de tener al menos una copia de ab. Por tanto, si se construye un diagrama de transición para este lenguaje, el estado inicial no puede ser también estado de aceptación.

Es más, si estando en el estado inicial se encuentra el carácter b, esto indica que la cadena  no puede ser aceptada, Por tanto, hay dos transiciones a partir del estado inicial, una para a y otra para b.

La transición correspondiente a, nos lleva a un estado en el que se espera encontrar como siguiente carácter de la cadena, una b. Si no hay más caracteres a considerar, se habrá identificado una cadena legal. Si se obtiene b, entonces nos desplazaremos a un estado de aceptación. Luego, si no hay más caracteres a considerar, se habrá identificado una cadena legal. Si no se han agotado los caracteres de la cadena, tomaremos la transición apropiada que parta de dicho estado. El diagrama de transición para A  es el que se muestre en la siguiente figura.

Tiene un único estado de aceptación. Si el análisis termina en cualquier otro estado, la cadena no está correctamente construida. Una vez que se identifica un prefijo incorrecto, se realiza un desplazamiento a un estado que no es de aceptación y se pertenece en el mismo.

Consideramos el lenguaje (ab)*. En este caso si se acepta la cadena vacía. Por tanto, el estado inicial también es de aceptación. El diagrama de transición correspondiente se muestra en la siguiente figura.                                      

Vamos a etiquetar los estados del último diagrama de transición con las letras q1 para i = 0,1,2 obtendremos lo siguiente

Podemos representar el diagrama de la figura anterior por medio de una tabla que indica el siguiente estado al que debe desplazarse, desde un estado combinado con un símbolo de la entrada.

La tabla para el diagrama de transición tiene, para cada par estado actual-entrada, un único estado siguiente. Por tanto, para cada estado actual y símbolo de entrada, se puede determinar cual será el estado siguiente. Se puede pensar que el diagrama representa la acción de alguna máquina. Esta máquina puede pasar por diferentes estados. El cambio de estado depende de la máquina y del estado en que se encuentre. Dicha máquina se llama autómata finito, una computadora ideal. El autómata finito se define en términos de sus estados, la entrada que acepta y su reacción ante la misma. Hay autómatas finitos de dos tipos, deterministas y no deterministas, dependiendo de cómo se defina la capacidad para cambiar de estado. El autómata que corresponde ala tabla anterior para (ab)* es determinista.

Formalmente, un autómata finito determinista M es una colección de cinco elementos.

1.- Un alfabeto de entrada E.

2.- Una colección finita de estados Q.

3.- Un estado inicial s.

4.- Una colección F de estados finales o de aceptación.

5.- Una función 8 : Q X E ==>Q  que determina el único estado siguiente para el par (qi, t) correspondiente al estado actual y la entrada.

Generalmente el término autómata finito determinista se abrevia como AFD.

M = ( Q, E, s, F, 8 ) indicará el conjunto de estados, el alfabeto, el estado inicial, el conjunto de estados finales y la función asociada con el AFD M.

Por ejemplo, el AFD correspondiente al ejemplo anterior se representa mediante M = ( Q, E, s, F, 8 ), donde:

Q = { q0, q1, q2 }

E = { a, b }

s = q0

F= { q0 }

8 Se define mediante la tabla siguiente:

La característica principal de un AFD es que 8 es una función. Por tanto, 8 se debe definir para todos los pares ( q1, t ) de Q X E. Esto significa que sea cual sea el estado actual y el carácter de entrada, siempre hay un estado siguiente y éste es el único. Por tanto, para un par ( q1, t ) hay  uno y sólo un valor de la función (estado siguiente), 8  ( q1, t ). En otras palabras, el estado siguiente está totalmente determinado por la información que proporciona el par ( q1, t ).

Se puede crear un diagrama de transición a partir de la definición de un AFD. Primero, creamos y etiquetamos un nodo para cada estado. Entonces, para cada celda q1 de la fila correspondiente al estado qi, trazamos una arista desde qi a qj, etiquetada con el carácter de entrada asociado a qj. Finalmente, se marca el nodo s con una flecha, y se trazan unos círculos en todos los nodos de F para indicar cuales son los estados de aceptación. Por tanto, el diagrama de transición para el AFD  M = ( Q, E, s, F, 8 ), donde:

Q = { q0, q1 }

E = { a, b }

s = q0

F= { q0 }

Y 8 representada mediante la tabla siguiente.

AFD y Lenguaje

Para trabajar con los AFD es necesario usar ciertas definiciones y notaciones. Si M es un AFD, entonces el lenguaje aceptado por M es

L(M) = { w E | w es aceptada por M}

Por tato, L(M) es el conjunto de cadenas que hacen que M pase de su estado inicial a un estado de aceptación.

Por ejemplo, el lenguaje aceptado por el AFD(*), presentado en la última sección, es

L(M) = { w E {a,b} * |w no contiene tres bes consecutivas }

L(M) está formado por todas las cadenas aceptadas por M, y no que es un conjunto de cadenas que son todas aceptadas por M.

Para cada (q1, t) de Q X E, 8 (q1, t) es un estado perteneciente a Q, y él mismo puede ser emparejado con la entrada. Este par se transforma mediante un nuevo estado de Q. En particular, si q es el estado inicial de M y se tiene como entrada la cadena  t1, t2, t3, el estado resultante se obtiene mediante la aplicación de &(&(&(q0, t1),t2),t3). Por ejemplo, para el AFD (*) de la última sección , se tiene &(&(&(&(q0, b),b),a), b) = q1 para la cadena bbab. Observece la aplicaciòn recursiva de M sobre la cadena. Adviértase, también, que escribir esta expresión es un proceso bastabte laborioso.

Usaremos el signo &(q0, bbab) para abreviar &(&(&(&(q0, b),b),a), b). Para ser màs precisos, si qi E Q y w es una cadena de la forma aiw’ para algún ai E E y una subcadena w’, definiremos & (q1, w) como &(&(q1, ai),w`).

Dos AFD M1 y M” son equivalentes si L(M1) = L(M2). Por ejemplo, sean M! Y M2 sobre el alfabeto E = {a}, representados por los siguientes diagramas de transiciones

Ambos aceptan el lenguaje a+ y,  por tantpo, son equivalentes. Por otro lado, sea M3 dodo por el siguiente diagrama:

No es equivalente a M1 o M2. M4 dado por el siguiente diagrama de transición

Es equivalente a M3 y es más “sencillo” puesto que tiene menos estados.