Gibt es inhärent mehrdeutige und deterministische kontextfreie Sprachen?

36

Nennen wir eine kontextfreie Sprache genau dann deterministisch, wenn sie von einem deterministischen Push-Down-Automaten akzeptiert werden kann, und andernfalls nicht deterministisch.

Nennen wir eine kontextfreie Sprache von Natur aus nur dann mehrdeutig, wenn alle kontextfreien Grammatiken, die die Sprache erzeugen, mehrdeutig und ansonsten eindeutig sind.

Ein Beispiel für eine deterministische, eindeutige Sprache ist die Sprache: Ein Beispiel für eine nicht deterministische, eindeutige Sprache ist die Sprache:

{anbn∈{a,b}∗|n≥0}
{w∈{a,b}∗|w=wR}

Ein Beispiel für eine inhärent mehrdeutige kontextfreie Sprache aus Wikipedia ist die folgende Vereinigung kontextfreier Sprachen, die ebenfalls kontextfrei sein muss:

L={anbmcmdn∈{a,b,c,d}∗|n,m≥0}∪{anbncmdm∈{a,b,c,d}∗|n,m≥0}

Nun zu den Fragen:

  1. Ist bekannt, ob es eine deterministische, inhärent mehrdeutige kontextfreie Sprache gibt? Wenn ja, gibt es ein (einfaches) Beispiel?
  2. Ist bekannt, ob es eine nicht deterministische, inhärent mehrdeutige kontextfreie Sprache gibt? Wenn ja, gibt es ein (einfaches) Beispiel?

Da eine inhärent mehrdeutige kontextfreie Sprache existiert ( ist ein Beispiel), ist die Antwort auf eine dieser Fragen einfach, wenn bekannt ist, ob deterministisch oder nicht deterministisch ist. Ich nehme auch an, dass es wahr ist, dass es, wenn es ein deterministisches gibt, auch ein nicht deterministisches geben muss ... aber ich war vorher überrascht. Referenzen werden geschätzt und ich entschuldige mich im Voraus, wenn dies ein bekanntes, gefeiertes Ergebnis ist (in diesem Fall bin ich mir dessen überhaupt nicht bewusst).LL

formal-languages automata formal-grammars pushdown-automata Patrick87
quelle

Antworten:

30

Wenn eine Sprache deterministisch ist, wird sie von einem deterministischen Push-Down-Automaten akzeptiert, was wiederum bedeutet, dass es eine LR (1) -Grammatik gibt, die die Sprache beschreibt, und da jede LR (1) -Grammatik eindeutig ist, bedeutet dies, dass dies nicht kann von Natur aus mehrdeutig sein. Knuth hat dies in seiner Arbeit bewiesen, in der er LR (1) ( Über die Übersetzung von Sprachen von links nach rechts ) vorstellte .LL

Eine Sprache kann durch eine kontextfreie Grammatik genau dann beschrieben werden, wenn sie von einem nicht deterministischen Automaten erkannt werden kann. Als Sonderfall können inhärent mehrdeutige kontextfreie Grammatiken von einem nicht deterministischen Automaten analysiert werden.

Letztendlich ist jeder deterministische Push-Down-Automat auch nicht deterministisch (dies ist der Fall für nahezu alles, was nicht deterministisch sein kann, für eine vernünftige Definition des Nichtdeterminismus).

Alex ten Brink
quelle
+1 für die Referenz für die Tatsache, dass alle deterministischen CFLs nicht von Natur aus mehrdeutig sind. Tatsächlich beantwortet dies auch die andere Frage: Da es eine inhärent mehrdeutige Sprache gibt und diese nicht deterministisch ist, muss sie nicht deterministisch sein (beachte, dass meine Definition von nicht deterministischer CFL nicht Standard ist, da sie deterministische CFLs ausschließt; das ist meine Schuld für die missbräuchliche Verwendung von Terminologie). In jedem Fall haben Sie ein Beispiel für Frage (2) angegeben und gezeigt, dass Frage (1) eine Unmöglichkeit ist. Ich werde abwarten, ob jemand mehr ausführt, aber ansonsten dies als richtig akzeptieren. Vielen Dank!
Patrick87
0

Lesen Sie Wikipedia & die Antwort & Ihren Kommentar dazu, um (Q2) klar zu sagen, dass alle inhärent mehrdeutigen CFLs unter der Standarddefinition nicht deterministisch sein müssen (einschließlich Ihres eigenen Beispiels!). lief über diese ref

vzn
quelle