miércoles, 30 de marzo de 2011

AUTOMATA PUSDOWN

  Este modelo posee dos cintas con celdas iniciales a la izquierda e infinitas celdas a la derecha. Una de sus cintas es para almacenar los símbolos de entrada o palabra a ser analizada y solo se realizan lecturas sobre ella. La otra cinta funciona como una pila ( primer símbolo en entrar, último en salir) sobre ella se introducen y extraen símbolos especiales, a partir de un cabezal de lectura / escritura. Los cabezales están vinculados a una unidad de control.





Inicialmente la cinta de entrada contiene blancos, al igual que la cinta de tipo pila. Se coloca los símbolos que representan la palabra a ser analizada a partir del extremo izquierdo de la cinta de entrada. El cabezal de la cinta de entrada se encuentra, como Estado Inicial sobre el primer símbolo del extremo izquierdo. El cabezal de la cinta de tipo pila se posiciona sobre el tope de la pila o extremo izquierdo de la misma.
  Recordemos que el cabezal de lectura de la cinta de entrada solo puede leer un símbolo y desplazarse hacia la derecha. Por otro lado el cabezal de la cinta tipo pila puede escribir un símbolo (generalmente auxiliar) y desplazarse a la derecha o descargar (borrar) in símbolo y desplazarse a la derecha.




Formalmente, un autómata con pila puede ser descrito como una séptupla M = (S,Σ,Γ,δ,s,Z,F) donde:
  • Σ y Γ son alfabetos de entrada, de la cadena y de la pila respectivamente;
  • S un conjunto de estados;
  • \delta: S \times (\Sigma \cup \{\epsilon \} ) \times \Gamma \rightarrow \mathcal{P} ( S \times \Gamma^*)
  • s \in S es el estado inicial;
  • Z\ \in \Gamma es el símbolo inicial de la pila;
  • F \subseteq S es un conjunto de estados de aceptación o finales.


La interpretación de \delta (s, a, Z) = \{ (s_1, \gamma_1), (s_2, \gamma_2), \ldots, (s_n, \gamma_n) \}, con s, p_i \in Q, a \in (\Sigma \cup \{ \epsilon \} ), \gamma_i \in \Gamma es la siguiente:
Cuando el estado del autómata es s, el símbolo que la cabeza lectora está inspeccionando en ese momento es a, y en la cima de la pila nos encontramos el símbolo Z, se realizan las siguientes acciones:
  • Si a \in \Sigma, es decir no es la palabra vacía, se avanza una posición la cabeza lectora para inspeccionar el siguiente símbolo.
  • Se elimina el símbolo Z de la pila del autómata.
  • Se selecciona un par (pi,γi) de entre los existentes en la definición de δ(s,A,Z), la función de transición del autómata.
  • Se apila la cadena \gamma_i = A_1 A_2 \ldots A_k en la pila del autómata, quedando el símbolo A1 en la cima de la pila.
  • Se cambia el control del autómata al estado pi.


A continuación se colocan 3 archivos recopilados de Internet de respetables ingenieros e informáticos:
Link Directo: http://www.dirinfo.unsl.edu.ar/~ayl/Teorias/Apunte_Teoria/Teoria4-07_2.pdf  
Link directo: http://www.exa.unicen.edu.ar/catedras/ccomp1/Apunte4.pdf

entrada de Yukito-Sama @ 17:35   0 comentarios