- Los autómatas finitos se utilizan para reconocer patrones.
- Toma la cadena de símbolo como entrada y cambia su estado en consecuencia. Cuando se encuentra el símbolo deseado, se produce la transición.
- En el momento de la transición, el autómata puede pasar al siguiente estado o permanecer en el mismo estado.
- Los autómatas finitos tienen dos estados, Aceptar estado o Estado de rechazo . Cuando la cadena de entrada se procese correctamente y el autómata alcance su estado final, aceptará.
Definición formal de FA
Un autómata finito es una colección de 5 tuplas (Q, ∑, δ, q0, F), donde:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Modelo de autómata finito:
Los autómatas finitos se pueden representar mediante cinta de entrada y control finito.
Cinta de entrada: Es una cinta lineal que tiene un cierto número de celdas. Cada símbolo de entrada se coloca en cada celda.
Control finito: El control finito decide el siguiente estado al recibir una entrada particular de la cinta de entrada. El lector de cinta lee las celdas una por una, de izquierda a derecha, y a la vez solo se lee un símbolo de entrada.
Tipos de autómatas:
Hay dos tipos de autómatas finitos:
- DFA (autómatas finitos deterministas)
- NFA (autómatas finitos no deterministas)
1. DFA
DFA se refiere a autómatas finitos deterministas. Determinista se refiere a la unicidad del cálculo. En DFA, la máquina pasa a un estado solo para un carácter de entrada particular. DFA no acepta el movimiento nulo.
2. NFA
NFA significa autómata finito no determinista. Se utiliza para transmitir cualquier número de estados para una entrada particular. Puede aceptar el movimiento nulo.
Algunos puntos importantes sobre DFA y NFA:
- Todo DFA es NFA, pero NFA no es DFA.
- Puede haber varios estados finales tanto en NFA como en DFA.
- DFA se utiliza en el análisis léxico del compilador.
- La NFA es más un concepto teórico.