Existem linguagens inerentemente ambíguas e deterministas sem contexto?

36

Vamos chamar uma linguagem livre de contexto determinística se, e somente se, puder ser aceita por um autômato push-down determinístico, e não determinística caso contrário.

Vamos chamar uma linguagem sem contexto inerentemente ambígua, se e somente se todas as gramáticas sem contexto que geram a linguagem forem ambíguas e, caso contrário, não ambíguas.

Um exemplo de linguagem determinística e inequívoca é a linguagem: Um exemplo de idioma não determinístico e inequívoco é o idioma:

{umanbn{uma,b}|n0 0}
{W{uma,b}|W=WR}

Na Wikipedia , um exemplo de uma linguagem livre de contexto inerentemente ambígua é a seguinte união de linguagens livres de contexto, que também deve ser livre de contexto:

L={anbmcmdn{a,b,c,d}|n,m0}{anbncmdm{uma,b,c,d}|n,m0 0}

Agora, para as perguntas:

  1. Sabe-se se existe uma linguagem determinista, inerentemente ambígua, livre de contexto? Se sim, existe um exemplo (fácil)?
  2. Sabe-se se existe uma linguagem livre de contexto inerentemente ambígua e não determinística? Se sim, existe um exemplo (fácil)?

Claramente, como existe uma linguagem livre de contexto inerentemente ambígua ( eu é um exemplo), a resposta para uma dessas perguntas é fácil, se for sabido se eu é determinístico ou não determinístico. Suponho também que é verdade que, se houver uma determinística, também haverá uma não-determinística ... mas já me surpreendi antes. As referências são apreciadas e pedimos desculpas antecipadamente se esse é um resultado bem conhecido e celebrado (nesse caso, eu não o conheço completamente).

Patrick87
fonte

Respostas:

30

Se uma linguagem é determinística, ela é aceita por algum autômato de empurrão determinístico, o que, por sua vez, significa que existe alguma gramática LR (1) descrevendo a linguagem e, como toda gramática LR (1) é inequívoca, isso significa que não pode ser inerentemente ambíguo. Knuth provou isso em seu artigo no qual ele apresentou LR (1) ( Sobre a tradução de idiomas da esquerda para a direita ).eueu

Uma linguagem pode ser descrita por alguma gramática livre de contexto, se e somente se puder ser reconhecida por algum autômato não determinístico. Como um caso especial disso, gramáticas inerentemente ambíguas e livres de contexto podem ser analisadas por algum autômato não determinístico.

Em uma nota final, qualquer autômato de empurrão determinístico também não é determinístico (este é o caso de praticamente qualquer coisa que possa ser não determinística, para uma definição razoável de não determinismo).

Alex ten Brink
fonte
+1 para a referência pelo fato de que todas as CFLs determinísticas não são inerentemente ambíguas. De fato, isso também responde à outra pergunta: como existe uma linguagem inerentemente ambígua e não é determinística, ela deve ser não determinística (observe que minha definição de LFC não determinística não é padrão, pois exclui LFC determinísticas; é minha culpa por uso indevido de terminologia). De qualquer forma, você deu um exemplo para a pergunta (2) e mostrou que a pergunta (1) é uma impossibilidade. Vou esperar e ver se alguém elabora mais, mas de outra forma aceitará isso como correto. Obrigado!
precisa saber é o seguinte
0

lendo a wikipedia e a resposta e seu comentário, re (Q2), para declarar abertamente, todas as CFLs inerentemente ambíguas devem ser não determinísticas sob o padrão std (incl seu próprio exemplo!). deparei com este ref

vzn
fonte