Autómatas

Los autómatas vienen a ser mecanismos formales que ``realizan'' derivaciones en gramáticas formales. La manera en que las realizan es mediante la noción de reconocimiento. Una palabra será generadaen una gramática si y sólo si la palabra hace transitar al autómata correspondiente a sus condiciones terminales. Por esto es que los autómatas son analizadores léxicos (llamados en inglés ``parsers'')de las gramáticas a que corresponden.
Autómatas regulares
Estos son los autómatas finitos más sencillos. Se construyen a partir de un conjunto de estados Q y de un conjunto de símbolos de entradaT. Su funcionamiento queda determinado por una función de transición [pic]. Si t(q,s)=p esto se interpreta como que el autómata transita del estado q al estado p cuando arriba el símbolo s. En todoautómata finito se cuenta con un estado inicial, [pic]y un conjunto de estados finales [pic]. Con todo esto definido, la estructura [pic]es un autómata regular. De manera natural, t se extiende a unafunción de transición [pic]: Toda palabra se aplica al autómata y éste, partiendo del estado inicial, transita con cada símbolo de la palabra dada según lo especifique t, correspondiendo a ese símbolo yal estado actual en el autómata. Una palabra es reconocida por el automata si lo hace arribar a un estado final. El lenguaje del autómata consta de todas las palabras reconocidas.

Autómatas de pilaEstos autómatas finitos cuentan con un dispositivo de memoria muy elemental, del tipo pila, el cual es un almacenamiento lineal que funciona bajo el principio PEUS[pic]: Primero en Entrar, Ultimo enSalir. Sea Q un conjunto de estados, sea T el alfabeto de entrada y sea V un alfabeto de pila. La función de transición es de la forma [pic], donde la relación [pic]se interpreta como sigue: ``Si seestá en el estado q, arriba el símbolo a y en el tope de la pila está el símbolo b entonces se pasa al estado p y se empila la palabra [pic]''. Un autómata de pila reconoce a una palabra si, tras...