Autómata finito
Keywords: Autómata finito, Alfabeto, Autómata, Cadena de caracteres, Expresión regular, Informática, Ken Thompson, Lenguaje formal
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.
| Tabla de contenidos |
Definición formal
Formalmente, un autómata finito (AF) puede ser descrito como una 5-tupla (S, Σ, T, s, A) donde:
- Σ es un alfabeto;
- S un conjunto de estados;
- T es la función de transición: T: S × (Σ ∪ {ε}) → P(S);
-
es el estado inicial;
-
es un conjunto de estados de aceptación o finales.
Ejemplo 1
- Σ = {0,1},
- S = {S1, S2},
- T = {(S1,0,{S2});(S1,1,{S1});(S2,0,{S1});(S2,1,{S2})}
- s = S1
- A = {S1}.
Formas de representar un autómata finito
Además de notar un AF a través de su definición formal es posible representarlo a través de otras notaciones que resultan más cómodas. Entre estas notaciones, las más usuales son:
- Las Tablas de Transiciones: la tabla de transición para el AF del ejemplo 1 es
| 0 | 1
| |
| S1 | S2 | S1 |
| S2 | S1 | S2 |
- Los Diagramas de Transiciones: el diagrama de transición para el AF del ejempo 1 es
Imagen:DFAexample.png
Descripción informal de su funcionamiento
Al 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 determinísticos
Un AFD o autómata finito determinístico 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.
Un AFD se denomina completo cuando tiene una transición por cada estado y cada carácter del alfabeto. Si no cumple esta condición se lo denomina incompleto.
A partir de este autómata finito es posible hallar la expresión regular resolviendo un sistema de ecuaciones.
- S1 = 1 S1 + 0 S2 + ε
- S2 = 1 S2 + 0 S1
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, un pionero de la informática.
Autómatas finitos no determinísticos
Un AFN, AFND o autómata finito no determinístico es aquel que presenta cero, una o más transiciones por el mismo carácter del alfabeto y se clasifican en con transiciones Σ y sin transiciones Σ dependiendo de la existencia o no de una o más transiciones sin que el autómata lea el próximo carácter de la cadena que está analizando.
Véase también: Sistema determinístico