Autómata de empuje hacia abajo

Tipo de autómata

Clases de autómatas

En la teoría de la computación , una rama de la ciencia informática teórica , un autómata pushdown ( PDA ) es un tipo de autómata que emplea una pila .

Los autómatas pushdown se utilizan en teorías sobre lo que pueden calcular las máquinas. Son más capaces que las máquinas de estados finitos , pero menos que las máquinas de Turing (véase más abajo). Los autómatas pushdown deterministas pueden reconocer todos los lenguajes deterministas libres de contexto, mientras que los no deterministas pueden reconocer todos los lenguajes libres de contexto ; los primeros se utilizan a menudo en el diseño de analizadores sintácticos .

El término "pushdown" se refiere al hecho de que la pila puede considerarse como "empujada hacia abajo" como un dispensador de bandejas en una cafetería, ya que las operaciones nunca funcionan en elementos distintos del elemento superior. Un autómata de pila , por el contrario, permite el acceso y las operaciones en elementos más profundos. Los autómatas de pila pueden reconocer un conjunto estrictamente más grande de lenguajes que los autómatas pushdown. ^[1] Un autómata de pila anidado permite el acceso completo y también permite que los valores apilados sean subpilas completas en lugar de solo símbolos finitos individuales.

Descripción informal

Diagrama de un autómata de empuje hacia abajo

Una máquina de estados finitos solo observa la señal de entrada y el estado actual: no tiene una pila con la que trabajar y, por lo tanto, no puede acceder a valores anteriores de la entrada. Solo puede elegir un nuevo estado, el resultado de seguir la transición. Un autómata de empuje (PDA) se diferencia de una máquina de estados finitos en dos aspectos:

1. Puede utilizar la parte superior de la pila para decidir qué transición tomar.
2. Puede manipular la pila como parte de la realización de una transición.

Un autómata de inserción lee una cadena de entrada dada de izquierda a derecha. En cada paso, elige una transición indexando una tabla por símbolo de entrada, estado actual y el símbolo en la parte superior de la pila. Un autómata de inserción también puede manipular la pila, como parte de la realización de una transición. La manipulación puede ser para empujar un símbolo particular a la parte superior de la pila, o para sacarlo de la parte superior de la pila. El autómata puede, alternativamente, ignorar la pila y dejarla como está.

Juntar: Dados un símbolo de entrada, un estado actual y un símbolo de pila, el autómata puede seguir una transición a otro estado y, opcionalmente, manipular (empujar o sacar) la pila.

Si, en cada situación, como máximo una de estas acciones de transición es posible, entonces el autómata se denomina autómata de empuje descendente determinista (DPDA) . En general, si son posibles varias acciones, entonces el autómata se denomina PDA general o no determinista . Una cadena de entrada dada puede conducir a un autómata de empuje descendente no determinista a una de varias secuencias de configuración; si una de ellas conduce a una configuración de aceptación después de leer la cadena de entrada completa, se dice que esta última pertenece al lenguaje aceptado por el autómata .

Definición formal

Utilizamos la notación del lenguaje formal estándar: denota el conjunto de cadenas de longitud finita sobre el alfabeto y denota la cadena vacía . ${\displaystyle \Gamma ^{*}}$ ${\displaystyle \Gamma }$ ${\displaystyle \varepsilon }$

Una PDA se define formalmente como una tupla de 7:

${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Z,F)}$dónde

• ${\displaystyle Q}$es un conjunto finito de estados
• ${\displaystyle \Sigma }$es un conjunto finito que se llama alfabeto de entrada
• ${\displaystyle \Gamma }$es un conjunto finito que se llama alfabeto de pila
• ${\displaystyle \delta }$es un subconjunto finito de , la relación de transición ${\displaystyle Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}}$
• ${\displaystyle q_{0}\in Q}$es el estado inicial
• ${\displaystyle Z\in \Gamma }$es el símbolo de pila inicial
• ${\displaystyle F\subseteq Q}$es el conjunto de estados aceptantes

Un elemento es una transición de . Tiene el significado previsto de que , en el estado , en la entrada y con el símbolo de pila superior, puede leer , cambiar el estado a , hacer estallar , reemplazándolo por empujar . El componente de la relación de transición se utiliza para formalizar que la PDA puede leer una letra de la entrada o continuar sin tocar la entrada. ^{[ cita requerida ]} ${\displaystyle (p,a,A,q,\alpha )\in \delta }$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle p\in Q}$ ${\displaystyle a\in \Sigma \cup \{\varepsilon \}}$ ${\displaystyle A\in \Gamma }$ ${\displaystyle a}$ ${\displaystyle q}$ ${\displaystyle A}$ ${\displaystyle \alpha \in \Gamma ^{*}}$ ${\displaystyle (\Sigma \cup \{\varepsilon \})}$

En muchos textos ^{[2] : 110} la relación de transición se reemplaza por una formalización (equivalente), donde

• ${\displaystyle \delta }$es la función de transición , que se asigna a subconjuntos finitos de ${\displaystyle Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma }$ ${\displaystyle Q\times \Gamma ^{*}}$

Aquí se incluyen todas las acciones posibles en el estado con en la pila, mientras se lee en la entrada. Se escribe, por ejemplo, precisamente cuando porque . Nótese que finito en esta definición es esencial. ${\displaystyle \delta (p,a,A)}$ ${\displaystyle p}$ ${\displaystyle A}$ ${\displaystyle a}$ ${\displaystyle \delta (p,a,A)=\{(q,BA)\}}$ ${\displaystyle (q,BA)\in \{(q,BA)\},(q,BA)\in \delta (p,a,A),}$ ${\displaystyle ((p,a,A),\{(q,BA)\})\in \delta }$

Cálculos

Un paso del autómata pushdown

Para formalizar la semántica del autómata pushdown se introduce una descripción de la situación actual. Cualquier 3-tupla se denomina descripción instantánea (ID) de , que incluye el estado actual, la parte de la cinta de entrada que no se ha leído y el contenido de la pila (el símbolo superior escrito primero). La relación de transición define la relación de paso de en las descripciones instantáneas. Para la instrucción existe un paso , para cada y cada . ${\displaystyle (p,w,\beta )\in Q\times \Sigma ^{*}\times \Gamma ^{*}}$ ${\displaystyle M}$ ${\displaystyle \delta }$ ${\displaystyle \vdash _{M}}$ ${\displaystyle M}$ ${\displaystyle (p,a,A,q,\alpha )\in \delta }$ ${\displaystyle (p,ax,A\gamma )\vdash _{M}(q,x,\alpha \gamma )}$ ${\displaystyle x\in \Sigma ^{*}}$ ${\displaystyle \gamma \in \Gamma ^{*}}$

En general, los autómatas de empuje son no deterministas, lo que significa que en una descripción instantánea dada puede haber varios pasos posibles. Cualquiera de estos pasos puede elegirse en un cálculo. Con la definición anterior, en cada paso siempre se extrae un solo símbolo (de la parte superior de la pila), reemplazándolo con tantos símbolos como sea necesario. En consecuencia, no se define ningún paso cuando la pila está vacía. ${\displaystyle (p,w,\beta )}$

Los cálculos del autómata pushdown son secuencias de pasos. El cálculo comienza en el estado inicial con el símbolo de pila inicial en la pila y una cadena en la cinta de entrada, por lo tanto con descripción inicial . Hay dos modos de aceptación. El autómata pushdown acepta por estado final, lo que significa que después de leer su entrada, el autómata alcanza un estado de aceptación (en ), o acepta por pila vacía ( ), lo que significa que después de leer su entrada, el autómata vacía su pila. El primer modo de aceptación utiliza la memoria interna (estado), el segundo la memoria externa (pila). ${\displaystyle q_{0}}$ ${\displaystyle Z}$ ${\displaystyle w}$ ${\displaystyle (q_{0},w,Z)}$ ${\displaystyle F}$ ${\displaystyle \varepsilon }$

Formalmente se define

1. ${\displaystyle L(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(f,\varepsilon ,\gamma )}$con y (estado final) ${\displaystyle f\in F}$ ${\displaystyle \gamma \in \Gamma ^{*}\}}$
2. ${\displaystyle N(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(q,\varepsilon ,\varepsilon )}$con (pila vacía) ${\displaystyle q\in Q\}}$

Aquí representa el cierre reflexivo y transitivo de la relación de pasos, es decir, cualquier número de pasos consecutivos (cero, uno o más). ${\displaystyle \vdash _{M}^{*}}$ ${\displaystyle \vdash _{M}}$

Para cada autómata de pushdown, estos dos lenguajes no deben tener ninguna relación: pueden ser iguales, pero normalmente no es así. Una especificación del autómata también debe incluir el modo de aceptación previsto. En todos los autómatas de pushdown, ambas condiciones de aceptación definen la misma familia de lenguajes.

Teorema. Para cada autómata de empuje se puede construir un autómata de empuje tal que , y viceversa, para cada autómata de empuje se puede construir un autómata de empuje tal que ${\displaystyle M}$ ${\displaystyle M'}$ ${\displaystyle L(M)=N(M')}$ ${\displaystyle M}$ ${\displaystyle M'}$ ${\displaystyle N(M)=L(M')}$

Ejemplo

La siguiente es la descripción formal del PDA que reconoce el lenguaje por estado final: ${\displaystyle \{0^{n}1^{n}\mid n\geq 0\}}$

PDA para (por estado final) ${\displaystyle \{0^{n}1^{n}\mid n\geq 0\}}$

${\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)}$, dónde

• Estados: ${\displaystyle Q=\{p,q,r\}}$
• Alfabeto de entrada: ${\displaystyle \Sigma =\{0,1\}}$
• alfabeto de pila: ${\displaystyle \Gamma =\{A,Z\}}$
• estado inicial: ${\displaystyle q_{0}=p}$
• Símbolo de pila inicial: Z
• Estados aceptantes: ${\displaystyle F=\{r\}}$

La relación de transición consta de las siguientes seis instrucciones: ${\displaystyle \delta }$

${\displaystyle (p,0,Z,p,AZ)}$,

${\displaystyle (p,0,A,p,AA)}$,

${\displaystyle (p,\epsilon ,Z,q,Z)}$,

${\displaystyle (p,\epsilon ,A,q,A)}$,

${\displaystyle (q,1,A,q,\epsilon )}$, y

${\displaystyle (q,\epsilon ,Z,r,Z)}$.

En palabras, las dos primeras instrucciones dicen que en el estado p en cualquier momento el símboloSe lee 0 y se coloca un A en la pila. Colocar el símbolo A sobre otro A se formaliza como reemplazar el A superior por AA (y lo mismo ocurre con colocar el símbolo A sobre un Z ).

La tercera y cuarta instrucciones dicen que, en cualquier momento, el autómata puede pasar del estado p al estado q .

La quinta instrucción dice que en el estado q , para cada símbolo1 lectura, aparece una A.

Finalmente, la sexta instrucción dice que la máquina puede moverse del estado q al estado de aceptación r sólo cuando la pila consiste en un solo Z.

Parece que no existe una representación de uso general para PDA. Aquí hemos representado la instrucción mediante un borde del estado p al estado q etiquetado como (leer a ; reemplazar A por ). ${\displaystyle (p,a,A,q,\alpha )}$ ${\displaystyle a;A/\alpha }$ ${\displaystyle \alpha }$

Explicación

aceptando el cálculo para0011

A continuación se muestra cómo el PDA anterior realiza los cálculos en diferentes cadenas de entrada. El subíndice M del símbolo de paso se omite aquí. ${\displaystyle \vdash }$

1. Cadena de entrada = 0011. Hay varios cálculos, según el momento en que se realiza el paso del estado p al estado q . Solo uno de ellos es aceptable.
   1. ${\displaystyle (p,0011,Z)\vdash (q,0011,Z)\vdash (r,0011,Z)}$
      El estado final es aceptable, pero la entrada no se acepta de esta manera porque no ha sido leída.
   2. ${\displaystyle (p,0011,Z)\vdash (p,011,AZ)\vdash (q,011,AZ)}$
      No es posible realizar más pasos.
   3. ${\displaystyle (p,0011,Z)\vdash (p,011,AZ)\vdash (p,11,AAZ)\vdash (q,11,AAZ)\vdash (q,1,AZ)\vdash (q,\epsilon ,Z)\vdash (r,\epsilon ,Z)}$
      Aceptando el cálculo: finaliza en el estado de aceptación, mientras se haya leído la entrada completa.
2. Cadena de entrada = 00111. Nuevamente hay varios cálculos, pero ninguno es aceptable.
   1. ${\displaystyle (p,00111,Z)\vdash (q,00111,Z)\vdash (r,00111,Z)}$
      El estado final es aceptable, pero la entrada no se acepta de esta manera porque no ha sido leída.
   2. ${\displaystyle (p,00111,Z)\vdash (p,0111,AZ)\vdash (q,0111,AZ)}$
      No es posible realizar más pasos.
   3. ${\displaystyle (p,00111,Z)\vdash (p,0111,AZ)\vdash (p,111,AAZ)\vdash (q,111,AAZ)\vdash (q,11,AZ)\vdash (q,1,Z)\vdash (r,1,Z)}$
      El estado final es de aceptación, pero la entrada no se acepta de esta manera porque no ha sido leída (completamente).

Lenguajes libres de contexto

Toda gramática libre de contexto puede transformarse en un autómata de derivación no determinista equivalente. El proceso de derivación de la gramática se simula de forma extrema izquierda. Cuando la gramática reescribe un no terminal, el PDA toma el no terminal superior de su pila y lo reemplaza por la parte derecha de una regla gramatical ( expand ). Cuando la gramática genera un símbolo terminal, el PDA lee un símbolo de la entrada cuando es el símbolo superior de la pila ( match ). En cierto sentido, la pila del PDA contiene los datos no procesados ​​de la gramática, correspondientes a un recorrido de preorden de un árbol de derivación.

Técnicamente, dada una gramática libre de contexto, la PDA tiene un solo estado, 1, y su relación de transición se construye de la siguiente manera.

1. ${\displaystyle (1,\varepsilon ,A,1,\alpha )}$para cada regla ( expandir ) ${\displaystyle A\to \alpha }$
2. ${\displaystyle (1,a,a,1,\varepsilon )}$para cada símbolo terminal ( coincidencia ) ${\displaystyle a}$

La PDA acepta por pila vacía. Su símbolo inicial de pila es el símbolo de inicio de la gramática. ^[3]

Para una gramática libre de contexto en forma normal de Greibach , definir (1,γ) ∈ δ(1, a , A ) para cada regla gramatical A → a γ también produce un autómata de empuje no determinista equivalente. ^{[2] : 115}

Lo inverso, encontrar una gramática para un PDA determinado, no es tan fácil. El truco consiste en codificar dos estados del PDA en los no terminales de la gramática.

Teorema. Para cada autómata de empuje se puede construir una gramática libre de contexto tal que . ^{[2] : 116} ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle N(M)=L(G)}$

El lenguaje de cadenas aceptado por un autómata de empuje determinista (DPDA) se denomina lenguaje determinista libre de contexto . No todos los lenguajes libres de contexto son deterministas. ^{[nota 1]} Como consecuencia, el DPDA es una variante estrictamente más débil del PDA. Incluso para los lenguajes regulares , existe un problema de explosión de tamaño: para cualquier función recursiva y para números enteros arbitrariamente grandes , existe un PDA de tamaño que describe un lenguaje regular cuyo DPDA más pequeño tiene al menos estados. ^[5] Para muchos PDA no regulares, cualquier DPDA equivalente requeriría un número ilimitado de estados. ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle f(n)}$

Un autómata finito con acceso a dos pilas es un dispositivo más potente, equivalente en potencia a una máquina de Turing . ^{[2] : 171} Un autómata lineal acotado es un dispositivo que es más potente que un autómata de empuje hacia abajo pero menos que una máquina de Turing. ^{[nota 2]}

Máquinas de Turing

Un autómata pushdown es computacionalmente equivalente a una máquina de Turing (TM) "restringida" con dos cintas que está restringida de la siguiente manera: en la primera cinta, la TM solo puede leer la entrada y moverse de izquierda a derecha (no puede hacer cambios). En la segunda cinta, solo puede "push" y "pop" datos. O equivalentemente, puede leer, escribir y moverse de izquierda a derecha con la restricción de que la única acción que puede realizar en cada paso es eliminar el carácter más a la izquierda en la cadena (pop) o agregar un carácter adicional a la izquierda del carácter más a la izquierda en la cadena (push).

El hecho de que una PDA sea más débil que una TM se puede achacar al hecho de que el procedimiento "pop" borra algunos datos. Para que una PDA sea tan fuerte como una TM, necesitamos guardar en algún lugar los datos perdidos a través del "pop". Podemos lograrlo introduciendo una segunda pila. En el modelo de TM de la PDA del párrafo anterior, esto es equivalente a una TM con 3 cintas, donde la primera cinta es la cinta de entrada de solo lectura, y la segunda y la tercera cintas son las cintas de "push and pop" (pila). Para que una PDA de este tipo simule una TM dada, damos la entrada de la PDA a la primera cinta, mientras mantenemos ambas pilas vacías. Luego pasa a empujar toda la entrada de la cinta de entrada a la primera pila. Cuando toda la entrada se transfiere a la primera pila, ahora procedemos como una TM normal, donde moverse hacia la derecha en la cinta es lo mismo que sacar un símbolo de la primera pila y empujar un símbolo (posiblemente actualizado) a la segunda pila, y moverse hacia la izquierda corresponde a sacar un símbolo de la segunda pila y empujar un símbolo (posiblemente actualizado) a la primera pila. Por lo tanto, tenemos una PDA con dos pilas que puede simular cualquier TM.

Generalización

Un autómata pushdown generalizado (GPDA) es un PDA que escribe una cadena completa de una longitud conocida en la pila o elimina una cadena entera de la pila en un solo paso.

Un GPDA se define formalmente como una tupla de 6:

${\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)}$

donde , y ⁠ ⁠ se definen de la misma manera que una PDA. ${\displaystyle Q,\Sigma \,,\Gamma \,,q_{0}}$ ${\displaystyle F}$

${\displaystyle \,\delta }$: ${\displaystyle Q\times \Sigma _{\epsilon }\times \Gamma ^{*}\longrightarrow P(Q\times \Gamma ^{*})}$

es la función de transición.

Las reglas de cálculo para un GPDA son las mismas que para un PDA, excepto que los ' y ' ahora son cadenas en lugar de símbolos. ${\displaystyle a_{i+1}}$ ${\displaystyle b_{i+1}}$

Los GPDA y los PDA son equivalentes en el sentido de que si un lenguaje es reconocido por un PDA, también lo es por un GPDA y viceversa.

Se puede formular una prueba analítica de la equivalencia de GPDA y PDA utilizando la siguiente simulación:

Sea una transición del GPDA ${\displaystyle \delta (q_{1},w,x_{1}x_{2}\cdot x_{m})\longrightarrow (q_{2},y_{1}y_{2}...y_{n})}$

dónde . ${\displaystyle q_{1},q_{2}\in Q,w\in \Sigma _{\epsilon },x_{1},x_{2},\ldots ,x_{m}\in \Gamma ^{*},m\geq 0,y_{1},y_{2},\ldots ,y_{n}\in \Gamma ^{*},n\geq 0}$

Construya las siguientes transiciones para la PDA:

${\displaystyle {\begin{array}{lcl}\delta '(q_{1},w,x_{1})&\longrightarrow &(p_{1},\epsilon )\\\delta '(p_{1},\epsilon ,x_{2})&\longrightarrow &(p_{2},\epsilon )\\&\vdots &\\\delta '(p_{m-1},\epsilon ,x_{m})&\longrightarrow &(p_{m},\epsilon )\\\delta '(p_{m},\epsilon ,\epsilon )&\longrightarrow &(p_{m+1},y_{n})\\\delta '(p_{m+1},\epsilon ,\epsilon )&\longrightarrow &(p_{m+2},y_{n-1})\\&\vdots &\\\delta '(p_{m+n-1},\epsilon ,\epsilon )&\longrightarrow &(q_{2},y_{1}).\end{array}}}$

Autómatas de pila

Como generalización de los autómatas de empuje hacia abajo, Ginsburg, Greibach y Harrison (1967) investigaron los autómatas de pila , que pueden además desplazarse hacia la izquierda o hacia la derecha en la cadena de entrada (rodeados de símbolos de marcador final especiales para evitar que se salgan), y hacia arriba o hacia abajo en la pila en modo de solo lectura. ^{[6] [7]} Un autómata de pila se denomina no borrable si nunca sale de la pila. La clase de lenguajes aceptados por los autómatas de pila no deterministas y no borrables es NSPACE ( n ² ), que es un superconjunto de los lenguajes sensibles al contexto . ^[1] La clase de lenguajes aceptados por los autómatas de pila deterministas y no borrables es DSPACE ( n ⋅log( n )). ^[1]

Autómatas de empuje alternado

Un autómata de empuje alterno (APDA) es un autómata de empuje con un conjunto de estados

• ${\displaystyle Q=Q_{\exists }\cup Q_{\forall }}$dónde . ${\displaystyle Q_{\exists }\cap Q_{\forall }=\emptyset }$

Los estados en y se denominan existenciales o universales . En un estado existencial, un APDA elige de manera no determinista el siguiente estado y lo acepta si al menos uno de los cálculos resultantes lo acepta. En un estado universal, el APDA se mueve a todos los siguientes estados y lo acepta si todos los cálculos resultantes lo aceptan. ${\displaystyle Q_{\exists }}$ ${\displaystyle Q_{\forall }}$

El modelo fue introducido por Chandra , Kozen y Stockmeyer . ^[8] Ladner , Lipton y Stockmeyer ^[9] demostraron que este modelo es equivalente a EXPTIME, es decir, un lenguaje es aceptado por algún APDA si, y solo si , puede decidirse mediante un algoritmo de tiempo exponencial.

Aizikowitz y Kaminski ^[10] introdujeron autómatas de empuje alternados sincronizados (SAPDA) que son equivalentes a las gramáticas conjuntivas de la misma manera que los PDA no deterministas son equivalentes a las gramáticas libres de contexto.

Véase también

• Gramática libre de contexto
• Autómata contador
• Máquina de estados finitos
• Autómata de cola
• Máquina apiladora

Notas

1. palíndromos de bits de longitud par no puede ser reconocido por un PDA determinista, pero es un lenguaje libre de contexto , con la gramática S → ε | 0 S 0 | 1 S 1. ^[4]
2. Los autómatas lineales acotados son aceptores de la clase de lenguajes sensibles al contexto, ^{[2] : 225} que es una superclase propia de los lenguajes libres de contexto, y una subclase propia de los lenguajes reconocibles por Turing (es decir, recursivamente enumerables ). ^{[2] : 228}

Referencias

1. John E. Hopcroft; Jeffrey D. Ullman (1967). "Autómatas de pila que no borran". Revista de Ciencias de la Computación y de Sistemas . 1 (2): 166–186. doi : 10.1016/s0022-0000(67)80013-8 .
2. John E. Hopcroft y Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación . Lectura/MA: Addison-Wesley. ISBN 0-201-02988-X.
3. "Autómatas de empuje hacia abajo". www.cs.odu.edu . Consultado el 7 de abril de 2024 .
4. John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). Introducción a la teoría de autómatas, lenguajes y computación . Addison Wesley.Aquí: Sect.6.4.3, p.249
5. Holzer, Markus; Kutrib, Martin (2019). "Las disyuntivas no recursivas están "casi en todas partes"". Computación con previsión e industria . 11558 : 25–36. doi :10.1007/978-3-030-22996-2_3.Esto se desprende de la cita [22, Proposición 7] y de la observación establecida de que cualquier autómata de empuje determinista se puede convertir en un autómata finito equivalente ^{[ aclarar ]} de tamaño doblemente exponencial como máximo.
6. Seymour Ginsburg, Sheila A. Greibach y Michael A. Harrison (1967). "Autómatas de pila y compilación". J. ACM . 14 (1): 172–201. doi : 10.1145/321371.321385 .
7. Seymour Ginsburg, Sheila A. Greibach y Michael A. Harrison (1967). "Autómatas de pila unidireccional". J. ACM . 14 (2): 389–418. doi : 10.1145/321386.321403 .
8. Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternancia". Revista de la ACM . 28 (1): 114–133. doi : 10.1145/322234.322243 . ISSN  0004-5411.
9. Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. (1984). "Autómatas de pila y pushdown alternos". Revista SIAM de informática . 13 (1): 135–155. doi :10.1137/0213010. ISSN  0097-5397.
10. Aizikowitz, Tamar; Kaminski, Michael (2011). "Gramáticas conjuntivas LR(0) y autómatas de empuje alternado sincronizado determinista". Ciencias de la computación: teoría y aplicaciones . Apuntes de clase en ciencias de la computación. Vol. 6651. págs. 345–358. doi :10.1007/978-3-642-20712-9_27. ISBN 978-3-642-20711-2. ISSN  0302-9743.

• Michael Sipser (1997). Introducción a la teoría de la computación . PWS Publishing. ISBN 0-534-94728-X.Sección 2.2: Autómatas Pushdown, págs. 101–114.
• Jean-Michel Autebert, Jean Berstel, Luc Boasson, Lenguajes libres de contexto y autómatas push-down, en: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, 1997, 111–174.

Enlaces externos

• JFLAP, simulador para varios tipos de autómatas, incluidos los autómatas de empuje no deterministas
• CoAn, otro simulador para varios tipos de máquinas, incluidos autómatas pushdown no deterministas (C++, Windows, Linux, MacOS)