Esta conformado por un alfabeto, por estados (nodos) y transiciones o aristas que son los que unen los estados, parte de un estado inicial con una cadena de caracteres que corresponden a la entrada, para finalmente construir un grafo.
Las transiciones se pueden dar de nodo a nodo o sobre el mismo para finalmente terminar en un estado final o de aceptacion
FUNCIONES DE LAS MAQUINAS DE ESTADO FINITO
- Reconocer lenguajes regulares segun la gerarquia de Chomsky
Las maquinas de estado finito se describe como M = (S,∑, A , sk),
ES = {s1, s2, ….,sm } es un conjunto finito de nodos
E∑ es un alfabeto infinito de etiquetas
EA es un conjunto de aristas etiquetadas que unen los nodos
Esk es el estado inicial
CLASES DE AUTOMATAS FINITOS
- AUTOMATA FINITO DETERMINISTICO (DFA)
Es un modelo matemático de un sistema que recibe una cadena constituida por símbolos del alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce .
Su funcionamiento se basa en una funcion de transició, 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.
AUTOMATA FINITO NO DETERMINISTICO (NDFA)
Este presenta cero, una o mas transiciones por el mismo carácter del alfabeto. Puede o no tener mas de un estado inicial
Cuando el autómata ha terminado de leer, y se encuentra en un estado de aceptación, se dice que el AFND acepta la cadena, de lo contrario se dice que la cadena de caracteres es rechazada. Tanto para un AFND como para un (AFD) se puede aceptar el mismo lenguaje. Por lo tanto, es posible convertir un AFND existente en un AFD para el desarrollo de una máquina tal vez más simple
