Diagramas de estado
Ya que el scanner debe reconocer tokens, debemos buscar la posibilidad de describir los tokens a manera de reconocimiento y no de manera generativa. La descripción de los tokens por medio de cómo pueden ser reconocidos (o aceptados) se hace en términos de un modelo matemático llamado un aceptor de estado finito.
En lo que resta de esta sección, describiremos un conjunto de tokens por medio de la especificación de un aceptor que reconocerá ese conjunto. Cabe aclarar que las gramáticas regulares también pueden utilizarse para este propósito.
Un aceptor de estado finito o autómata finito puede considerarse como una máquina consistente de una cabeza de lectura y una caja de control de estado finito. La máquina lee una cinta de carácter a la vez, de izquierda a derecha. Existe un número finito de estados que la máquina puede adoptar.
Cada vez que la máquina lee el siguiente carácter, ocurre en ella un cambio de estado. Siempre que un aceptor de estado finito inicia la lectura de una cinta, éste se encuentra en cierto estado llamado estado inicial.
Algunos de los estados que el aceptor puede adoptar se llaman estados finales, y si el aceptor intenta leer más allá del final de la cinta mientras se encuentra en un estado final, la cadena que está en la cinta se dice que fue aceptada por el autómata finito. En otras palabras, la cadena pertenece al lenguaje que es aceptado por el autómata finito.
