Autómata de empuje determinista

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

Definicion 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\,}$, ¿dónde está el conjunto de estados aceptantes 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 las dos condiciones siguientes:

• Para cualquiera , 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 cualquiera , 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 .}$

Hay dos criterios de aceptación posibles: 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 lo son para el autómata de empuje no determinista). Los idiomas aceptados por pila vacía son aquellos idiomas que se aceptan por estado final y no tienen prefijos: 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 sólo si hay un único cómputo desde la configuración inicial hasta una de aceptación para todas las cadenas que pertenecen . Si puede ser aceptado por una PDA, es un lenguaje libre de contexto y si puede ser aceptado por una DPDA, es un lenguaje determinista libre de contexto (DCFL). ${\displaystyle L(A)}$ ${\displaystyle A}$ ${\displaystyle L(A)}$ ${\displaystyle L(A)}$

No todos los lenguajes libres de contexto son deterministas. Esto convierte al DPDA en 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 ^{norte +2} ∉ L _pags . 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 se vacíe nuevamente. 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 la DPDA a un solo estado reduce la clase de idiomas aceptados a los idiomas LL(1) , ^[5] que es una subclase propia de la DCFL. ^[6] En el caso de una PDA, esta restricción no tiene ningún efecto sobre la clase de idiomas aceptados.

Propiedades

Cierre

Las propiedades de cierre de los lenguajes deterministas libres de contexto (aceptadas por PDA determinista por estado final) son drásticamente diferentes de las de los lenguajes libres de contexto. Por ejemplo, están (efectivamente) cerrados bajo complementación, pero no cerrados bajo unión. Demostrar que el complemento de un lenguaje aceptado por una PDA determinista también lo es por una 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, se puede decidir si una 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 libres de contexto (por lo tanto, no para PDA general).

problema de equivalencia

Géraud Sénizergues (1997) demostró que el problema de equivalencia para PDA deterministas (es decir, dados dos PDA deterministas A y B, ¿L(A)=L(B)?) es decidible, ^{[8] [9] [10]} una prueba de 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 . Publicación PWS. pag. 102.ISBN​ 0-534-94728-X.
2. Soltys-kulinicz, Michael (2018). Introducción al análisis de algoritmos (3ª ed.). Científico mundial. págs.193, 195. ISBN 9789813235922.
3. Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006). Introducción a la teoría, los lenguajes y la computación de los autómatas (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, los lenguajes y la computación de los autómatas (2 ed.). Addison-Wesley. págs. 249-253.
5. Kurki-Suonio, R. (1969). "Notas sobre idiomas de arriba hacia abajo". POCO . 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áginas 246–247
7. Hopcroft, John E.; Ullman, Jeffrey D. (1 de enero de 1969), "Autómatas pushdown deterministas", 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 de los autómatas de empuje deterministas es decidible". Proc. En t. Col. sobre Autómatas, Lenguajes y Programación (ICALP) . Apuntes de conferencias sobre 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 )? La decidibilidad resulta de sistemas formales completos". Informática 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". Informática Teórica . 281 (1–2): 555–608. doi : 10.1016/S0304-3975(02)00027-0 .

Otras lecturas

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