Autómatas

Los autómatas son mecanismos que generan gramáticas formales. La manera en que realizan esto es mediante la noción de reconocimiento.

Se considera a los autómatas como analizadores léxicos de las gramáticas a que corresponden.

Un analizador léxico lee los caracteres de entrada del programa fuente, los agrupa en secuencias conocidas como lexemas y produce como salida una secuencia de tokens para cada lexema en el programa fuente. Un token es una estructura formada por el nombre del token y su valor.

Podemos encontrar seis tipos de autómatas: regulares, de pila, lineales, de pila no deterministas, máquinas de Turing y autómatas por jerarquía de Chomsky.

Fuente: Apuntes de Informática VII de la FCA de la UNAM