Autómata finito

Revisión del 14:20 16 oct 2019 de Olga ciget.pinardelrio (discusión | contribuciones)
(dif) ← Revisión anterior | Revisión actual (dif) | Revisión siguiente → (dif)
Autómata finito
Información sobre la plantilla
Autómata F.JPG

Autómata finito (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.

Historia

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.

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 de símbolos terminales;
  • q0 es el estado inicial en Q;
  • δ es la relación de transiciones de la forma <qi,x,qj> con qi y qj como estados de Q y x, símbolo de Σ ó puede ser también la cadena vacía;
  • F es el conjunto de estados finales o de aceptación y (evidentemente) subconjunto de Q.

Autómata finito determinista

Un autómata finito determinista (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:

  • Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
  • Que existan transiciones del tipo δ(q,ε), salvo que q sea un estado final, sin transiciones hacia otros estados.

Un ejemplo interesante de autómatas finitos deterministas son los tries.

Autómata finito no determinista

Un autómata finito no determinista (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:

  • Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
  • Que existan transiciones del tipo δ(q,ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.

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.

Equivalencias entre autómatas finitos

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.

Conversión de un AFND-ε a un AFND

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:

  • (Base inductiva) Para todo estado q, q ∈ clausura-ε(q).
  • (Inducción) Dados dos estados p y r, si p ∈ clausura-ε(q) y r ∈ δ(p,ε), entonces r ∈ clausura-ε(q).

El algoritmo para eliminar las transiciones vacías es el siguiente:

  • Se calcula la clausura-ε del estado inicial, formándose un conjunto A que corresponderá al estado inicial del nuevo autómata.
  • Para cada símbolo del alfabeto, se verifican los estados alcanzables a partir de algún estado contenido en A, y se calcula la clausura-ε de dichos estados alcanzables. Si dichas clausuras producen nuevos conjuntos distintos de A, estos serán nuevos estados a los que se accederá a partir de A y del símbolo correspondiente.
  • Se repite lo anterior para cada nuevo conjunto, hasta que no existan transiciones posibles para ningún símbolo del alfabeto.

Generalizaciones de autómatas finitos

Existes 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.

Fuentes

Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey D. (2001) (en inglés). Introduction to Automata Theory, Languages, and Computation. Massachusetts, Estados Unidos: Addison-Wesley.