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:

{{uma}^{n} b^{n} \in {uma, b}^{*} | n \geq 0 0}

$\{a^{n}b^{n} \in \{a, b\}^{*} | n \ge 0\}$

{W \in {uma, b}^{*} | W = W^{R}}

$\{w \in \{a, b\}^{*} | w = w^{R}\}$

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 = {a^{n} b^{m} c^{m} d^{n} \in {a, b, c, d}^{*} | n, m \geq 0} \cup {a^{n} b^{n} c^{m} d^{m} \in {uma, b, c, d}^{*} | n, m \geq 0 0}

$L = \{a^{n}b^{m}c^{m}d^{n} \in \{a, b, c, d\}^{*} | n, m \ge 0\} \cup \{a^{n}b^{n}c^{m}d^{m} \in \{a, b, c, d\}^{*} | n, m \ge 0\}$

Agora, para as perguntas:

Sabe-se se existe uma linguagem determinista, inerentemente ambígua, livre de contexto? Se sim, existe um exemplo (fácil)?
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 ( $L$ é um exemplo), a resposta para uma dessas perguntas é fácil, se for sabido se $L$ é 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).

formal-languages automata formal-grammars pushdown-automata Patrick87
fonte

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 ). $L$ $L$

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

Algumas linguagens sem contexto inerentemente ambíguas / Shamir e provavelmente outras são estudadas na literatura.

vzn
fonte

Existem linguagens inerentemente ambíguas e deterministas sem contexto?

Respostas: