• La máquina de estados finitos se utiliza para reconocer patrones.
• La máquina de autómatas finitos toma la cadena de símbolos como entrada y cambia su estado en consecuencia. En la entrada, cuando se encuentra el símbolo deseado, se produce la transición.
• Durante la transición, los autómatas pueden pasar al siguiente estado o permanecer en el mismo estado.
• FA tiene dos estados: aceptar estado o rechazar estado. Cuando la cadena de entrada se procese con éxito y el autómata alcance su estado final, aceptará.

Un autómata finito consta de lo siguiente:

Q: conjunto finito de estados
∑: conjunto finito de símbolo de entrada
q0: estado inicial
F: estado final
d: función de transición

La función de transición se puede definir como

 δ: Q x ∑ →Q 

FA se caracteriza de dos maneras:

1. DFA (autómatas finitos)
2. NDFA (autómatas finitos no deterministas)

DFA

DFA significa Autómata Finito Determinista. Determinista se refiere a la unicidad del cálculo. En DFA, el carácter de entrada pasa a un solo estado. DFA no acepta el movimiento nulo, lo que significa que DFA no puede cambiar de estado sin ningún carácter de entrada.

DFA tiene cinco tuplas {Q, ∑, q0, F, δ}

Ejemplo

Vea un ejemplo de autómatas finitos deterministas:

los números del alfabeto

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 

NDFA

NDFA se refiere a los autómatas finitos no deterministas. Se utiliza para transitar cualquier número de estados para una entrada en particular. NDFA acepta el movimiento NULL, lo que significa que puede cambiar de estado sin leer los símbolos.

La NDFA también tiene cinco estados al igual que la DFA. Pero el NDFA tiene una función de transición diferente.

La función de transición del NDFA se puede definir como:

Ejemplo

Vea un ejemplo de autómatas finitos no deterministas:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3}