Unidad 3 Lenguajes y Automatas 1

Unidad III: Autómatas finitos 

Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.
Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida. La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.

3.1 Definición formal Formalmente, 

Un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:

 Q: es un conjunto finito de estados;
 Σ: es un alfabeto finito;
 q0: es el estado inicial;
 δ: es una función de transición;
 F: es un conjunto de estados finales o de aceptación.

En el comienzo del proceso de reconocimiento de una cadena de entrada, el autómata finito se encuentra en el estado inicial y a medida que procesa cada símbolo de la cadena va cambiando de estado de acuerdo a lo determinado por la función de transición. Cuando se ha procesado el último de los símbolos de la cadena de entrada, el autómata se detiene en el estado final del proceso. Si el estado final en el que se detuvo es un estado de aceptación, entonces la cadena pertenece al lenguaje reconocido por el autómata; en caso contrario, la cadena no pertenece a dicho lenguaje.

Note que el estado inicial q0 de un autómata finito siempre es único, en tanto que los estados finales pueden ser más de uno, es decir, el conjunto puede contener más de un elemento. También puede darse el caso de que un estado final corresponda al mismo estado inicial.

3.2 Clasificación de AF 

Los autómatas se pueden clasificar en:
Deterministas: Cada combinación (estado, símbolo de entrada) produce un solo estado.
No Deterministas: Cada combinación (estado, símbolo de entrada) produce varios estados y además son posibles las transiciones con λ.

3.3 Conversión de un AFND a AFD 

3.4 Representación de ER usando AFND

3.5 Minimización de estados en un AF

Minimización de un AFD 

Dos estados de un autómata finito determinista son estados equivalentes si al unirse en un sólo estado, pueden reconocer el mismo lenguaje regular que si estuviesen separados. Esta unión de estados implica la unión tanto de sus transiciones de entrada como de salida. Si dos estados no son equivalentes, se dice que son estados distinguibles. Un estado final con un estado no-final nunca serán equivalentes.

Un AFD está minimizado, si todos sus estados son distinguibles y alcanzables. Un algoritmo de minimización de AFD es el siguiente:

1. Eliminar los estados inaccesibles del autómata.
2. Construir una tabla con todos los pares (p, q) de estados restantes.
3. Marcar en la tabla aquellas entradas donde un estado es final y el otro es no-final, es decir, aquellos pares de estados que son claramente distinguibles.

Para cada par (p, q) y cada símbolo a del alfabeto, tal que r = δ(p,a) y s = δ(q,a):
Si (r, s) ya ha sido marcado, entonces p y q también son distinguibles, por lo tanto marcar la entrada (p, q).
De lo contrario, colocar (p, q) en una lista asociada a la entrada (r, s).
Agrupar los pares de estados no marcados.

Luego del tercer paso, si la tabla creada queda completamente marcada, entonces el AFD inicial ya era mínimo.

La complejidad computacional del problema de minimizar un AFD es polinomial. De hecho, existen algoritmos más eficientes aún que el mostrado en este artículo (aunque menos intuitivos).11 Sin embargo, el problema de minimizar un autómata finito no determinista es NP-completo y PSPACE-completo

Ejemplo
En la primera figura del ejemplo, se muestra un autómata con el estado inaccesible d, el cual puede eliminarse inmediatamente. Luego se construye la tabla de pares de estados, y a continuación se marcan, de acuerdo a la tercera línea del algoritmo, las filas y columnas correspondientes a los estados finales c y g, salvo la celda que representa el par (c,g), puesto que al ser ambos estados finales, pueden ser estados equivalentes. Posteriormente, se marcan las celdas restantes de acuerdo a la cuarta línea del algoritmo, notando que el par (b, f) queda asociado con el par (c, g), y así finalmente se obtiene el autómata final, agrupando los estados b y f, así como c y g, tal y como se muestra en la segunda figura del ejemplo.