Autómatas

Autómatas a Pila: Anexo a la guía de estudio
Elena Gaudioso Vázquez y Tomás García Saiz Abril 2011

Motivación
El objetivo del presente anexo es clarificar algunos conceptos contenidos en elcapítulo 6 y en las orientaciones al estudio presentadas en la guía de estudio de la asignatura.

Criterios de aceptación en los autómatas a pila
De acuerdo a [2] existen dos criterios de aceptaciónpara los autómatas a pila: por estado de aceptación y por pila vacía. Este doble criterio se usa igualmente en la herramienta JFLAP [3] (ver Figura 1).

Figura 1: Pantalla de JFLAP donde se muestra eldoble criterio de aceptación En esta asignatura consideraremos que un autómata a pila acepta una cadena cuando es posible que, al terminar de leer la cadena de entrada, el autómata llegue a un estadode aceptación, independientemente del contenido de la pila. No obstante, dado cualquier autómata a pila no determinista, es posible modificarlo para que vacíe su pila antes de aceptar una cadena. Estono es necesariamente cierto para los autómatas a pila deterministas. Así por ejemplo, el lenguaje {xn : n ≥ 0} + {xn y n : n ≥ 0} es un lenguaje independiente del contexto determinista para el cual noes posible encontrar un autómata a pila determinista que vacíe su pila antes de aceptar las cadenas.

Jerarquía de los lenguajes independientes del contexto
Dentro de los lenguajes independientesdel contexto se puede establecer la jerarquía que se presenta en la Figura 2

1

Figura 2: Relación entre los lenguajes independientes del contexto deterministas, no deterministas y los lenguajesregulares. Ejemplos de lenguajes en cada uno de los niveles expuestos en la Figura 2: Lenguaje independiente del contexto no determinista: {xn y n : n ≥ 0} + {xn y 2n : n ≥ 0} Lenguaje independientedel contexto determinista para el cual no se puede construir un autómata a pila determinista que vacíe su pila antes de aceptar las cadenas: {xn : n ≥ 0} + {xn y n : n ≥ 0} Lenguaje independiente...