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 libres de contexto deterministas , 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 más bajos en la pila no son visibles y no tienen un efecto inmediato. Las acciones de la máquina incluyen empujar, hacer estallar o reemplazar la parte superior de la pila. Un autómata de empuje 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
Un PDA (no necesariamente determinista) se puede definir como una tupla de 7:
dónde
- es un conjunto finito de estados
- es un conjunto finito de símbolos de entrada
- es un conjunto finito de símbolos de pila
- es el estado de inicio
- es el símbolo de la pila inicial
- , dónde es el conjunto de estados de aceptación
- es una función de transición, donde
- dónde es 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 de poder de un conjunto .
M es determinista si satisface las dos condiciones siguientes:
- Para cualquier , el conjunto tiene como máximo un elemento.
- Para cualquier , Si , luego para cada
Hay 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 pushdown determinista (aunque sí lo son para el autómata pushdown 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. [ cita requerida ]
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 idioma 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 que se acepta uno para todas las cadenas que pertenecen a . Si puede ser aceptado por un PDA es un lenguaje libre de contexto y si puede ser aceptado por un DPDA es un lenguaje determinista libre de contexto (DCFL).
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 pares 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 n , debe usar su pila para memorizar la longitud n , con el fin de poder distinguir sus posibles continuaciones 0 n 11 0 n ∈ L p y 0 n 11 0 n +2 ∉ L pág . Por lo tanto, después de leer 0 n 11 0 n , 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 n 11 0 n 0 n 11 0 n ∈ L p y 0 n 11 0 n 0 n +2 11 0 n +2 ∉ L p no se pueden distinguir. [2]
Restringir la DPDA a un solo estado reduce la clase de idiomas aceptados para los idiomas LL (1) , [3] que es una subclase adecuada de la DCFL. [4] En el caso de un PDA, esta restricción no tiene ningún efecto sobre la clase de idiomas aceptados.
Propiedades
Cierre
Las propiedades de cierre de los lenguajes libres de contexto deterministas (aceptadas por PDA determinista por estado final) son drásticamente diferentes 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 un PDA determinista también es aceptado por un PDA determinista es complicado. [ cita requerida ] En principio, uno tiene que evitar cálculos infinitos.
Como consecuencia de la complementación, se puede decidir si un PDA determinista acepta todas las palabras sobre su alfabeto de entrada, probando su complemento en busca de vacuidad. 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 determinista (es decir, dados dos PDA deterministas A y B, ¿L (A) = L (B)?) Es decidible, [5] [6] [7] una prueba de que le valió el Premio Gödel 2002 . Para PDA no determinista, la equivalencia es indecidible.
Notas
- ^ Michael Sipser (1997). Introducción a la Teoría de la Computación . Publicación de PWS. pag. 102 . ISBN 0-534-94728-X.
- ^ 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. pp. 249 -253.
- ^ Kurki-Suonio, R. (1969). "Notas sobre idiomas descendentes". BIT . 9 (3): 225–238. doi : 10.1007 / BF01946814 .
- ^ Rosenkrantz, DJ; Stearns, RE (1970). "Propiedades de las gramáticas de arriba hacia abajo deterministas" . Información y control . 17 (3): 226–256. doi : 10.1016 / s0019-9958 (70) 90446-8 . Aquí: p.246–247
- ^ Sénizergues, Géraud (1997). "El problema de equivalencia para los autómatas pushdown deterministas es decidible". Proc. En t. Coll. sobre Autómatas, Lenguajes y Programación (ICALP) . Apuntes de conferencias en informática . 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.
- ^ 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 .
- ^ 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
- Hamburger, Henry; Dana Richards (2002). Modelos de lógica y lenguaje para la informática . Upper Saddle River, Nueva Jersey 07458: Prentice Hall. págs. 284 –331. ISBN 0-13-065487-6.Mantenimiento de CS1: ubicación ( enlace )