Autómatas finitos

Los autómatas finitos son las máquinas que ocuparían el nivel inferior en la jerarquía de clasificación de las máquinas. Esto es debido a su limitada capacidad de procesamiento, ya que son capaces de tomar determinaciones en función de su estado y entrada actual, pero incapaces de recordar lo sucedido hasta ese momento.
Aunque a primera vista podemos pensar en pasarlos por alto, que son inútiles, tienen algunas aplicaciones prácticas interesantes (es el caso que veremos de analizadores léxicos de los compiladores) y además los tomaremos como base para otros tipos de máquinas más complejas y con mayor capacidad de procesamiento.
Los representamos con un mecanismo de control, donde aparecerán todos los posibles estados (un número finito, de ahí que se les denomine autómatas finitos) en que se pueden encontrar. Similar a un reloj, con una aguja que marcará en cada momento el estado actual.
El autómata finito recibe a través del flujo de entrada, un símbolo por vez y decide (el mecanismo de control está programado para tomar la decisión) según sea éste y el estado actual, si cambia a otro estado o permanece igual. Los símbolos de la entrada deberán pertenecer a un conjunto de símbolos, que previamente establecemos, nunca será vacío y en todo caso será finito (por ejemplo los caracteres del teclado), es el llamado alfabeto de la máquina. El autómata comienza a funcionar y lee de izquierda a derecha todos los símbolos de entrada, uno a uno, y en cada caso va tomando las determinaciones oportunas. Pero, digamos que según toma estas determinaciones, las “olvida”. Cuando llega al final de la cadena, ésta será aceptada si el estado en que se encuentra es de aceptación, caso contrario, la rechaza.
Un caso especial es cuando la máquina llega al fin de la entrada sin haber leído ningún símbolo, ya que ha encontrado al inicio una marca de fin de cadena. En este caso se dice que la entrada es una cadena vacía.
Ejemplos de aplicación son los analizadores léxicos de los compiladores. Éstos leen el programa fuente y catalogan las entradas según sean nombres de variables, constantes o palabras reservadas, comprobando en cada caso que cumplan determinadas reglas. Por ejemplo suele ser habitual que deban comenzar por una letra, a continuación deban tener un número limitado de letras o números y finalmente tengan un indicador de fin de cadena (por ejemplo un espacio en blanco).
En el dibujo de abajo se representa el autómata leyendo los símbolos de una cinta, de esta manera podemos visualizar su funcionamiento.