Automatas

Los autómatas son mecanismos formales que hacen derivaciones en gramáticas formales. La manera en que las realizan es mediante la noción de reconocimiento. Una palabra será generada en 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.

Automatas regulares:

Estos son los autómatas finitos más sencillos. Los autómatas finitos pueden ser deterministas, que tienen una transición por cada símbolo del alfabeto, y los no deterministas, que pueden, o no, tener una o más transiciones por cada símbolo del alfabeto, aún cuando existen estas diferencias, los dos autómatas, tanto deterministas como no deterministas pueden aceptar los mismos lenguajes.

En un autómata finito determinista, el autómata acepta una palabra si existe al menos un camino desde el estado q₀ a un estado final F etiquetado con la palabra de entrada. Si una transición no está definida, de manera que el autómata no puede saber como continuar leyendo la entrada, la palabra es rechazada.

Además de ser capaz de alcanzar más estados leyendo un símbolo, permite alcanzarlos sin leer ningún símbolo. Si un estado tiene transiciones etiquetadas con ε, entonces el Automata Finito No Determinista puede encontrarse en cualquier de los estados alcanzables por las transiciones ε, directamente o a través de otros estados con transiciones ε. El conjunto de estados que pueden ser alcanzados mediante este método desde un estado q, se denomina la clausura ε de q.



Autómatas de pila

Son autómatas regulares finitos con una memoria elemental, tipo pila, el cual es un almacenamiento lineal que funciona bajo el principio PEUS: Primero en Entrar, Último en Salir.

"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 , donde la relación se interpreta como sigue: ``Si se está 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 ''. Un autómata de pila reconoce a una palabra si, tras haberla leído, termina con su pila vacía. " (1)



Autómatas lineales.

Son autómatas de pila deterministas que a lo largo de su computación sólo hacen un "cambio de turno''. A grandes rasgos, esto significa que toda computación consiste de un procedimiento de empilar consecutivamente para después pasar a desempilar.

Un autómata lineal acotado (LBA de sus siglas en inglés Linear-Bounded Autómata) es una máquina de Turing no determinística (explicada mas adelante) que satisface las siguientes dos condiciones:

1. El alfabeto de entrada de cinta incluye dos símbolos: <>, los señaladores de extremo izquierdo y derecho, respectivamente.
2. El LBA no tiene movimientos a la izquierda de <>, ni puede sustituir los símbolos <>.

Autómatas de pila no deterministas

Son iguales que los autómatas de pila salvo en que su transición no es propiamente una función. Aquí se tiene que la transición es un subconjunto .


Maquinas de Turing

Son autómatas finitas con dos pilas que tienen un tope común. O equivalentemente, son autómatas que poseen una memoria dada por una cinta la cual es un almacenamiento lineal, infinito a ambos lados, con acceso a cualquier localidad en ella. El tope común es la casilla leída, una pila es la parte de la cinta a la derecha de la casilla leída y otra pila es su parte izquierda.


Las transiciones de la máquina quedan determinadas por una función , donde . Esta vez, la relación se interpreta como sigue: ``Si se está en el estado q y se lee el símbolo a entonces se escribe b, se pasa a p y se va a examinar la casilla al lado de la leída''. De hecho, la relación puede escribirse como , y por esto, decimos que una máquina de Turing queda especificada por su lista de quíntuplas.


Jerarquía de Chomsky en autómatas.

La complejidad de un autómata está determinada por sus capacidades de transición, de su dispositivo de memoria y las capacidades de inspección en su memoria. De manera natural la jerarquí a gramatical se traduce en una jerarquía equivalente en los autómatas.

(2)

Tipo Nombres Tipo de autómata reconocedor 0 Irrestricta Máquinas de Turing 1 Irrestricta con memoria limitada Máquinas de Turing con cinta acotada 2 Sensibles al contexto con borro Máquinas de Turing con dominio total 3 Sensibles al contexto no reductivas Máquinas de Turing con ``espacio lineal'' 4 Libres de contexto Autómatas de pila no-deterministas 5 Libres de contexto deterministas Autómatas de pila deterministas 6 Lineales Autómatas lineales 7 Regulares Autómatas regulares

Referencias:

(1) Tomado de http://delta.cs.cinvestav.mx/~gmorales/ta/node14.html

(2) Tomado de http://delta.cs.cinvestav.mx/~gmorales/ta/node18.html