autómata de empuje

tipo de autómata

clases de autómatas

En la teoría de la computación , una rama de la 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 las máquinas pueden calcular. Son más capaces que las máquinas de estados finitos pero menos capaces que las máquinas de Turing (ver 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 , y los primeros se utilizan a menudo en el diseño de analizadores .

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

descripción informal

Un diagrama de un autómata pushdown.

Una máquina de estados finitos simplemente mira 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 los valores anteriores de la entrada. Sólo puede elegir un nuevo estado, resultado de seguir la transición. Un autómata pushdown (PDA) se diferencia de una máquina de estados finitos en dos formas:

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

Un autómata pushdown lee una cadena de entrada determinada 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 pushdown también puede manipular la pila, como parte de la realización de una transición. La manipulación puede ser empujar un símbolo particular a la parte superior de la pila o sacarlo de la parte superior de la pila. Alternativamente, el autómata puede ignorar la pila y dejarla como está.

En conjunto: dado 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 hacer estallar) la pila.

Si, en cada situación, como máximo una de esas acciones de transición es posible, entonces el autómata se denomina autómata determinista de empuje (DPDA) . En general, si son posibles varias acciones, entonces el autómata se denomina PDA general o no determinista . Una cadena de entrada determinada puede impulsar un autómata pushdown no determinista a una de varias secuencias de configuración; si uno de ellos 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 .

Definicion formal

Usamos notación de 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 inicial de la pila
• ${\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 leerse , cambiar el estado a pop , reemplazándolo presionando . El componente de la relación de transición se utiliza para formalizar que la PDA puede leer una carta de la entrada o continuar dejando la entrada intacta. ^{[ cita necesaria ]} ${\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 , mapeando en subconjuntos finitos de ${\displaystyle Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma }$ ${\displaystyle Q\times \Gamma ^{*}}$

Aquí contiene todas las acciones posibles en el estado de la pila, mientras se lee la entrada. Se escribe por ejemplo precisamente cuando porque . Tenga en cuenta que lo 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 tupla triple 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 se escribe primero). La relación de transición define la relación escalonada de descripciones instantáneas. Para la instrucción existe un paso , para todos y cada uno . ${\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 pushdown no son deterministas, lo que significa que en una descripción instantánea dada puede haber varios pasos posibles. Cualquiera de estos pasos se puede elegir en un cálculo. Con la definición anterior, en cada paso siempre aparece un solo símbolo (parte superior de la pila), reemplazándolo con tantos símbolos como sea necesario. Como consecuencia, no se define ningún paso cuando la pila está vacía. ${\displaystyle (p,w,\beta )}$

Los cálculos del autómata de empuje 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 la descripción inicial . Hay dos modos de aceptar. 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í se 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 pushdown, estos dos lenguajes no necesitan tener relación: pueden ser iguales, pero normalmente este no es el caso. Una especificación del autómata también debería incluir el modo de aceptación previsto. Asumidas en todos los autómatas 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 idioma 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 de aceptación: ${\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 cualquier momento en que el símboloSe lee 0 , se empuja una A a la pila. Empujar el símbolo A encima de otro A se formaliza como reemplazar la parte superior A por AA (y de manera similar para empujar el símbolo A encima de una 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, una A aparece.

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

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

Explicación

aceptar el cálculo para0011

A continuación se ilustra cómo el PDA anterior calcula en diferentes cadenas de entrada. Aquí se omite el subíndice M del símbolo de paso . ${\displaystyle \vdash }$

1. Cadena de entrada = 0011. Hay varios cálculos, dependiendo del momento en que se realiza el paso del estado p al estado q . Sólo uno de ellos acepta.
   1. ${\displaystyle (p,0011,Z)\vdash (q,0011,Z)\vdash (r,0011,Z)}$
      El estado final es aceptar, 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)}$
      Aceptación del cálculo: finaliza en el estado de aceptación, mientras se ha leído la entrada completa.
2. Cadena de entrada = 00111. Nuevamente hay varios cálculos. Ninguno de estos acepta.
   1. ${\displaystyle (p,00111,Z)\vdash (q,00111,Z)\vdash (r,00111,Z)}$
      El estado final es aceptar, 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 aceptar, pero la entrada no se acepta de esta manera porque no ha sido leída (completamente).

Idiomas libres de contexto

Cada gramática libre de contexto se puede transformar en un autómata pushdown no determinista equivalente. El proceso de derivación de la gramática se simula en el extremo izquierdo. Cuando la gramática reescribe un no terminal, la PDA toma el no terminal superior de su pila y lo reemplaza por la parte derecha de una regla gramatical ( expandir ). Cuando la gramática genera un símbolo terminal, la PDA lee un símbolo de la entrada cuando es el símbolo más alto de la pila ( coincidencia ). 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, el 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 de terminal ( coincidencia ) ${\displaystyle a}$

La PDA acepta por pila vacía. Su símbolo de pila inicial 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 pushdown no determinista equivalente. ^{[2] : 115}

Lo contrario, encontrar una gramática para una PDA determinada, 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 pushdown 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 pushdown determinista (DPDA) se denomina lenguaje determinista libre de contexto . No todos los lenguajes libres de contexto son deterministas. ^{[nota 1]} Como consecuencia, la DPDA es una variante estrictamente más débil de la 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 muchas 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 delimitado es un dispositivo que es más potente que un autómata de empuje 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 realizar cambios). ). En la segunda cinta, sólo puede "enviar" y "explotar" datos. O de manera equivalente, puede leer, escribir y moverse hacia la izquierda y hacia la 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 de la cadena (pop) o agregar un carácter adicional a la izquierda. -la mayoría de los caracteres de la cadena (push).

El hecho de que una PDA sea más débil que una TM puede deberse al hecho de que el procedimiento "pop" elimina algunos datos. Para hacer una PDA tan fuerte como una TM, necesitamos guardar en algún lugar los datos perdidos a través del 'pop'. Podemos lograr esto introduciendo una segunda pila. En el modelo TM de PDA del último párrafo, esto equivale a un TM con 3 cintas, donde la primera cinta es la cinta de entrada de sólo lectura, y la segunda y tercera cintas son las cintas 'push and pop' (apiladas). . Para que una PDA de este tipo simule cualquier TM determinada, le damos la entrada de la PDA a la primera cinta, mientras mantenemos ambas pilas vacías. Luego pasa 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 MT 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 tanto tenemos una PDA con 2 pilas que puede simular cualquier TM.

Generalización

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

Una 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 las de un PDA excepto que los 's' y 's ahora son cadenas en lugar de símbolos. ${\displaystyle a_{i+1}}$ ${\displaystyle b_{i+1}}$

Los GPDA y PDA son equivalentes en el sentido de que si un idioma es reconocido por un PDA, también lo será 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 de la 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 el 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 una generalización de los autómatas pushdown, Ginsburg, Greibach y Harrison (1967) investigaron los autómatas de pila , que además pueden avanzar hacia la izquierda o hacia la derecha en la cadena de entrada (rodeados de símbolos de marca final especiales para evitar que se salgan) y subir o bajar en la cadena. apilar en modo de solo lectura. ^{[6] [7]} Un autómata de pila se llama no borrable si nunca sale de la pila. La clase de lenguajes aceptados por los autómatas de pila no deterministas y que no se borran es NSPACE ( n ² ), que es un superconjunto de lenguajes sensibles al contexto . ^[1] La clase de lenguajes aceptados por los autómatas de pila deterministas que no se borran es DSPACE ( n ⋅log ( n )). ^[1]

Autómatas de empuje alterno

Un autómata de empuje alterno (APDA) es un autómata de empuje con un estado establecido

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

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

El modelo fue presentado 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 alguna APDA si, y sólo si , puede decidirse mediante un algoritmo de tiempo exponencial.

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

Ver también

• Gramática libre de contexto
• contador autómata
• 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 una 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 aceptan la clase de lenguajes sensibles al contexto, ^{[2] : 225,} que es una superclase adecuada de los lenguajes libres de contexto y una subclase adecuada de los lenguajes reconocibles por Turing (es decir, enumerables recursivamente ). ^{[2] : 228}

Referencias

1. John E. Hopcroft; Jeffrey D. Ullman (1967). "Autómatas de pila que no se 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, los lenguajes y la computación de autómatas . Lectura/MA: Addison-Wesley. ISBN 0-201-02988-X.
3. "Autómatas de empuje". 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, los lenguajes y la computación de autómatas . Addison Wesley.Aquí: Sección 6.4.3, p.249
5. Holzer, Markus; Kutrib, Martín (2019). "Las compensaciones no recursivas están" en casi 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 [22, Proposición 7] citada y de la observación declarada de que cualquier autómata de empuje determinista puede convertirse en un autómata finito equivalente ^{[ aclarar ]} de tamaño doble exponencial como máximo.
6. Seymour Ginsburg, Sheila A. Greibach y Michael A. Harrison (1967). "Apilar autómatas y compilar". 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). "Alternancia de pushdown y apilamiento de autómatas". Revista SIAM de Computación . 13 (1): 135-155. doi :10.1137/0213010. ISSN  0097-5397.
10. Aizikowitz, Tamar; Kaminski, Michael (2011). "LR (0) Gramáticas conjuntivas y autómatas pushdown alternos sincronizados deterministas". Informática: teoría y aplicaciones . Apuntes de conferencias sobre informática. 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 . Publicación PWS. ISBN 0-534-94728-X.Sección 2.2: Autómatas de empuje, 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.), Manual de lenguajes formales, vol. 1, Springer-Verlag, 1997, 111-174.

enlaces externos

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