autómata de empuje

Clases de autómatas

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

Los autómatas de pila se utilizan en teorías sobre qué 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 de pila deterministas pueden reconocer todos los lenguajes libres de contexto deterministas, 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 "apilamiento" 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 funcionan con elementos que no sean el elemento superior. Un autómata de pila , por el contrario, permite el acceso y las operaciones con elementos más profundos. Los autómatas de pila pueden reconocer un conjunto de lenguajes estrictamente mayor que los autómatas de apilamiento. ^{[ 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.

Una máquina de estados finitos solo considera la señal de entrada y el estado actual: no tiene 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 pila (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 pila lee una cadena de entrada de izquierda a derecha. En cada paso, elige una transición consultando una tabla según el símbolo de entrada, el estado actual y el símbolo en la parte superior de la pila. Un autómata de pila también puede manipular la pila como parte de la transición. Esta manipulación puede consistir en insertar un símbolo específico en la parte superior de la pila o extraerlo de ella. Alternativamente, el autómata puede ignorar la pila y dejarla sin modificar.

En resumen: dado un símbolo de entrada, el estado actual y un símbolo de la pila, el autómata puede seguir una transición a otro estado y, opcionalmente, manipular (insertar o extraer) la pila.

Si, en cada situación, es posible como máximo una acción de transición, entonces el autómata se denomina autómata de pila determinista (DPDA) . En general, si son posibles varias acciones, entonces el autómata se denomina autómata de pila general o no determinista ( PDA ). Una cadena de entrada dada puede llevar a un autómata de pila 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 .

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

Un PDA se define formalmente como una 7-tupla:

${\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 denomina alfabeto de entrada
• ${\displaystyle \Gamma }$es un conjunto finito que se llama alfabeto de pila
• ${\displaystyle \delta }$es un subconjunto finito de${\displaystyle Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}}$, la relación de transición
• ${\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${\displaystyle (p,a,A,q,\alpha )\in \delta }$es una transición de${\displaystyle M}$Tiene el significado previsto de que${\displaystyle M}$, en el estado${\displaystyle p\in Q}$, en la entrada${\displaystyle a\in \Sigma \cup \{\varepsilon \}}$y con${\displaystyle A\in \Gamma }$como símbolo de pila superior, puede leer${\displaystyle a}$, cambiar el estado a${\displaystyle q}$, estallido${\displaystyle A}$, reemplazándolo empujando${\displaystyle \alpha \in \Gamma ^{*}}$. El${\displaystyle (\Sigma \cup \{\varepsilon \})}$El componente de la relación de transición se utiliza para formalizar que el autómata de pila puede leer una letra de la entrada o continuar sin modificar la entrada.

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

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

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

Cálculos

Para formalizar la semántica del autómata de pila, se introduce una descripción de la situación actual. Cualquier 3-tupla${\displaystyle (p,w,\beta )\in Q\times \Sigma ^{*}\times \Gamma ^{*}}$se denomina descripción instantánea (ID) de${\displaystyle M}$, 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${\displaystyle \delta }$define la relación de pasos${\displaystyle \vdash _{M}}$de${\displaystyle M}$sobre descripciones instantáneas. Para instrucciones${\displaystyle (p,a,A,q,\alpha )\in \delta }$existe un paso${\displaystyle (p,ax,A\gamma )\vdash _{M}(q,x,\alpha \gamma )}$, por cada${\displaystyle x\in \Sigma ^{*}}$y cada${\displaystyle \gamma \in \Gamma ^{*}}$.

En general, los autómatas de pila son no deterministas, lo que significa que en una descripción instantánea dada${\displaystyle (p,w,\beta )}$Existen 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 único símbolo (el de la parte superior de la pila) y se reemplaza con tantos símbolos como sean necesarios. En consecuencia, no se define ningún paso cuando la pila está vacía.

Los cálculos del autómata de pila son secuencias de pasos. El cálculo comienza en el estado inicial.${\displaystyle q_{0}}$con el símbolo de pila inicial${\displaystyle Z}$en la pila y una cadena${\displaystyle w}$en la cinta de entrada, por lo tanto, con la descripción inicial${\displaystyle (q_{0},w,Z)}$.

Hay dos modos de aceptación. El autómata de pila acepta por estado final, lo que significa que después de leer su entrada el autómata alcanza un estado de aceptación (en${\displaystyle F}$), o bien acepta por pila vacía (${\displaystyle \varepsilon }$), 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).

Formalmente se define

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

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

Para cada autómata de pila, estos dos lenguajes no tienen por qué estar relacionados; pueden ser iguales, pero generalmente no es así. La especificación del autómata también debe incluir el modo de aceptación previsto. Considerando todos los autómatas de pila, ambas condiciones de aceptación definen la misma familia de lenguajes.

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

A continuación se presenta la descripción formal del PDA que reconoce el lenguaje.${\displaystyle \{0^{n}1^{n}\mid n\geq 0\}}$por estado final:

${\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 de inicio: Z
• Estados que aceptan:${\displaystyle F=\{r\}}$

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

${\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 , se inserta una A en la pila. Insertar el símbolo A encima de otra A se formaliza como reemplazar la A superior por AA (y de forma similar para insertar 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 indica que la máquina solo puede pasar del estado q al estado de aceptación r cuando Z es el símbolo superior de la pila. En este autómata de pila, esto equivale a que la pila contenga una sola Z , ya que Z se utiliza únicamente como marcador de la parte inferior de la pila y ninguna transición coloca otra Z encima de ella.

Parece que no existe una representación de uso general para PDA. Aquí hemos representado la instrucción.${\displaystyle (p,a,A,q,\alpha )}$por una arista del estado p al estado q etiquetada por ${\displaystyle a;A/\alpha }$(leer a de la cadena de entrada; reemplazar A en la parte superior de la pila por${\displaystyle \alpha }$).

Explicación

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

1. Cadena de entrada = 0011. Existen varios cálculos, dependiendo del momento en que se realiza el cambio 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 de aceptación, pero la entrada no se acepta de esta manera ya que no se ha leído.
   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)}$Cálculo de aceptación: finaliza en estado de aceptación, una vez que se ha leído la entrada completa.
2. Cadena de entrada = 00111. Nuevamente se realizan varios cálculos. Ninguno de ellos es válido.
   1. ${\displaystyle (p,00111,Z)\vdash (q,00111,Z)\vdash (r,00111,Z)}$El estado final es de aceptación, pero la entrada no se acepta de esta manera ya que no se ha leído.
   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 ya que no se ha leído (completamente).

Toda gramática libre de contexto puede transformarse en un autómata de pila no determinista equivalente. El proceso de derivación de la gramática se simula de izquierda a derecha. Cuando la gramática reescribe un no terminal, el autómata de pila 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, el autómata de pila lee un símbolo de la entrada cuando este es el símbolo superior de la pila ( coincidir ). En cierto modo, la pila del autómata de pila contiene los datos sin procesar de la gramática, que corresponden a un recorrido en preorden de un árbol de derivación.

Técnicamente, dada una gramática libre de contexto, el autómata de pila tiene un único 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${\displaystyle A\to \alpha }$( expandir )
2. ${\displaystyle (1,a,a,1,\varepsilon )}$para cada símbolo terminal${\displaystyle a}$( fósforo )

El 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 de pila no determinista equivalente. ^{[ 4 ]}

Lo contrario, encontrar una gramática para un autómata de pila dado, no es tan fácil. El truco consiste en codificar dos estados del autómata de pila en los no terminales de la gramática.

Teorema. Para cada autómata de pila${\displaystyle M}$Se puede construir una gramática libre de contexto.${\displaystyle G}$de tal manera que${\displaystyle N(M)=L(G)}$. ^{[ 5 ]}

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

Un autómata finito con acceso a dos pilas es un dispositivo más potente, equivalente en potencia a una máquina de Turing . ^{[ 8 ]} Un autómata lineal acotado es un dispositivo más potente que un autómata de pila pero menos potente que una máquina de Turing. ^{[ c ]}

Un autómata de pila es computacionalmente equivalente a una máquina de Turing (MT) "restringida" con dos cintas, la cual está restringida de la siguiente manera: en la primera cinta, la MT solo puede leer la entrada y moverse de izquierda a derecha (es decir, no puede realizar cambios). En la segunda cinta, solo puede "insertar" y "extraer" datos; es decir, la MT puede leer, escribir y moverse de izquierda a derecha en la segunda cinta, 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 (extraer) o agregar un carácter adicional a la izquierda del carácter más a la izquierda de la cadena (insertar).

Que un autómata de pila (AP) sea más débil que una máquina de Turing (MT) se reduce a que el procedimiento de "eliminación" borra algunos datos. Para que un AP sea tan robusto como una MT, necesitamos almacenar estos datos perdidos en algún lugar; esto se logra introduciendo una segunda pila. En el modelo de MT de autómatas de pila mencionado anteriormente, esto equivale a una MT con tres cintas, donde la primera es la cinta de entrada de solo lectura, y la segunda y la tercera son cintas de "inserción" y "eliminación" (pila). Para que un AP de este tipo simule una MT dada, se le proporciona la entrada al AP en la primera cinta, manteniendo ambas pilas vacías; luego, el AP inserta toda la entrada de la cinta de entrada en la primera pila. Cuando toda la entrada se transfiere a la primera pila, la operación procede como en una máquina de Turing normal: moverse a la derecha en la cinta es lo mismo que extraer un símbolo de la primera pila y colocar un símbolo (posiblemente actualizado) en la segunda pila, y moverse a la izquierda corresponde a extraer un símbolo de la segunda pila y colocar un símbolo (posiblemente actualizado) en la primera pila; por lo tanto, ahora tenemos un autómata de pila de dos pilas que puede simular cualquier máquina de Turing.

Un autómata de pila generalizado (GPDA, por sus siglas en inglés) es un autómata de pila que escribe una cadena completa de longitud conocida en la pila o elimina una cadena completa de la pila en un solo paso.

Un GPDA se define formalmente como una 6-tupla:

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

dónde${\displaystyle Q,\Sigma \,,\Gamma \,,q_{0}}$y​${\displaystyle F}$Se definen de la misma manera que una PDA.

${\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${\displaystyle a_{i+1}}$'arena${\displaystyle b_{i+1}}$Ahora son cadenas de caracteres en lugar de símbolos.

Los autómatas de pila y los autómatas de pila generalizados son equivalentes en el sentido de que si un lenguaje es reconocido por un autómata de pila, también lo es por un autómata de pila generalizado, y viceversa.

Se puede formular una demostración analítica de la equivalencia entre autómatas de pila y autómatas de pila generalizados utilizando la siguiente simulación:

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

${\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}$

Construye 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}}}$

Como generalización de los autómatas de pila, Ginsburg, Greibach y Harrison (1967) investigaron los autómatas de pila , que pueden además avanzar a la izquierda o a la derecha en la cadena de entrada (rodeada de símbolos de marcador de fin especiales para evitar salirse), y avanzar hacia arriba o hacia abajo en la pila en modo de solo lectura. ^{[ 11 ] [ 12 ]} Un autómata de pila se llama no borrador si nunca se extrae de la pila. La clase de lenguajes aceptados por los autómatas de pila no deterministas y no borradores 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 borradores es DSPACE ( n ⋅log( n )). ^{[ 1 ]}

Un autómata de pila alternante (APDA) es un autómata de pila con un conjunto de estados.

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

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

El modelo fue introducido por Chandra , Kozen y Stockmeyer . ^{[ 13 ]} Ladner , Lipton y Stockmeyer ^{[ 14 ]} demostraron que este modelo es equivalente a EXPTIME , es decir, un lenguaje es aceptado por algún APDA si, y solo si , puede ser decidido por un algoritmo de tiempo exponencial.

Aizikowitz y Kaminski ^{[ 15 ]} introdujeron autómatas de pila alternantes 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.

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