Autómata de empuje determinista

En la teoría de autómatas , un autómata determinista de tipo pushdown ( DPDA o DPA ) es una variación del autómata de tipo pushdown . La clase de autómatas deterministas de tipo pushdown acepta los lenguajes deterministas libres de contexto , 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, y también en el símbolo superior actual de la pila. Los símbolos que se encuentran en la parte inferior de la pila no son visibles y no tienen un efecto inmediato. Las acciones de la máquina incluyen empujar, sacar o reemplazar la parte superior de la pila. Un autómata de empuje hacia abajo determinista tiene como máximo una transición legal para la misma combinación de símbolo de entrada, estado y símbolo superior de la pila. Aquí es donde se diferencia del autómata de empuje hacia abajo no determinista.

Definición formal

Una PDA (no necesariamente determinista) se puede definir como una tupla de 7: ${\displaystyle M}$

${\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}\,\in \Gamma \,}$es el símbolo de la pila inicial
• ${\displaystyle A\,\subseteq Q\,}$, donde es el conjunto de estados de aceptación o finales ${\displaystyle A}$
• ${\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 ^{*})}$

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

M es determinista si satisface ambas condiciones siguientes:

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

Existen dos posibles criterios de aceptación: aceptación por pila vacía y aceptación por estado final . Los dos no son equivalentes para el autómata de empuje determinista (aunque sí lo son para el autómata de empuje no determinista). Los idiomas aceptados por pila vacía son aquellos idiomas que son aceptados por estado final y no tienen prefijo: ninguna palabra en el idioma es el prefijo de otra palabra en el idioma. ^{[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 .

Idiomas reconocidos

Si es un lenguaje aceptado por una PDA , también puede ser aceptado por una DPDA si y solo si hay un único cálculo desde la configuración inicial hasta uno que lo acepte para todas las cadenas que pertenecen a . Si puede ser aceptado por una PDA, es un lenguaje libre de contexto y si puede ser aceptado por una DPDA, es un lenguaje libre de contexto determinista (DCFL). ${\displaystyle L(A)}$ ${\displaystyle A}$ ${\displaystyle L(A)}$ ${\displaystyle L(A)}$

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 idiomas aceptados a los idiomas 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 idiomas aceptados.

Propiedades

Cierre

Las propiedades de clausura de los lenguajes deterministas libres de contexto (aceptados por PDA deterministas por estado final) son drásticamente diferentes de las de los lenguajes libres de contexto. Por ejemplo, son (efectivamente) cerrados bajo complementación, pero no cerrados bajo unión. Probar que el complemento de un lenguaje aceptado por un PDA determinista también lo es por un PDA determinista es complicado porque hay que evitar cálculos infinitos y manejar correctamente las transiciones que manipulan la pila sin leer los símbolos de entrada. ^[7]

Como consecuencia de la complementación, es posible decidir si un PDA determinista acepta todas las palabras de su alfabeto de entrada, comprobando si su complemento está vacío. Esto no es posible para gramáticas independientes del contexto (y, por lo tanto, no es posible para PDA general).

Problema de equivalencia

Géraud Sénizergues (1997) demostró que el problema de equivalencia para PDA determinista (es decir, dadas dos PDA deterministas A y B, ¿es L(A)=L(B)?) es decidible, ^{[8] [9] [10]} una prueba que le valió el Premio Gödel 2002. Para PDA no determinista, la equivalencia es indecidible.

Notas

1. Michael Sipser (1997). Introducción a la teoría de la computación . PWS Publishing. pág. 102. ISBN. 0-534-94728-X.
2. Soltys-kulinicz, Michael (2018). Introducción al análisis de algoritmos (3.ª ed.). World Scientific. pp. 193, 195. ISBN 9789813235922.
3. Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006). Introducción a la teoría de autómatas, lenguajes y computación (3.ª ed.). Addison-Wesley. págs. 234, 254. ISBN 0-321-45536-3.
4. Hopcroft, John ; Rajeev Motwani ; Jeffrey Ullman (2001). Introducción a la teoría de autómatas, lenguajes y computación (2.ª ed.). Addison-Wesley. págs. 249–253.
5. Kurki-Suonio, R. (1969). "Notas sobre lenguajes de arriba hacia abajo". BIT . 9 (3): 225–238. doi :10.1007/BF01946814. S2CID  60912010.
6. Rosenkrantz, DJ; Stearns, RE (1970). "Propiedades de las gramáticas deterministas de arriba hacia abajo". Información y control . 17 (3): 226–256. doi : 10.1016/s0019-9958(70)90446-8 .Aquí: p.246–247
7. Hopcroft, John E.; Ullman, Jeffrey D. (1969-01-01), "Autómatas deterministas de tipo pushdown", Lenguajes formales y su relación con los autómatas , EE. UU.: Addison-Wesley Longman Publishing Co., Inc. , consultado el 29 de mayo de 2024
8. Sénizergues, Géraud (1997). "El problema de equivalencia para autómatas deterministas de tipo pushdown es decidible". Proc. Int. Coll. on Automata, Languages, and Programming (ICALP) . Apuntes de clase en informática . Vol. 1256. págs. 671–681. doi :10.1007/3-540-63165-8_221. ISBN 978-3-540-63165-1.— Versión completa: Géraud Sénizergues (1997). L(A) = L(B)? (Informe Técnico 1161-97). Universidad de Burdeos, LaBRI.
9. Géraud Sénizergues (2001). "Estudio fundamental: L ( A ) = L ( B )? resultados de decidibilidad a partir de sistemas formales completos". Ciencias de la Computación Teórica . 251 (1–2): 1–166. doi :10.1016/S0304-3975(00)00285-1.
10. Géraud Sénizergues (2002). "L(A) = L(B)? Una prueba de decidibilidad simplificada". Ciencias Informáticas Teóricas . 281 (1–2): 555–608. doi : 10.1016/S0304-3975(02)00027-0 .

Lectura adicional

• Hamburger, Henry; Dana S. Richards (2002). Modelos lógicos y de lenguaje para la informática. Upper Saddle River, NJ 07458: Prentice Hall. pp. 284–331. ISBN 0-13-065487-6.{{cite book}}: CS1 maint: location (link)