Decida se uma linguagem livre de contexto pode ser aceita por um autômato de pushdown determinístico

22

Dada uma gramática livre de contexto G, existe um autômato de empilhamento não determinístico N que aceita exatamente o idioma que G aceita. (e vice-versa)

Também pode existir um autômato de empilhamento determinístico D que aceite exatamente o idioma que G também aceita. Depende da gramática.

Por qual algoritmo nas produções de G podemos determinar se D existe?

Andrew Tomazos
fonte
4
Mesmo se você souber de antemão que existe um DPDA para G, não há algoritmo para encontrá-lo. Veja aqui .
Sdcvvc

Respostas:

20

Não há algoritmo que, dada uma gramática livre de contexto, decida se um DPDA reconhece o mesmo idioma e o calcula, se existir.

Porque, se esse algoritmo existisse, poderíamos decidir o problema indecidível da universalidade de uma gramática livre de contexto, isto é, se uma determinada gramática livre de contexto on reconhece toda a linguagem .GΣΣ

Suponha que exista esse algoritmo . Seja uma gramática livre de contexto. Deixe ser . Em seguida, o algoritmo vai decidir se há um DPDA reconhecendo .ADPDAGLL(G)ADPDAAL

  • Se não houver esse DPDA, não é reconhecível por um DPDA, em particular não é regular, portanto não pode ser .LΣ

  • Se existe um DPDA , podemos decidir se é igual a because porque a universalidade é decidível para DPDAs. Por quê? Porque:ALΣ

    • Os idiomas do DPDA são fechados sob complementação (porque os DPDAs são determinísticos)
    • o vazio é decidível para DPDAs (porque é para PDAs )

Usando , construímos um algoritmo que decide se para qualquer gramática sem contexto , que se provou impossível. Portanto, não existe.ADPDAL(G)=ΣGADPDA

jmad
fonte
Eu não entendo isso desculpe. Você está usando Σ para se referir ao alfabeto usado por G? E o que você quer dizer "L é a linguagem completa "? Você está dizendo que executaremos o algoritmo em uma gramática G que gera , o idioma de qualquer string acima de Σ? Nós encontraríamos claramente não apenas um DPDA, mas um DFA simples para esse idioma. O complemento de é o idioma vazio, que também é facilmente reconhecido por um DPDA e um DFA - então estou claramente perdendo algo em sua explicação. ΣΣΣ
Andrew Tomazos
D