Decidir si un autómata determinista puede aceptar un lenguaje sin contexto

22

Dada una gramática G sin contexto, existe un Automatismo N Pushdown no determinista que acepta exactamente el lenguaje que G acepta. (y viceversa)

También puede existir un Automatismo determinista pushdown D que acepta exactamente el lenguaje que G acepta también. Depende de la gramática.

¿Por qué algoritmo en las producciones de G podemos determinar si D existe?

Andrew Tomazos
fuente
44
Incluso si sabe de antemano que hay un DPDA para G, no hay un algoritmo para encontrarlo. Ver aquí .
sdcvvc

Respuestas:

20

No existe un algoritmo que, dada una gramática libre de contexto, decida si un DPDA reconoce el mismo lenguaje y lo calcula si existe.

Porque si existiera dicho algoritmo, podríamos decidir el problema indecidible de la universalidad de una gramática libre de contexto, es decir, si una gramática libre de contexto dada G en reconoce todo el lenguaje .ΣΣΣ

Supongamos que existe tal algoritmo ADPDA . Deje que G sea ​​una gramática libre de contexto. Deje L ser L(G) . A continuación, el algoritmo ADPDA decidirá si hay un DPDA A reconocimiento L .

  • Si no existe tal DPDA, entonces L no es reconocible por un DPDA, en particular no es regular, por lo que no puede ser Σ .

  • Si existe un DPDA , entonces podemos decidir si es igual a porque la universalidad es decidible para los DPDA. ¿Por qué? Porque:L ΣUNALΣ

    • Los lenguajes DPDA están cerrados bajo complementación (porque los DPDA son deterministas)
    • el vacío es decidible para DPDA (porque es para PDA )

Usando hemos construido un algoritmo para decidir si para cualquier gramática sin contexto , que se ha demostrado que es imposible. Por lo tanto, no existe. L ( G ) = Σ G A D P D AUNArePAGSreUNAL(sol)=ΣsolUNArePAGSreUNA

jmad
fuente
No entiendo esto lo siento. ¿Estás usando Σ para referirte al alfabeto usado por G? ¿Y qué quieres decir con "es L el idioma completo "? ¿Estás diciendo que ejecutaremos el algoritmo en una gramática G que genera , el lenguaje de cualquier cadena sobre Σ? Claramente encontraríamos no solo un DPDA, sino un DFA simple para este lenguaje. El complemento de es el lenguaje vacío, esto también es fácilmente reconocido por un DPDA y un DFA, por lo que claramente me falta algo en su explicación. ΣΣΣΣΣ
Andrew Tomazos
Espero que esto sea más claro ahora. Tenga en cuenta que respondo una pregunta ligeramente diferente: habría jurado que me preguntó si podríamos calcular , no solo decidir si existe o no. re
jmad