3. Autómatas de Estados Finitos

Aplicación de los autómatas en los procesadores de lenguaje

La tarea de comprobar si una sentencia pertenece o no a un determinado lenguaje se encomienda a los autómatas. En el campo de estudio de los traductores, compiladores, procesadores e intérpretes los autómatas se utilizan como reconocedores de lenguajes, que dada una cadena de símbolos indican si dicha cadena pertenece o no al lenguaje.

Una cadena pertenece a un lenguaje si el autómata reconocedor de dicho lenguaje lo toma como entrada, y partiendo del estado inicial  transita a través de varias configuraciones hasta que alcanza el estado final.

Autómatas finitos

Un autómata finito es un conjunto de nodos y aristas que representan trayectorias para generar una expresión bajo un alfabeto. Un diagrama de transición es un autómata finito.

Existen dos tipos autómatas finitos, los cuales son:

• Autómatas finitos deterministas (AFD)
• Autómatas finitos no deterministas (AFND) 

Autómatas finitos deterministas (AFD) 

Definición. Una máquina de estados finitos M es un quíntuplo (K, Σ, δ, s, F), donde:


K es conjuntos de estados. 
Σ es el alfabeto de entrada. 
δ : K X Σ → K, es la función de transición, que a partir de un estado y un símbolo del alfabeto obtiene un nuevo estado.  
s ∈ K es el estado inicial. F ⊆ K es un conjunto de estados finales.  
δ : K X Σ → K, es la función de transición, que a partir de un estado y un símbolo del alfabeto obtiene un nuevo estado.


Ejemplo: 

Este autómata finito determinista puede ser expresado formalmente como: 

M = (K, Σ, δ, q0, F) 

K = {q0, q1, q2}

Σ = {a, b} 

δ = {((q0, a), q1), ((q0, b), q2), ((q1, a), q1), ((q1,

b), q1), ((q2, a), q0), ((q2, b), q2)}

F = { q1, q2 } 

IMPORTANTE: Para que un AFD sea válido, el número de transiciones que salen de cada estado debe ser igual a la cantidad de caracteres del alfabeto, puesto que δ es una función que está definida para todas las entradas posibles. 

• Para el AFD anterior, el alfabeto es {a, b} de cada estado deben salir exactamente dos transiciones, una con a y otra con b. 
• Otra condición es que debe tener exactamente un estado inicial. En cambio, la cantidad de estados finales puede ser cualquiera, inclusive cero, hasta un máximo de |K| (la cantidad de estados).

Autómatas finitos no deterministas (AFND) 

Una extensión de los AFD’S es la de permitir que de cada estado o nodo del diagrama de estados salga un número de flechas mayor o menor que |Σ|. Así se puede permitir que falte la flecha correspondiente a alguno de los símbolos del alfabeto, o bien que haya varias flechas que salgan de un solo nodo con la misma etiqueta. Inclusive se permite que las transiciones tengan como etiqueta palabras de varias letras o hasta la palabra vacía.

Definición. Un autómata finito no determinista es un quíntuplo (K, Σ, Δ, s, F), donde K, Σ, s y F tienen el mismo significado para el caso de los AFD y Δ, llamada la relación de transición, es un subconjunto finito K X Σ* X K.

Ejemplo. Verificar si la palabra baabbaba es aceptada por el autómata finito no determinista siguiente:

Solución. La palabra baabbaba puede ser dividida en cuatro pedazos: p1 = b, p2 = a, p3 = abbab y p4 = a, cuya concatenación produce la palabra original. Ahora bien, podemos seguir la siguiente secuencia de estados (trayectoria) en el AFND dado:

Así probamos que la cadena baabbaba es aceptada por el AFND.

Los autómatas finitos se pueden utilizar para reconocer las expresiones regulares asociadas a los componentes léxicos en los lenguajes de programación.

Simulación de un autómata de estado finito en Jflap:

Simulación de un autómata de estado finito en Jflap from Eduardo Chavez Vasquez