Integrantes

Nicolas Ruiz
Javier Moreira
Richard Oyarzún
Juan Carlos Gallardo

Informe

Introducción

Cuando se habla de autómata, nos referimos a máquinas (abstractas o no) que sean capaces de computar. Las máquinas de Turing son un ejemplo de un autómata tan complejo que es capaz de resolver todos los problemas que una computadora actual puede resolver con precisión. Sin embargo, existen autómatas más simples que éstos, como los autómatas finitos o los autómatas de pila.

Los autómatas finitos tienen relación con los lenguajes regulares y las expresiones regulares, mientras que los autómatas de pila tienen relación con los lenguajes y las gramáticas de contexto libre. Las expresiones regulares se usan en la actualidad para la búsqueda de patrones en textos, mientras que las gramáticas de contexto libre juegan un papel escencial en la implementación de compiladores.



Conceptos


Gramáticas formales.-

Las gramáticas formales son sistemas de manipulación simbólica que permiten generar cadenas de símbolos, llamadas por esto bien formadas, o bien reconocer cuándo una cadena dada está, en efecto, bien formada. En este primer capítulo, meramente introductorio, ilustraremos con varios ejemplos estos tipos de sistemas e inclusive algunos otros sistemas un tanto más generales.


Jerarquía de Chomski en Autómatas.-


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


Automatas.-

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á 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.


Autómata finito.-

Un autómata finito (determinista) es pues una estructura de la forma


\begin{displaymath}\mbox{\it AF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)\end{displaymath}

donde
\begin{eqnarray*}Q &:& \mbox{\rm es el conjunto de {\em estados},} \\ \mbox{\i... ...bset Q &:& \mbox{\rm es el conjunto de estados {\em finales}.} \end{eqnarray*}

Se construyen a partir de un conjunto de estados Q y de un conjunto de símbolos de entrada T. Su funcionamiento queda determinado por una función de transición $t: Q \times T \rightarrow Q$. 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 todo autómata finito se cuenta con un estado inicial, $q_0 \in Q$ y un conjunto de estados finales $F\subset Q$.


Autómata no-determinista.-

Los autómatas no-deterministas se conforman como los autómatas finitos, salvo que sus transiciones, en lugar de ser funciones, son relaciones que a cada pareja (estado,estímulo) le asocian varios, uno o ningún estado.

Tiene una estructura de la forma $\mbox{\it SAFND\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0)$ donde
\begin{eqnarray*}Q &:& \mbox{\rm es el conjunto de {\em estados},} \\ \mbox{\i... ...on},} \\ q_0\in Q &:& \mbox{\rm es el estado {\em inicial}.} \end{eqnarray*}



Autómatas de pila.-

Son autómatas finitos que cuentan con un dispositivo de memoria muy elemental, del tipo pila, el cual es un almacenamiento lineal que funciona bajo el principio LIFO: Primero en Entrar, Ultimo 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 $t : Q \times T \times V \rightarrow Q \times V^*$, donde la relación $t(q, a, v) = (p, \mbox{\bf v})$ 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 $\mbox{\bf v}$''. Un autómata de pila reconoce a una palabra si, tras haberla leído, termina con su pila vacía.


Máquinas de Turing.-

Son autómatas finitos 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 ("scanned cell''), 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 $t : Q \times T \rightarrow Q \times T \times \mbox{\it Mov\/}$, donde $\mbox{\it Mov\/} = \{\mbox{\it Der\/},\mbox{\it Izq\/}\}$. Esta vez, la relación $t(q,a) = ( p, b, \mu )$ 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 $\mu$ de la leída''. De hecho, la relación $t(q,a) = ( p, b, \mu )$ puede escribirse como $(q,a;p,b,\mu)$, y por esto, decimos que una máquina de Turing queda especificada por su lista de quíntuplas.

Suscribirse a: Entradas (Atom)