Autómata finito

Esquema lógico de un autómata finito.

Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.

Definición formal

Formalmente, un autómata finito (AF) puede ser descrito como una 5-tupla $(S,\Sigma ,T,s,A)$ donde:

• $S$ un conjunto de estados;
• $\Sigma$ es un alfabeto;
• $T$ es la función de transición: $T:S\times (\Sigma \cup \{\epsilon \})\to {\mathcal {P}}(S)$;
• $s\in S$ es el estado inicial;
• $A\subseteq S$ es un conjunto de estados de aceptación o finales.

Ejemplo 1

• S = {S₁, S₂},
• Σ = {0,1},
• T = {(S₁,0,{S₂});(S₁,1,{S₁});(S₂,0,{S₁});(S₂,1,{S₂})}
• s = S₁
• A = {S₁}.

Máquinas DFA, NFA, GNFA, o Moore

S₁ y S₂ son estados y S₁ es un estado de aceptación. Cada arista está etiquetado con la entrada.

Descripción informal de su funcionamiento

En el comienzo del proceso de reconocimiento de una cadena, el AF 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. Si el estado en el que se detuvo es un estado de aceptación o final, entonces la cadena pertenece al lenguaje reconocido por el autómata, caso contrario, la cadena no pertenece a dicho lenguaje.

Autómatas finitos deterministas

Un AFD o autómata finito determinista es aquel autómata finito cuyo estado de llegada está unívocamente determinado por el estado inicial y el carácter leído por el autómata.

Formalmente, un autómata finito determinista (AFD) es similar a un Autómata de estados finitos, representado con una 5-tupla $(S,\Sigma ,T,s,A)$ donde:

• $\Sigma$ es un alfabeto;
• $S$ un conjunto de estados;
• $T$ es la función de transición: $T:S\times \Sigma \to {\mathcal {S}}$;
• $s\in S$ es el estado inicial;
• $A\subseteq S$ es un conjunto de estados de aceptación o finales.

Al contrario de la definición de autómata finito, este es un caso particular donde no se permiten transiciones vacías, el dominio de la función T es S (con lo cual no se permiten transiciones desde un estado de un mismo símbolo a varios estados).

A partir de este autómata finito es posible hallar la expresión regular resolviendo un sistema de ecuaciones.

S₁ = 1 S₁ + 0 S₂ + ε

S₂ = 1 S₂ + 0 S₁

Siendo ε la palabra nula. Resolviendo el sistema y haciendo uso de las reducciones apropiadas se obtiene la siguiente expresión regular: 1*(01*01*)*.

Inversamente, dada la expresión regular es posible generar un autómata que reconozca el lenguaje en cuestión utilizando el algoritmo de Thompson, desarrollado por Ken Thompson, uno de los principales creadores de UNIX, junto con Dennis Ritchie.

Un tipo de autómatas finitos deterministas interesantes son los tries.

Autómatas finitos no deterministas

Un AFND o autómata finito no determinista es aquel que presenta cero, una o más transiciones por el mismo carácter del alfabeto.

Un autómata finito no determinista también puede o no tener más de un nodo inicial.

Los AFND también se representan formalmente como tuplas de 5 elementos $(S,\Sigma ,T,s,A)$. La única diferencia respecto al AFD es T.

AFD: $T:S\times \Sigma \rightarrow S$

AFND: $T:S\times \Sigma \rightarrow P(S)$ (partes de S)

Debido a que la función de transición lleva a un conjunto de estados, el automáta puede estar en varios estados a la vez (o en ninguno si se trata del conjunto vacío de estados).

Autómatas finitos no deterministas con transiciones vacías

Un AFND-$\epsilon$ o autómata finito no determinista con transiciones $\epsilon$ permite cambiar de estado sin procesar ningún símbolo de entrada. Cuando el autómata llega a un estado, se encuentra en ese estado y en los estados a los que apunte éste mediante una transición $\epsilon$.

Un automata es un AFND: $T:S\times \Sigma \rightarrow P(S)$ (partes de S)

AFND-$\epsilon$: $T:S\times (\Sigma \cup \epsilon )\rightarrow P(S)$ (partes de S)

Cuando el símbolo de entrada es la palabra vacía ($\epsilon$), existe una transición $\epsilon$ entre los estados.

Cierre $\epsilon$*

AFD, AFND y AFND-$\epsilon$

Para todo AFND-$\epsilon$ existe un AFND equivalente y para todo AFND existe un AFD equivalente.

Existen algoritmos para transformar un autómata en otro. Los AFD son los más sencillos de construir, por tanto, puede ser útil diseñar un autómata complejo como AFND-$\epsilon$ o AFND para luego transformarlo en AFD para su implementación.

Véase también

• Sistema determinista
• Teoría de grafos
• Lenguaje regular

Enlaces externos

• Wikimedia Commons alberga una galería multimedia sobre Autómata finito.

• SELFA-Pro Herramienta online de uso gratuito para trabajar con lenguajes regulares, expresiones regulares, gramáticas, autómatas, autómatas a pila y realizar multitud de operaciones y transformaciones entre ellos, no se requiere ningún tipo de instalación, solamente un navegador web SELFA-Pro (Universidad de Castilla-La Mancha)

• Chalchalero! Herramienta visual (gratuita y en español) para trabajar con lenguajes regulares, expresiones regulares, gramáticas regulares y autómatas finitos Proyecto SEPa! (Universidad Católica de Santiago del Estero)

• Herramienta para experimentar con lenguajes formales, autómatas, etc

• Libro electrónico gratuito sobre autómatas y lenguajes formales (Tecnológico de Monterrey, México)