AUTÓMATAS FINITOS

Un reconocedor de un lenguaje es un programa que toma como entrada una cadena “x y”,
responde "si" si x es una frase del programa, y "no", si no lo es. Se compila una expresión regular
en un reconocedor construyendo un diagrama de transiciones generalizado llamado autómata
finito.

Un autómata finito puede ser determinista o no determinista, donde "no determinista" significa
que en un estado se puede dar el caso de tener más de una transición para el mismo símbolo de
entrada.

Autómatas finitos no deterministas (AFN)

Un autómata finito no determinista es un modelo formado por:

1. Un conjunto de estados denotados como: estados S.

2. Un conjunto de símbolos de entrada S (el alfabeto símbolos de entrada).

3. Una función de transición mover que transforma pares estado-símbolo en conjuntos de

estados.

4. Un estado S0 que se considera el estado de inicio (o inicial).

5. Un conjunto de estados F considerados como estados de aceptación (o finales).

Un AFN se puede representar mediante un grafo dirigido etiquetado, llamado grafo de

transiciones, en el que los nodos son los estados y las aristas etiquetadas representan las
funciones de transición. Este grafo se parece a un diagrama de transiciones, pero el mismo
carácter puede etiquetar dos o más transiciones fuera de un estado, y las aristas pueden
etiquetarse con el símbolo especial V´ o V´y con símbolos de entrada.

En la Figura, se muestra el grafo de transiciones de un AFN que reconoce al lenguaje (a|b)*abb.

. .

El conjunto de estados del AFN es {0,1,2,3} y el alfabeto de símbolos de entrada es {a, b}. El
estado 0 de la figura 1 se considera el estado de inicio, y el estado de aceptación 3 está indicado
mediante un círculo doble.

Cuando se describe un AFN, se utiliza la representación de grafo de transiciones. En un

computador, puede aplicarse la función de transición de un AFN de varias formas. La
implantación más sencilla es una tabla de transiciones en donde hay una fila por cada estado y
una columna por cada símbolo de entrada V´, si es necesario.
Autómatas finitos deterministas (AFD)

Un autómata finito determinista es un caso especial de un autómata finito no determinista en

el cual:

1. Ningún estado tiene una transición V´, es decir, una transición con la entrada V´, y

2. Para cada estado s y cada símbolo de entrada a, hay exactamente una arista etiquetada a que
sale de s.

Un autómata finito determinista tiene una transición desde cada estado con cualquier entrada.
Si se está usando una tabla de transiciones para representar la función de transición de un AFD,
entonces cada entrada en la tabla de transiciones es un solo estado. Como consecuencia es muy
fácil determinar si un autómata finito determinista acepta o no una cadena de entrada, puesto
que hay a lo sumo un camino desde el estado de inicio etiquetado con esa cadena.

Ejemplo de AFD
 Transformación de un AFN en un AFD
En un autómata determinista, AFD, las transiciones tienen la siguiente estructura:

Desde el estado j , leyendo el símbolo a, se debe transitar al estado k.

Un autómata no determinista, AFN, se caracteriza por transitar a más de un estado; es

decir, la acción básica podría ser como esta:

Desde el estado j, leyendo el símbolo a, se puede transitar al estado k o al estado

p.

Los AFN son útiles como herramienta teórica: facilitan el diseño y suelen ser más
“económicos” (menor número de estados, menor número de transiciones) que los AFD.

Pero, por desgracia, son herramientas teóricas: el mundo real es determinista... por lo
tanto, para poder “verlos en funcionamiento” o bien se recurre a la simulación o bien se
deben transformar previamente a AFD.

Para transformar un AFN en un AFD se sigue el siguiente método:

1. Se construye una tabla donde cada columna esta etiquetada con un símbolo del
alfabeto de entrada y cada fila se etiqueta con un conjunto de estados.

2. La primera fila se etiqueta con {q0}, estado inicial, y en cada entrada de la tabla
[q0, si ] se almacena f(q0, si) = {p1, . . . , pn} = P.

3. Se etiqueta cada fila con cada uno de los conjuntos P que no tengan asociada
una fila en la tabla (es decir, con cada uno de los conjuntos P que aparezcan por
primera vez en la tabla) y se completa cada una de estas filas con el
correspondiente f(P, si).

4. Se realiza el paso (3) hasta que no haya en la tabla conjuntos P sin filas asociadas.

5. Se asocia a cada conjunto P que aparezca en la tabla un estado en el nuevo AFD

y aquellos que tengan entre sus componentes algún estado final del AFN se
considerarán estados finales en el AFD.
Ejemplo 1.
Calcular el AFD asociado al AFN definido por la siguiente función de transición:

f 0 1
q0 { q1 , q2 } { q3 }
q1 { q1 , q4 } --
q2 { q3 } --
q3 -- { q1 , q2 , q4 }
q4 { q3 } { q4 }

Estado inicial: I ={ q0 } , Estado final: F = { q4 }

Comenzamos a aplicar el método a partir de {q0} con cada uno, de acuerdo a la tabla original:

f 0 1
q0 { q1 , q2 } { q3 }
... … …

La imagen de {q0} con el símbolo 0 es el conjunto de estados {q1, q2} ( f(q0, 0) = {q1, q2}) y su
imagen con el símbolo 1 es el conjunto de estados {q3}. Como el conjunto {q1, q2} no tiene
asociada ninguna fila en la tabla, se etiqueta una fila con el:

f 0 1
q0 { q1 , q2 } { q3 }
q1 , q2

Para calcular la imagen de {q1, q2} con el símbolo 0, se debe calcular f(q1, 0) ∪ f(q2, 0). Si lo
consultamos en la tabla de transición del AFN o en el grafo, se obtiene que es

{q1, q4} ∪ {q3} = {q1, q4, q3}. Este resultado se escribe en la tabla en la entrada [{q1, q2}, 0].
De forma similar se calcula la imagen de {q1, q2} con el símbolo 1:

f(q1, 1) ∪ f(q2, 1) = ∅ U ∅ = ∅.

f 0 1
q0 { q1 , q2 } { q3 }
q1 , q2 { q1,q4,q3} --
… … …

Una vez completada la fila etiquetada como {q1, q2} se observa que aparece un conjunto de
estados nuevos; por lo tanto, se procede a crear una fila más en la tabla, etiquetada con el nuevo
conjunto de estados:

f 0 1
q0 { q1 , q2 } { q3 }
q1 , q2 { q1,q3,q4} --
q1,q3,q4
… … …

Se calcula la fila etiquetada como {q1, q3, q4}:

f({q1, q3, q4}, 0) = f(q1, 0) ∪ f(q3, 0) ∪ f(q4, 0) = {q1, q4} ∪ ∅ ∪{q3} = {q1, q3, q4}.

f({q1, q3, q4}, 1) = f(q1, 1) ∪ f(q3, 1) ∪ f(q4, 1) = ∅ ∪ {q1, q2,q4} ∪ {q4} = {q1,q2,q4}.

f 0 1
q0 { q1 , q2 } { q3 }
q1 , q2 { q1,q3,q4} --
q1,q3,q4 { q1,q3,q4} { q1,q2,q4}
… … …

Como se puede ver, al rellenar esta fila con respecto a 0 no ha aparecido ningún nuevo conjunto
de estados; pero sí con respecto a 1 por eso le coloca una nueva fila con dichos estados:

f 0 1
q0 { q1 , q2 } { q3 }
q1 , q2 { q1,q3,q4} --
q1,q3,q4 { q1,q3,q4} { q1,q2,q4}
q1,q2,q4
… … …

Se calcula la fila etiquetada como {q1, q2, q4}:

f({q1, q2, q4}, 0) = f(q1, 0) ∪ f(q, 0) ∪ f(q4, 0) = {q1, q4} ∪ {q3} ∪{q3} = {q1, q3, q4}.

f({q1, q2, q4}, 1) = f(q1, 1) ∪ f(q2, 1) ∪ f(q4, 1) = ∅ ∪ ∅ ∪ {q4} = {q4}.

 f 0 1
q0 { q1 , q2 } { q3 }
q1 , q2 { q1,q3,q4} --
q1,q3,q4 { q1,q3,q4} { q1,q2,q4}
q1,q2,q4 { q1,q3,q4} {q4}
… … …

Ahora no han aparecido nuevos conjuntos de estados, por lo que ya se ha finalizado: el AFD
equivalente al AFN descrito y en la tabla original tiene como función de transición:

f 0 1
q0 { q1 , q2 } { q3 }
q1 , q2 { q1,q3,q4} --
{ q1 , q2 ,
q3 --
q4 }
q1,q3,q4 { q1,q3,q4} { q1,q2,q4}
q1,q2,q4 { q1,q3,q4} {q4}
q4 { q3 } { q4 }

Los estados finales son los estados en donde aparece el estado final original q4.

I f 0 1
q0 { q1 , q2 } { q3 }
q1 , q2 { q1,q3,q4} --
q3 -- {q1,q2,q4}
F q1,q3,q4 { q1,q3,q4} { q1,q2,q4}
F q1,q2,q4 { q1,q3,q4} {q4}
F q4 { q3 } { q4 }

El conjunto {q0} se renombra como q’0 , el {q0, q1} como q’1 , el {q1, q3, q4} como q’2, el estado
{q3 } se renombra como q’3 , el {q1, q3, q4} como q’5, el {q1, q2, q4} como q’6 y q4 se renombra
como q’4 . Como los conjuntos {q1, q2, q4}, {q4} y {q1, q3, q4} contienen estados finales del AFN
original, entonces los estados q’4, q´5 y q’6 serán estados finales en el AFD.

I f 0 1 I f 0 1
q0 { q1, q2 } { q3 } q'0 q'1 q'3
q1 , q2 { q1,q3,q4} -- q'1 q'5 --
q3 -- {q1,q2,q4} q'3 -- q'6
F q4 { q3 } { q4 } F q'4 q'3 q'4
F q1,q3,q4 { q1,q3,q4} { q1,q2,q4} F q'5 q'5 q'6
F q1,q2,q4 { q1,q3,q4} {q4} F q'6 q'5 q'4
 Grafo obtenido

Ejemplo 2.
Transforma el siguiente AFN a un AFD.

La función de transición de este AFN es la siguiente:

f 0 1
q0 { q0 , q1 } { q0 }
q1 { q2 } { q0 , q2 }
q2 -- --

Estado Inicial: I = { q0 } , Estado final: F = { q2 }

Comenzamos a aplicar el método a partir de la imagen de {q0} con cada uno de los símbolos del
alfabeto, de acuerdo a la tabla original:

f 0 1
q0 { q0 , q1 } { q0 }
… … …
La imagen de {q0} con el símbolo 0 es el conjunto de estados {q0, q1} (f(q0, 0) = {q0, q1}) y su
imagen con el símbolo 1 es el conjunto de estados {q0}. Como el conjunto {q0, q1} no tiene
asociada ninguna fila en la tabla, se etiqueta una fila con el.
Para calcular la imagen de {q0, q1} con el símbolo 0, se debe calcular f(q0, 0) ∪ f(q1, 0). Si lo
consultamos en la tabla de transición del AFN o en el grafo, se obtiene que es {q0, q1}∪ {q2} =
{q0, q1, q2}. Este resultado se escribe en la tabla en la entrada [{q0, q1}, 0]:

f 0 1
q0 { q0 , q1 } { q0 }
q0 , q1 { q0, q1 , q2} --
… … …
De forma similar se calcula la imagen de {q0, q1} con el símbolo 1: f(q0, 1) ∪ f(q1, 1) = {q0} ∪
{q0, q2} = {q0, q2}.

f 0 1
q0 { q0 , q1 } { q0 }
q0 , q1 { q0, q1 , q2} { q0 , q2 }
… … …
Una vez completada la fila etiquetada como {q0, q1} se observa que aparecen dos conjuntos
de estados nuevos; por lo tanto, se procede a crear dos nuevas filas en la tabla, cada una
etiquetada con cada uno de los nuevos conjuntos:

f 0 1
q0 { q0 , q1 } { q0 }
q0 , q1 { q0, q1 , q2} { q0 , q2 }
q0 , q1 , q2
q0 , q2
… … …

Se calcula la fila etiquetada como {q0, q1, q2}:

f({q0, q1, q2}, 0) = f(q0, 0) ∪ f(q1, 0) ∪ f(q2, 0) = {q0, q1} ∪ {q2} ∪ ∅ = {q0, q1, q2}.

f({q0, q1, q2}, 1) = f(q0, 1) ∪ f(q1, 1) ∪ f(q2, 1) = {q0} ∪ {q0, q2} ∪ ∅ = {q0, q2}.

f 0 1
q0 { q0 , q1 } { q0 }
q0 , q1 { q0, q1 , q2} { q0 , q2 }
q0 , q1 , q2 { q0, q1 , q2} { q0 , q2 }
q0 , q2
… … …

Como se puede ver, al rellenar esta fila no ha aparecido ningún nuevo conjunto de estados;
por lo tanto, pasamos a completar la fila etiquetada con {q0, q2}.

f({q0, q2}, 0) = f(q0, 0) ∪ f(q2, 0) = {q0, q1} ∪ ∅ = {q0, q1}.

f({q0, q2}, 1) = f(q0, 1) ∪ f(q2, 1) = {q0} ∪ ∅ = {q0}.

f 0 1
q0 { q0 , q1 } { q0 }
q0 , q1 { q0, q1 , q2} { q0 , q2 }
q0 , q1 , q2 { q0, q1 , q2} { q0 , q2 }
q0 , q2 { q0 , q1 } { q0 }
… … …
Tampoco ahora han aparecido nuevos conjuntos de estados, por lo que ya se ha finalizado: el
AFD equivalente al AFN descrito en el ejercicio tiene como función de transición la descrita en:

f 0 1
q0 { q0 , q1 } { q0 }
q0 , q1 { q0, q1 , q2} { q0 , q2 }
q0 , q1 , q2 { q0, q1 , q2} { q0 , q2 }
q0 , q2 { q0 , q1 } { q0 }

Los estados finales son los estados en donde aparece el estado final original q2.

f 0 1
I q0 { q0 , q1 } { q0 }
q0 , q1 { q0, q1 , q2} { q0 , q2 }
F q0 , q1 , q2 { q0, q1 , q2} { q0 , q2 }
F q0 , q2 { q0 , q1 } { q0 }

El conjunto {q0} se renombra como q’0 , el {q0, q1} como q’1 , el {q0, q1, q2} como q’2 y el
estado {q0, q2} se renombra como q’3 .

Como los conjuntos {q0, q1, q2} y {q0, q2} contienen estados finales del AFN original, entonces
los estados q’2 y q’3 serán estados finales en el AFD.

f 0 1
I q'0 q'1 q0
q'1 q'2 q'3
F q'2 q'2 q'3
F q'3 q'1 q'0

Grafo obtenido