Mehrdeutigkeit in regulären und kontextfreien Sprachen

Ich verstehe die folgenden Behauptungen als wahr:

Zwei unterschiedliche Ableitungen eines Strings in einem bestimmten CFG können dem String manchmal denselben Analysebaum zuordnen.
Wenn in einem bestimmten CFG Ableitungen eines Strings vorhanden sind, die unterschiedliche Analysebäume zuordnen, ist das CFG nicht eindeutig.
Einige kontextfreie Sprachen, die durch mehrdeutige CFGs generiert werden, werden auch durch eindeutige CFGs generiert.
Einige Sprachen sind so beschaffen, dass die einzigen CFGs, die sie generieren können (und es gibt solche), nicht eindeutig sind.

Q1. Ich verstehe es auch als unentscheidbar, ob eine willkürliche CFG im Sinne von Punkt 3 mehrdeutig ist. Oder ist es eher unentscheidbar, ob eine kontextfreie Sprache im Sinne von Punkt 4 mehrdeutig ist? Oder sind beide unentscheidbar?

Q2. Welcher der Punkte 1 bis 4 wird falsch, wenn wir "kontextfrei" durch "regulär" ersetzen? Sind reguläre Grammatiken und Sprachen immer eindeutig?

fl.formal-languages regular-language context-free zweifelhaft
quelle

Die Sprachen, die Sie in Punkt 4 erwähnen, sind "von Natur aus mehrdeutig". Für Q1 denke ich, dass es unentscheidbar ist, ob die GRAMMATIK mehrdeutig ist. Somit sind sowohl 3 als auch 4 unentscheidbar.

Lamine

Richtig, Punkt 4-Sprachen werden als "inhärent mehrdeutig" bezeichnet.

Dubiousjim

Q1: beide unentscheidbar. Q2: 1 ist nicht möglich, da höchstens ein Nicht-Terminal in irgendeiner sententialen Form erscheint, so dass jede Ableitung sowohl ganz links als auch ganz rechts ist; 2 das ist immer noch wahr; 3 bleibt wahr, wenn Sie das Bit "auch" entfernen. 4 nicht mehr wahr, zum Beispiel erhalten Sie durch die Bestimmung Ihrer Grammatik eine eindeutige.

Sylvain

@ Sylvain machen das eine Antwort?

Yuval Filmus

@ Sylvain, danke und ja, mach das zu einer Antwort. Kann ich bestätigen, dass ich verstanden habe? Zu 2: Es gibt also eine reguläre Grammatik, die dieselbe Zeichenfolge mit unterschiedlichen Analysebäumen erzeugen kann? (Ich bin seitdem auf einen Verweis auf "mehrdeutige NFAs" gestoßen, bin mir aber nicht sicher, ob "mehrdeutig" in dem Sinne verwendet wird, wie ich es bin). Zu 3 und 4 denke ich, dass Sie sagen, dass einige reguläre Sprachen durch mehrdeutige reguläre Grammatiken erzeugt werden können, aber immer auch durch eine eindeutige reguläre Grammatik erzeugt werden?

Dubiousjim

Antworten:

Zu Q1: Sowohl das Mehrdeutigkeitsproblem (bei einem CFG, ob es mehrdeutig ist) als auch das inhärente Mehrdeutigkeitsproblem (bei einem CFG, ob seine Sprache von Natur aus mehrdeutig ist, dh ob ein gleichwertiges CFG mehrdeutig ist) sind unentscheidbar. Hier sind die Originalreferenzen:

Die Unentscheidbarkeit der Mehrdeutigkeit wurde von Cantor (1962) , Floyd (1962) sowie Chomsky und Schützenberger (1963) bewiesen . Die Beweise in Lehrbüchern reduzieren sich normalerweise aufgrund des Post-Korrespondenz-Problems.
Die Unentscheidbarkeit der inhärenten Mehrdeutigkeit wurde von Ginsburg und Ullian (1966) bewiesen .

Über Q2: Eine reguläre Grammatik ist eine "einseitige lineare" kontextfreie Grammatik, bei der höchstens ein Nichtterminal in einem rechten Teil der Regel erscheint und bei der dieses Nichtterminal am letzten (in der rechten linearen Grammatik) oder am ersten (in) steht linke lineare Grammatik) Position. Solche Grammatiken lassen sich leicht in äquivalente Automaten mit endlichen Zuständen übersetzen (ungefähr unter Berücksichtigung jedes Nichtterminals als Zustand), die eindeutig sind, wenn die reguläre Grammatik eindeutig ist. Die Klasse der eindeutigen regulären Grammatiken und eindeutigen Automaten wurde insbesondere von Stearns und Hunt (1985) untersucht , die zeigen, dass sie über nachvollziehbare Algorithmen für das Einschlussproblem verfügen.

$\beta A\gamma\Rightarrow \beta\alpha\gamma$ $A\to\alpha$ $A$ $X_1,\dots,X_m$ $A\to X_1\cdots X_m$

$\gamma A\eta B\theta$ $A$ $B$ $A\to\alpha$ $\gamma\alpha\eta B\theta$ $B\to\beta$ $\gamma A\eta\beta\theta$ $\gamma\alpha\eta\beta\theta$ (immer das Nicht-Terminal ganz links in einer sententialen Form ableiten) oder Ableitungen ganz rechts legen eine feste Reihenfolge für den Besuch von Ableitungsbäumen fest, und es gibt dann eine einzelne Ableitung für einen bestimmten Ableitungsbaum.

In einer linearen kontextfreien Grammatik gibt es keine solche Wahl, da es höchstens ein Nichtterminal in einer sententialen Form gibt und es eine einzige Ableitung für einen gegebenen Ableitungsbaum gibt, die sowohl ganz links als auch ganz rechts ist.
$w$ $w$ $w$
und 4. Wenn Sie die Automatenansicht mit endlichen Zuständen verwenden, reicht es aus, Ihren mehrdeutigen Automaten zu bestimmen, um einen eindeutigen Automaten für dieselbe Sprache zu erhalten: Für jedes Wort wird ein einziger Lauf ausgeführt. Dieser deterministische Automat entspricht einer eindeutigen regulären Grammatik. $~$

$S\to A\mid B,\,A\to a,\,B\to a$ $a$ $S\Rightarrow A\Rightarrow a$ $S\Rightarrow B\Rightarrow a$ $S\to a$

$O(|G|^2)$ $(q,q')$ $q\neq q'$

Sylvain
quelle

$G$ $\Sigma^*$

Ich habe nicht ganz verstanden, welche Art von Sprachen Sie in 4 sprechen. Jede CF-Sprache hat eine mehrdeutige Grammatik.

Q2. Alles ist entscheidbar, wenn Sie sich mit einer normalen Grammatik beschäftigen. Sie sollten nur ein minimales DFA erstellen und damit eine eindeutige Grammatik erstellen. Wenn Sie sich mit der durch die CF-Grammatik definierten regulären Sprache beschäftigen, lautet die Antwort nein - siehe Q1.

Alexander Rubtsov
quelle

Vielen Dank, gute Klarstellung zu Q2. Fragen zu einer regulären Sprache können entschieden werden, wenn die Sprache durch eine reguläre Grammatik festgelegt wird. Das heißt aber noch nicht, dass sie entscheidbar sind, wenn die Sprache von einer CFG festgelegt wird - das sagen Sie doch, oder? Wissen wir also, dass Fragen zur Mehrdeutigkeit usw., die für willkürliche CFGs nicht zu entscheiden sind, auch dann nicht zu entscheiden sind, wenn sie auf diejenigen CFGs beschränkt sind, die zufällig reguläre Sprachen erzeugen?

Dubiousjim

Das mag nicht sein, aber sie sind immer entscheidbar. Ich meine, wenn Sie sich mit einer Sprache beschäftigen, die durch eine reguläre Grammatik beschrieben wird - der Unterklasse von CFG -, ist jede Frage, die Sie mögen, entscheidbar. Einige unregelmäßige CFGs können jedoch eine reguläre Sprache erzeugen, und es ist unentscheidbar, ob CFG eine reguläre Sprache erzeugt.

Alexander Rubtsov

@ alexandr-rubtsov "Wenn Sie sich mit einer Sprache beschäftigen, die durch eine reguläre Grammatik beschrieben wird, ist jede Frage, die Sie mögen, entscheidbar." Dies scheint eine zu optimistische Aussage zu sein ...

J.-E.

Danke, ich meinte "kann sein" in seiner rhetorischen Funktion, nicht im Sinne von "wer weiß?"

Dubiousjim

@ J.-E.Pin ja ich hätte feiner sein und so etwas wie «alle natürlichen Fragen wie Mehrdeutigkeit» sagen sollen.

Alexander Rubtsov

Es hängt davon ab, ob Sie "kontextfrei" durch "regulär" nur vor "Sprache (n)" oder auch vor "Grammatik (en)" ersetzen.

Alle regulären Sprachen werden durch reguläre Grammatiken erzeugt , insbesondere durch eindeutige reguläre Grammatiken, z. B. LL (1) rechtsreguläre Grammatiken, die alle eindeutig sind.

Reinierpost
quelle