¿Los DCFL están cerrados bajo inversión?

Según este gráfico , los DCFL se cierran por reversión.

Sin embargo, no estoy convencido de que la prueba intuitiva (que invierte las flechas de la máquina de estados finitos de control y cambie los empujes y estallidos) para esto parece depender del no determinismo en la elección de la transición nula para tomar desde el estado inicial (ya que El nuevo estado inicial contendría una transición nula a todos los estados finales antiguos).

Esto haría que el "PDA inverso" de un DPDA no sea determinista siempre que haya más de un estado final en el DPDA original.

¿Cuál es la falacia en mi argumento? ¿O hay otra manera de probar esto?

formal-languages context-free closure-properties pushdown-automata nondeterminism peteykun
fuente

Avíseme si mi respuesta de StackOverflow requiere alguna explicación adicional. El problema con su intento de prueba es este: el PDA que construye no es el único PDA para el lenguaje que acepta. Puede haber otros, posiblemente de otra manera, que sean deterministas. En particular, los DCFL pueden ser aceptados por PDA que no sean deterministas.

Patrick87

Correcto, es por eso que me doy cuenta de que esto no es una "prueba" en absoluto, solo tendría sentido si el resultado fuera siempre un DCFL, que no lo es. Supongo que solo estaba tratando de probarlo usando el mismo método que se usa para los idiomas normales y fallé. Gracias por el contraejemplo!

peteykun

Considerar

L = b^{n} c^{n} \cap a b^{2} n c^{n}

$L={b^n c^n} \cap {a b^2n c^n}$

Pranav

Esa tabla también dice que los lenguajes recursivos están cerrados

λ

$\lambda$ -sustitución libre ... ¿es eso correcto?

anir

Respuestas:

Busqué Hopcroft y Ullman 1979 y dice en la página 281 que no está cerrado bajo inversión. Pero no encontré ninguna prueba en mi rápido vistazo al capítulo correspondiente.

La búsqueda en la web también da una respuesta negativa, con un contraejemplo, en stackoverflow de un miembro de CS (notación adaptada):

$(a+b+c)^*WcW^R$ , dónde $W \in (a+b)^+$ ; esto no es determinista porque no sabes dónde $WcW$ poco comienza

$W^RcW(a+b+c)^*$ , dónde $W \in (a+b)^+$ ; esto es determinista porque puede escribir un PDA determinista para aceptar palíndromos simples de la forma $W^RcW$ y modifique el estado de aceptación para que se repita en cualquiera de $a$ , $b$ y $c$ .

El truco aquí es que los PDA tienen que leer la entrada de izquierda a derecha.

babou
fuente

Esto es absurdo. Patrick87 proporcionó los ejemplos, @Raphael hizo la mitad del trabajo de edición y obtuve el representante. Entonces, nos ponemos tan poco para el trabajo real ... :)

babou

Piense en ello como una "tarifa del buscador" :) Estoy desconcertado de que el sistema realmente funcione lo suficientemente bien como para que haya encontrado esa publicación anterior mía. El sistema funciona! ¡Salve SE!

Patrick87

¿H&U pasó por alto la reversión de DCFL? Mencionan el no cierre bajo unión, concatenación, Kleene, morfismo en Thm 10.5 ver el Ejercicio 10.4 (marcado con una estrella pero con una solución). Sin embargo, notan

{0^{i} 1^{i} 2^{j} ∣ i, j} \cup {0^{i} 1^{j} 2^{j} ∣ i, j}

$\{ 0^i1^i2^j\mid i,j\} \cup \{ 0^i1^j2^j\mid i,j\}$ no es DCFL, entonces tampoco lo es

K = {0^{i} 1^{i} 2^{j} a ∣ i, j} \cup {0^{i} 1^{j} 2^{j} b ∣ i, j}

$K = \{ 0^i1^i2^ja \mid i,j\} \cup \{ 0^i1^j2^jb\mid i,j\}$ por cierre de DCFL bajo cociente con set regular, Thm 10.2. Pero la reversión de

K

$K$ es un DCFL, los 'marcadores'

a

$a$ y

b

$b$ regalar la información sobre dónde usar el pushdown. [Quizás @babou pueda agregar esto si le gusta; él es el que recoge las repeticiones aquí :)]

Hendrik Jan