Autómata de pila determinista

En la teoría de autómatas , un autómata de pila determinista ( DPDA o DPA ) es una variación del autómata de pila . La clase de autómatas de pila deterministas acepta los lenguajes libres de contexto deterministas , un subconjunto propio de los lenguajes libres de contexto . ^{[ 1 ]}

Las transiciones de la máquina se basan en el estado actual y el símbolo de entrada, así como en el símbolo superior actual de la pila. Los símbolos inferiores de la pila no son visibles y no tienen efecto inmediato. Las acciones de la máquina incluyen insertar, extraer o reemplazar el elemento superior de la pila. Un autómata de pila determinista tiene como máximo una transición válida para la misma combinación de símbolo de entrada, estado y símbolo superior de la pila. Aquí radica su diferencia con el autómata de pila no determinista.

Un generador de números de pila (no necesariamente determinista)${\displaystyle M}$se puede definir como una 7-tupla:

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

dónde

• ${\displaystyle Q\,}$es un conjunto finito de estados
• ${\displaystyle \Sigma \,}$es un conjunto finito de símbolos de entrada
• ${\displaystyle \Gamma \,}$es un conjunto finito de símbolos de pila
• ${\displaystyle q_{0}\,\in Q\,}$es el estado inicial
• ${\displaystyle Z_{0}\,\en \Gamma \,}$es el símbolo de pila inicial
• ${\displaystyle A\,\subsetequ Q\,}$, dónde${\displaystyle A}$es el conjunto de estados de aceptación o finales
• ${\displaystyle \delta \,}$es una función de transición, donde

${\displaystyle \delta \colon (Q\,\times (\Sigma \,\cup \left\{\varepsilon \,\right\})\times \Gamma \,)\longrightarrow {\mathcal {P}}(Q\times \Gamma ^{*})}$

dónde${\displaystyle *}$es la estrella de Kleene , lo que significa que${\displaystyle \Gamma ^{*}}$es "el conjunto de todas las cadenas finitas (incluida la cadena vacía)${\displaystyle \varepsilon }$) de elementos de${\displaystyle \Gamma }$",${\displaystyle \varepsilon }$denota la cadena vacía y${\displaystyle {\mathcal {P}}(X)}$es el conjunto potencia de un conjunto${\displaystyle X}$.

M es determinista si satisface las dos condiciones siguientes:

• Para cualquier${\displaystyle q\in Q,a\in \Sigma \cup \left\{\varepsilon \right\},x\in \Gamma }$, el conjunto${\displaystyle \delta (q,a,x)\,}$tiene como máximo un elemento.
• Para cualquier${\displaystyle q\in Q,x\in \Gamma }$, si${\displaystyle \delta (q,\varepsilon ,x)\not =\emptyset \,}$, entonces${\displaystyle \delta \left(q,a,x\right)=\emptyset }$por cada${\displaystyle a\in \Sigma .}$

Existen dos criterios de aceptación posibles: aceptación por pila vacía y aceptación por estado final . Ambos no son equivalentes para el autómata de pila determinista (aunque sí lo son para el autómata de pila no determinista). Los lenguajes aceptados por pila vacía son aquellos que son aceptados por estado final y no contienen prefijos: ninguna palabra del lenguaje es prefijo de otra palabra del mismo lenguaje. ^{[ 2 ] [ 3 ]}

El criterio de aceptación habitual es el estado final , y es este criterio de aceptación el que se utiliza para definir los lenguajes deterministas libres de contexto .

Si${\displaystyle L(A)}$es un idioma aceptado por un PDA${\displaystyle A}$, también puede ser aceptado por un DPDA si y solo si hay un único cálculo desde la configuración inicial hasta uno que acepte para todas las cadenas pertenecientes a${\displaystyle L(A)}$. Si${\displaystyle L(A)}$Si un autómata de pila (AP) puede aceptarlo, es un lenguaje libre de contexto, y si un autómata de pila determinista (APD) puede aceptarlo, es un lenguaje libre de contexto determinista (LCPD).

No todos los lenguajes libres de contexto son deterministas. Esto hace que el DPDA sea un dispositivo estrictamente más débil que el PDA. Por ejemplo, el lenguaje L _{p de} palíndromos de longitud par en el alfabeto de 0 y 1 tiene la gramática libre de contexto S → 0S0 | 1S1 | ε. Si existe un DPDA para este lenguaje y ve una cadena 0 ⁿ , debe usar su pila para memorizar la longitud n , para poder distinguir sus posibles continuaciones 0 ⁿ 11 0 ⁿ ∈ L _p y 0 ⁿ 11 0 ^{n +2} ∉ L _p . Por lo tanto, después de leer 0 ⁿ 11 0 ⁿ , comparar la longitud posterior a "11" con la longitud anterior a "11" hará que la pila vuelva a estar vacía. Por esta razón, las cadenas 0 ⁿ 11 0 ⁿ 0 ⁿ 11 0 ⁿ ∈ L _p y 0 ⁿ 11 0 ⁿ 0 ^{n +2} 11 0 ^{n +2} ∉ L _p no se pueden distinguir. ^{[ 4 ]}

Restringir el DPDA a un solo estado reduce la clase de lenguajes aceptados a los lenguajes LL(1) ^{[ 5 ]} , que es una subclase propia del DCFL ^{[ 6 ]} . En el caso de un PDA, esta restricción no tiene efecto sobre la clase de lenguajes aceptados.

• Hamburger, Henry; Dana S. Richards (2002). Modelos lógicos y lingüísticos para la informática . Upper Saddle River, NJ 07458: Prentice Hall. pp. 284–331 . ISBN  0-13-065487-6.{{cite book}}: CS1 mantenimiento: ubicación ( enlace )