Ambiguidade inerente ao idioma

Fiz uma pergunta pedindo que eu escolhesse o idioma inerentemente ambíguo entre um conjunto de opções.

L_{1} = {a^{n} b^{m} c^{m} d^{n} | m, n \geq 1} \cup {a^{n} b^{n} c^{m} d^{m} | m, n \geq 1}

$L_1 = \{a^nb^mc^md^n \;|\; m,n \geq 1\}\cup \{a^nb^nc^md^m \;|\; m,n \geq 1\}$

a n d

$and$

L_{2} = {a^{n} b^{m} c^{m} | m, n \geq 1} \cup {a^{n} b^{n} c^{m} | m, n \geq 1}

$L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$

A solução disse que é ambíguo enquanto não. Gerou a seguinte gramática para $L_1$ $L_2$ $L_1$

$S \rightarrow S_1\;|\;S_2$

$S_1 \rightarrow AB$

$A \rightarrow aAb\;|\;ab$

$B \rightarrow cBd\;|\;cd$

$S_2 \rightarrow aS_2d\;|\;aCd$

$C \rightarrow bCc\;|\;bc$

Agora, para a string abcd, ela gerará duas árvores de análise; por isso é ambíguo.

Mas uma gramática similar pode ser criado para demais $L_2$

$S \rightarrow S_1|S_2$

$S_1 \rightarrow Ac$

$A \rightarrow aAb\;|\;\epsilon$

$S_2 \rightarrow aB$

$B \rightarrow bBc\;|\;\epsilon$

E também irá gerar duas árvores de análise para abc. Por que não é ambíguo então?

Se você precisar, pode ser escrito como $L_2$ $\{a^nb^pc^m\;|\; n=p \;\; or \;\; m=p\}$

formal-languages formal-grammars context-free ambiguity Shashwat
fonte

Apenas um comentário rápido: uma gramática pode ser ambígua ou não; Um idioma não pode ser ambíguo, mas pode ser inerentemente ambíguo, o que significa que qualquer gramática desse idioma é ambígua.

Ran G.

L_{1}

$L_1$ é de fato inerentemente ambíguo, e suponho que você peça para mostrar que não é, ou seja, para mostrar uma gramática não ambígua para . Você deve editar a pergunta adequadamente, se houver.

L_{2}

$L_2$

L_{2}

$L_2$

9788 Ranier G.

Eu acho que é ambíguo. Mas a solução disse que não é. Eu quero saber "como".

L_{2}

$L_2$

Shashwat 9/11/12

Veja aqui uma técnica que pode ser útil aqui.

Raphael

A ambiguidade do @FatemehKarimi é uma propriedade da gramática, não do idioma. Ou seja, alguma língua pode ter duas gramáticas: uma ambígua e a outra não. Se todas as gramáticas são ambíguas, diz-se que a linguagem é inerentemente ambígua.

L

$L$

Ran G.

Respostas:

A pergunta está errada. A segunda língua também é inerentemente ambígua. A maneira usual de provar isso é a seguinte. Suponha que tivesse uma gramática inequívoca. Seja a constante prometida pelo lema de Ogden e considere a palavra . Marque as posições de e aplique o lema de Ogden para bombear esta palavra com a palavra (o lema de Ogden nos permite bombeie para e desde .) Da mesma forma, podemos obter a mesma palavra bombeando $L_2$ $p$ $a^{p!+p} b^p c^p$ $b^p c^p$ $a^{p!+p} b^{p!+p} c^{p!+p}$ $b^q c^q$ $q\leq p$ $q|p!$ $q \leq p$ $a^p b^p c^{p!+p}$ . As duas árvores de análise são diferentes, pois na primeira a maioria dos está "intimamente relacionada" (em termos de ancestral menos comum) com s, e na segunda é o contrário. $b$ $c$

Yuval Filmus
fonte

Veja a seguinte apresentação para outros métodos de prova: algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf

Yuval Filmus

Arrumado. Eu não sabia disso antes.

Raphael

Como observação, a linguagem é de fato mencionada como um exemplo no artigo original de Ogden, de 1968, "Um resultado útil para provar a ambiguidade inerente". O resultado nesse idioma em si é atribuído a Ginsburg, mas provavelmente obtido usando métodos adhoc horríveis.

L_{2}

$L_2$

Hendrik Jan

Você está certo em duvidar, também é inerentemente ambíguo. Foi até usado como "protótipo de uma linguagem inerentemente ambígua" por Flajolet (logo no início da seção 2). $L_{2}$

Luke Mathieson
fonte