Inhärente Mehrdeutigkeit der Sprache

Ich ging eine Frage durch, in der ich gebeten wurde, die inhärent mehrdeutige Sprache unter einer Reihe von Optionen auszuwählen.

{L.}_{1} = {{ein}^{n} b^{m} c^{m} d^{n} | m, n \geq 1}} \cup {{ein}^{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\}$

ein n d

$and$

L_{2} = {a^{n} b^{m} c^{m} | m, n \geq 1} \cup {{ein}^{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\}$

Die Lösung besagte, dass mehrdeutig ist, jedoch nicht. Es wurde die folgende Grammatik für generiert $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$

Für die Zeichenfolge abcdwerden nun zwei Analysebäume generiert. so ist es mehrdeutig.

Eine ähnliche Grammatik kann aber auch für werden $L_2$

$S \rightarrow S_1|S_2$

$S_1 \rightarrow Ac$

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

$S_2 \rightarrow aB$

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

Und es werden auch zwei Analysebäume für generiert abc. Warum ist es dann nicht mehrdeutig?

Bei Bedarf kann als $L_2$ $\{a^nb^pc^m\;|\; n=p \;\; or \;\; m=p\}$

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

Nur ein kurzer Kommentar: Eine Grammatik kann mehrdeutig sein oder nicht; Eine Sprache kann nicht mehrdeutig sein, aber sie kann von Natur aus mehrdeutig sein, was bedeutet, dass jede Grammatik für diese Sprache mehrdeutig ist.

Ran G.

L_{1}

$L_1$ ist in der Tat von Natur aus mehrdeutig, und ich gehe davon aus, dass Sie darum bitten, dies zu zeigen

L_{2}

$L_2$ ist nicht, das heißt, eine nicht mehrdeutige Grammatik für zu zeigen

L_{2}

$L_2$ . Wenn ja, sollten Sie die Frage entsprechend bearbeiten.

Ran G.

Ich glaube

L_{2}

$L_2$ ist auch mehrdeutig. Aber die Lösung sagte, dass es nicht ist. Ich möchte wissen "wie".

Shashwat

Sehen Sie hier für eine Technik , die hier nützlich sein könnten.

Raphael

@ FatemehKarimi Mehrdeutigkeit ist eine Eigenschaft der Grammatik, nicht der Sprache. Das heißt, eine Sprache

L

$L$ kann zwei Grammatiken haben: eine mehrdeutig und die andere nicht. Wenn alle Grammatiken mehrdeutig sind, wird die Sprache als inhärent mehrdeutig bezeichnet.

Ran G.

Antworten:

Die Frage ist falsch. Die zweite Sprache ist ebenfalls von Natur aus mehrdeutig. Dies wird üblicherweise wie folgt bewiesen. Annehmen $L_2$ hatte eine eindeutige Grammatik. Lassen $p$ Sei die Konstante, die Ogdens Lemma versprochen hat , und betrachte das Wort $a^{p!+p} b^p c^p$ . Markieren Sie die Positionen von $b^p c^p$ und wende Ogdens Lemma an, um dieses Wort auf das Wort zu pumpen $a^{p!+p} b^{p!+p} c^{p!+p}$ (Ogdens Lemma erlaubt es uns, etwas zu pumpen $b^q c^q$ zum $q\leq p$ , und $q|p!$ schon seit $q \leq p$ .) Ebenso können wir das gleiche Wort durch Pumpen erhalten $a^p b^p c^{p!+p}$ . Die beiden Analysebäume sind unterschiedlich, da im ersten die meisten $b$ s sind "eng verwandt" (in Bezug auf den am wenigsten verbreiteten Vorfahren) mit $c$ s, und im zweiten ist es umgekehrt.

Yuval Filmus
quelle

Weitere Beweismethoden finden Sie in der folgenden Präsentation: algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf

Yuval Filmus

Ordentlich. Das wusste ich vorher nicht.

Raphael

Als Anmerkung, Sprache

L_{2}

$L_2$ Tatsächlich wird in Ogdens Originalarbeit von 1968 "Ein hilfreiches Ergebnis für den Nachweis der inhärenten Mehrdeutigkeit" als Beispiel genannt. Das Ergebnis dieser Sprache selbst wird Ginsburg zugeschrieben, aber wahrscheinlich mit schrecklichen Ad-hoc-Methoden erzielt.

Hendrik

Sie haben völlig Recht, zweifelhaft zu sein, $L_{2}$ ist auch von Natur aus mehrdeutig. Es wurde sogar von Flajolet (gleich zu Beginn von Abschnitt 2) als "Prototyp einer inhärent mehrdeutigen Sprache" verwendet .

Luke Mathieson
quelle