Máquina de estado finito
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 finito, una función de transición, un estado inicial y un conjunto de estados finales. 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.
El origen de los autómatas finitos probablemente se remonta a su uso implícito en máquinas electromecánicas, desde principios del siglo XX. Ya en 1907, el matemático ruso Andréi Márkov formalizó un proceso llamado cadena de Markov, donde la ocurrencia de cada evento depende con una cierta probabilidad del evento anterior. Esta capacidad de "recordar" es utilizada posteriormente por los autómatas finitos, que poseen una memoria primitiva similar, en que la activación de un estado también depende del estado anterior, así como del símbolo o palabra presente en la función de transición.
Posteriormente, en 1943, surge una primera aproximación formal de los autómatas finitos con el modelo neuronal de McCulloch-Pitts. Durante la década de 1950 prolifera su estudio, frecuentemente llamándoseles máquinas de secuencia; se establecen muchas de sus propiedades básicas, incluyendo su interpretación como lenguajes regulares y su equivalencia con las expresiones regulares. Al final de esta década, en 1959, surge el concepto de autómata finito no determinista en manos de los informáticos teóricos Michael O. Rabin y Dana Scott.
En la década de 1960 se establece su conexión con las series de potencias y los sistemas de sobreescritura. Finalmente, con el desarrollo del sistema operativo Unix en la década de 1970, los autómatas finitos encuentran su nicho en el uso masivo de expresiones regulares para fines prácticos, específicamente en el diseño de analizadores léxicos (comando lex) y la búsqueda y reemplazo de texto (comandos ed y grep). A partir de ese tiempo, los autómatas finitos también se comienzan a utilizar en sistemas dinámicos.
Formalmente, un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:
Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:
Otra manera de describir el funcionamiento de un autómata finito es mediante el uso de tablas de transiciones o matrices de estados. Dos posibles tablas para el ejemplo de la imagen anterior podrían ser las siguientes:
La primera representa explícitamente los parámetros y el valor que toma cada ocurrencia de la función de transición. La segunda es más compacta, y marca con una flecha el estado inicial, y con un asterisco los estados finales.
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 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.
Si Σ es un alfabeto, entonces se denota Σ* al conjunto de todas las cadenas de caracteres o palabras que se pueden conformar con dicho alfabeto.
Una función de transición δ se puede generalizar a una función δ*, que opera sobre estados y secuencias de símbolos, en lugar de símbolos individuales del alfabeto. Así, esta nueva función de transición se define , permitiendo caracterizar los autómatas de manera más abreviada y sin perder expresividad.
La función δ* puede expresarse también de manera recursiva, definiendo para toda cadena x ∈ Σ*, todo símbolo a ∈ Σ, y un estado q ∈ Q:
Se llama configuración de un autómata finito a un "instante" en el cómputo de la máquina; es decir, al estado actual en que se encuentra dicho cómputo, junto con la palabra que ha sido procesada hasta ese momento. Formalmente, se define como un par ordenado (q, x) ∈ Q × Σ*. De este modo, se puede definir además la configuración inicial del autómata, como el par (q0,x), donde x es la entrada; y la configuración final, como el par (q,ε), con q ∈ F.
De este modo, el lenguaje regular aceptado por un autómata finito A puede denotarse como L(A) = {w; δ*(q0,w)∈ F}, es decir, como el conjunto de todas las configuraciones iniciales que conllevan a estados finales.
Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado q ∈ Q en que se encuentre el autómata, y con cualquier símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(q,a).
En un AFD no pueden darse ninguno de estos dos casos:
Un tipo interesante de autómatas finitos deterministas son los llamados acíclicos y un ejemplo de estos son los tries.
Un autómata finito no determinista (abreviado AFND) es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.
Haciendo la analogía con los AFDs, en un AFND puede darse cualquiera de estos dos casos:
Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada.
Formalmente, se distingue de la 5-tupla que define a un autómata finito determinista en su función de transición. Mientras en un AFD esta función se define de la siguiente manera:
en un AFND se define como:
Para el caso de los AFND-ε, se suele expresar la función de transición de la forma:
donde P(Q) es el conjunto potencia de Q.
Esto significa que los autómatas finitos deterministas son un caso particular de los no deterministas, puesto que Q pertenece al conjunto P(Q).
La interpretación que se suele hacer en el cómputo de un AFND es que el autómata puede estar en varios estados a la vez, generándose una ramificación de las configuraciones existentes en un momento dado. Otra interpretación puede ser imaginar que la máquina "adivina" a qué estado debe ir, eligiendo una transición entre varias posibles.
Note finalmente que en un autómata finito no determinista podemos aceptar la existencia de más de un nodo inicial, relajando aún más la definición original.
Se dice que dos autómatas finitos son equivalentes, si ambos reconocen el mismo lenguaje regular.
Toda expresión regular (que define a su vez un lenguaje regular) puede ser expresada como un autómata finito determinista, y viceversa. Dada una expresión regular, es posible construir un AFND-ε que reconozca dicho lenguaje, por ejemplo mediante el algoritmo de Thompson. Luego, todo AFND-ε puede transformarse en un AFND equivalente, así como todo AFND puede transformarse en un AFD equivalente, mediante el método llamado construcción de conjunto potencia. Así, por transitividad, para cualquier autómata finito no determinista siempre existe un autómata finito determinista equivalente, y viceversa.
Normalmente en el diseño de autómatas finitos, lo primero que se hace es construir un AFND-ε, que es el más sencillo de construir, por poseer menos restricciones en su función de transiciones. Luego dicho autómata se reduce a un AFND, y finalmente a un AFD, el cual por sus características deterministas ya puede ser implementado sin problemas utilizando un lenguaje de programación.
La conversión de un AFND-ε en un AFND se basa en el concepto de clausura-ε, que corresponde a una clausura transitiva contextualizada en la teoría de autómatas.
Dado un estado q, se llama clausura-ε(q) al conjunto de todos los estados a los que se puede acceder a partir de q, procesándose a lo más un único símbolo de la entrada. Puede definirse recursivamente de la siguiente manera:
El algoritmo para eliminar las transiciones vacías es el siguiente:
En el ejemplo de la figura, se tendrá inicialmente:
Con esto concluye el algoritmo y se obtiene el autómata de la figura.
En algunos casos puede ocurrir que al quitar las transiciones épsilon obtengamos directamente un AFD, pues la única razón de no-determinismo era justamente la presencia de dichas transiciones.
Todo AFND (QN, Σ, q0, δN, FN) puede convertirse en un AFD (QD, Σ, q0, δD, FD) equivalente, que mantiene el alfabeto Σ y el estado inicial q0 originales. La conversión implica pasar por un AFD intermedio con estados y transiciones redundantes, que al no ser accesibles a partir del estado inicial, son eliminados para obtener el AFD definitivo.
Para definir el AFD intermedio, se deben seguir los siguientes pasos:
En las figuras de ejemplo, como el AFND inicial posee tres estados (q0, q1, q2), entonces el AFD intermedio poseerá siete ({q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2}), y como el estado final original era q2, entonces los estados finales del AFD intermedio son {q2}, {q0, q2}, {q1, q2} y {q0, q1, q2}. Con respecto a las nuevas transiciones, note por ejemplo que se mantuvo la transición δN(q0,1)=q0, siendo ahora llamada δD({q0},1)={q0}; sin embargo, dado que originalmente se daba que δN(q0,0)=q0 y δN(q0,0)=q1, ahora estas dos transiciones fueron reemplazadas por δD({q0},0)={q0, q1}. Para terminar, note que los estados {q1}, {q2} y {q1, q2} no están conectados con el resto del autómata que posee el estado inicial; por tanto, son eliminados. Asimismo es eliminado también {q0, q1, q2}, pues a pesar de estar conectado con el resto del autómata, no es accesible a partir de {q0}. Así finalmente, eliminando estos cuatro estados, así como sus respectivas transiciones, se obtiene el AFD buscado.
Dos estados de un autómata finito determinista son estados equivalentes si al unirse en un solo 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:
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). Sin embargo, el problema de minimizar un autómata finito no determinista es NP-completo y PSPACE-completo.
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.
Existen diversas generalizaciones posibles de hacer sobre los autómatas finitos, para aumentar su uso y expresividad. Así, por ejemplo, se definen los transductores de estados finitos como autómatas finitos que están dotados además de un alfabeto de salida, distinto al de entrada, y que pueden poseer más de un estado inicial. Las máquinas de Moore y máquinas de Mealy son conocidos ejemplos de transductores, que se utilizan sobre todo para modelar sistemas secuenciales.
Es incluso posible aumentar el poder de cómputo de un autómata finito, permitiendo un alfabeto adicional sobre éste, que actúe sobre una memoria de tipo pila para ser considerada en cada transición. Esta es la idea utilizada por los llamados autómatas con pila, los cuales son capaces de reconocer lenguajes libres de contexto, que están un nivel por sobre los lenguajes regulares en la Jerarquía de Chomsky.