Dispositivo de reconocimiento que procesa mecanicamente cadenas de caracteres con el proposito de decidir su pertenencia o no a un conjunto de cadenas o lenguaje formal. Es un sistema formado por un conjunto finito y no vacio de estados, un alfabeto finito y un conjunto de reglas de transición entre los estados en función del alfabeto. Destaca un elemento del conjunto de estados como estado inicial y un subconjunto de los estados como conjunto de estados finales.
