DEFINICIÓN

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.
Éstos se definen mediante una quíntupla (E, Q, f, q0, F ) donde:

E: alfabeto de entrada.
Q: conjunto de estados; es conjunto finito no vacío.
f: función de transición. f(p,a)=q
q0 : (perteneciente a Q) estado inicial.
F : (perteneciente a Q) conjunto de estados finales o de aceptación.