Inwiefern unterscheidet sich die Eindeutigkeit vom Determinismus?

13

Ich versuche zu verstehen, was unter "deterministisch" in Ausdrücken wie "deterministische kontextfreie Grammatik" zu verstehen ist. (Es gibt eher deterministische "Dinge" in diesem Bereich). Ich würde ein Beispiel mehr schätzen als die ausführlichste Erklärung! Wenn möglich.

Meine Hauptverwirrung ist, dass ich nicht feststellen kann, inwiefern sich diese Eigenschaft einer Grammatik von (Nicht-) Mehrdeutigkeiten unterscheidet.

Am ehesten habe ich herausgefunden, was das bedeutet: Dieses Zitat stammt aus dem Artikel von D. Knuth über die Übersetzung von Sprachen von links nach rechts :

Ginsburg und Greibach (1965) haben den Begriff einer deterministischen Sprache definiert; Wir zeigen in Abschnitt V, dass dies genau die Sprachen sind, für die es eine LR (k) -Grammatik gibt

Das wird kreisförmig, sobald Sie zum kommen Section V, denn dort heißt es, dass der LR (k) -Parser die deterministische Sprache parsen kann ...


Nachfolgend finden Sie ein Beispiel, anhand dessen ich nachvollziehen kann, was "ambivalent" bedeutet. Schauen Sie sich dies bitte an:

onewartwoearewe

Welches kann analysiert werden als one war two ear eweoder o new art woe are we- wenn eine Grammatik das erlaubt (sagen Sie, es hat alle Wörter, die ich gerade aufgeführt habe).

Was muss ich tun, um diese Beispielsprache (nicht) deterministisch zu machen? (Ich könnte zum Beispiel das Wort oaus der Grammatik entfernen , um die Grammatik nicht mehrdeutig zu machen).

Ist die obige Sprache deterministisch?

PS. Das Beispiel stammt aus dem Buch Godel, Esher, Bach: Eternal Golden Braid.


Nehmen wir an, wir definieren die Grammatik für die Beispielsprache wie folgt:

S -> A 'we' | A 'ewe'
A -> B | BA
B -> 'o' | 'new' | 'art' | 'woe' | 'are' | 'one' | 'war' | 'two' | 'ear'

Macht diese Grammatik die Sprache durch das Argument, die gesamte Zeichenfolge analysieren zu müssen, nicht deterministisch?


let explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) [];;

let rec woe_parser s =
  match s with
  | 'w' :: 'e' :: [] -> true
  | 'e' :: 'w' :: 'e' :: [] -> true
  | 'o' :: x -> woe_parser x
  | 'n' :: 'e' :: 'w' :: x -> woe_parser x
  | 'a' :: 'r' :: 't' :: x -> woe_parser x
  | 'w' :: 'o' :: 'e' :: x -> woe_parser x
  | 'a' :: 'r' :: 'e' :: x -> woe_parser x
  (* this line will trigger an error, because it creates 
     ambiguous grammar *)
  | 'o' :: 'n' :: 'e' :: x -> woe_parser x
  | 'w' :: 'a' :: 'r' :: x -> woe_parser x
  | 't' :: 'w' :: 'o' :: x -> woe_parser x
  | 'e' :: 'a' :: 'r' :: x -> woe_parser x
  | _ -> false;;

woe_parser (explode "onewartwoearewe");;
- : bool = true

| Label   | Pattern      |
|---------+--------------|
| rule-01 | S -> A 'we'  |
| rule-02 | S -> A 'ewe' |
| rule-03 | A -> B       |
| rule-04 | A -> BA      |
| rule-05 | B -> 'o'     |
| rule-06 | B -> 'new'   |
| rule-07 | B -> 'art'   |
| rule-08 | B -> 'woe'   |
| rule-09 | B -> 'are'   |
| rule-10 | B -> 'one'   |
| rule-11 | B -> 'war'   |
| rule-12 | B -> 'two'   |
| rule-13 | B -> 'ear'   |
#+TBLFM: @2$1..@>$1='(format "rule-%02d" (1- @#));L

Generating =onewartwoearewe=

First way to generate:

| Input             | Rule    | Product           |
|-------------------+---------+-------------------|
| ''                | rule-01 | A'we'             |
| A'we'             | rule-04 | BA'we'            |
| BA'we'            | rule-05 | 'o'A'we'          |
| 'o'A'we'          | rule-04 | 'o'BA'we'         |
| 'o'BA'we'         | rule-06 | 'onew'A'we'       |
| 'onew'A'we'       | rule-04 | 'onew'BA'we'      |
| 'onew'BA'we'      | rule-07 | 'onewart'A'we'    |
| 'onewart'A'we'    | rule-04 | 'onewart'BA'we'   |
| 'onewart'BA'we'   | rule-08 | 'onewartwoe'A'we' |
| 'onewartwoe'A'we' | rule-03 | 'onewartwoe'B'we' |
| 'onewartwoe'B'we' | rule-09 | 'onewartwoearewe' |
|-------------------+---------+-------------------|
|                   |         | 'onewartwoearewe' |

Second way to generate:

| Input             | Rule    | Product           |
|-------------------+---------+-------------------|
| ''                | rule-02 | A'ewe'            |
| A'ewe'            | rule-04 | BA'ewe'           |
| BA'ewe'           | rule-10 | 'one'A'ewe'       |
| 'one'A'ewe'       | rule-04 | 'one'BA'ewe'      |
| 'one'BA'ewe'      | rule-11 | 'onewar'A'ewe'    |
| 'onewar'A'ewe'    | rule-04 | 'onewar'BA'ewe'   |
| 'onewar'BA'ewe'   | rule-12 | 'onewartwo'A'ewe' |
| 'onewartwo'A'ewe' | rule-03 | 'onewartwo'B'ewe' |
| 'onewartwo'B'ewe' | rule-13 | 'onewartwoearewe' |
|-------------------+---------+-------------------|
|                   |         | 'onewartwoearewe' |
wvxvw
quelle
1
-1, da die Frage jetzt wenig Sinn macht. Zunächst einmal ist eine Zeichenfolge keine Sprache. Zeichenfolgen sind nicht mehrdeutig, eindeutig, deterministisch oder nicht deterministisch. Sie sind nur Streicher. Die von Ihnen angegebene Grammatik generiert nicht die Beispielzeichenfolge. Ich habe nicht alle 180 Ableitungen überprüft, um festzustellen, ob es Duplikate gibt, aber theoretisch ist das alles, was Sie tun müssen, um festzustellen, ob die Grammatik nicht eindeutig ist. Leider kann die Sprache nicht von Natur aus mehrdeutig sein, da die Sprache endlich und daher regelmäßig ist und daher von einem DPDA akzeptiert wird und somit deterministisch.
Patrick87
@ Patrick87 wie? Wo sagt es , dass die Zeichenfolge ist die Sprache? Diese Zeichenfolge ist ein Beispielprodukt und es ist sicher möglich, sie mit der angegebenen Grammatik zu generieren. Was lässt dich anders denken? Die fragliche Zeichenfolge ist genau der Fall, wenn zwei verschiedene Sequenzen von Regelanwendungen dieselbe Zeichenfolge erzeugen, die Grammatik also nicht eindeutig ist. Wenn Sie jedoch einige Regeln entfernen (z. B., B -> 'o'ist sie nicht mehr eindeutig ...
wvxvw
Können Sie zunächst eine Ableitung der Beispielzeichenfolge mithilfe der Grammatik bereitstellen? Aus Ihrer eigenen Frage: "Ist die obige Sprache deterministisch?" Du nennst niemals eine Sprache, nur eine Zeichenkette, die durch unendlich viele Grammatiken erzeugt wird, wenn auch nicht die, die du vorschlägst.
Patrick87
Kannst du es auf Englisch schreiben? ZB "Beginnen Sie mit S. Durch die Anwendung der Regel erhalten S := ...wir ..., ..."
Patrick87
@ Patrick87 Ich habe eine schrittweise Generierungsprozedur hinzugefügt und festgestellt, dass ich einen Fehler in der Grammatik gemacht habe, den ich behoben habe.
wvxvw

Antworten:

9

Ein PDA ist deterministisch, daher ein DPDA, wenn für jede erreichbare Konfiguration des Automaten höchstens ein Übergang vorliegt (dh höchstens eine neue Konfiguration möglich). Wenn Sie einen PDA haben, der eine Konfiguration erreichen kann, für die zwei oder mehr eindeutige Übergänge möglich sind, verfügen Sie nicht über einen DPDA.

Beispiel:

Q.={q0,q1}Σ=Γ={ein,b}EIN=q0δ

q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
...

Dies sind nicht deterministische PDAs, da die anfängliche Konfiguration - q_0, Z0- erreichbar ist und zwei gültige Übergänge von ihr wegführen, wenn das Eingabesymbol ist a. Immer wenn dieser PDA versucht, eine Zeichenfolge zu verarbeiten, die mit einem beginnt a, haben Sie die Wahl. Wahl bedeutet nicht deterministisch.

Betrachten Sie stattdessen die folgende Übergangstabelle:

q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
q1   a    a    q0   aa
q1   a    b    q0   ab
q1   a    b    q2   aa
q2   b    a    q0   ba
q2   b    b    q0   bb
q2   b    a    q1   bb

Sie könnten versucht sein zu sagen, dass dieser PDA nicht deterministisch ist; Schließlich gibt es zum Beispiel zwei gültige Übergänge außerhalb der Konfiguration q1, b(a+b)*. Da diese Konfiguration jedoch auf keinem Weg durch den Automaten erreichbar ist, zählt sie nicht. Die einzige erreichbaren Konfigurationen sind eine Teilmenge von q_0, (a+b)*Z0, q1, a(a+b)*Z0und q2, b(a+b)*Z0, und für jede dieser Konfigurationen, höchstens ein Übergang definiert wird .

Eine CFL ist deterministisch, wenn sie die Sprache einiger DPDA ist.

Eine CFG ist eindeutig, wenn jeder String höchstens eine gültige Ableitung gemäß der CFG hat. Ansonsten ist die Grammatik nicht eindeutig. Wenn Sie eine CFG haben und für eine Zeichenfolge zwei verschiedene Ableitungsbäume erstellen können, haben Sie eine mehrdeutige Grammatik.

Eine CFL ist von Natur aus mehrdeutig, wenn sie nicht die Sprache einer eindeutigen CFG ist.

Beachten Sie das Folgende:

  • Eine deterministische CFL muss die Sprache einiger DPDA sein.
  • Jede CFL ist die Sprache unendlich vieler nicht deterministischer PDAs.
  • Eine inhärent mehrdeutige CFL ist nicht die Sprache einer eindeutigen CFG.
  • Jede CFL ist die Sprache unendlich vieler mehrdeutiger CFGs.
  • Eine inhärent mehrdeutige CFL kann nicht deterministisch sein.
  • Eine nicht deterministische CFL kann von Natur aus mehrdeutig sein oder nicht.
Patrick87
quelle
1
Wiki sagt, dass PDA nicht deterministisch ist (es kann eine deterministische Version und eine nicht deterministische Version geben), aber Sie können den ersten Teil des Satzes auch weglassen, da er nicht wirklich zu dem beiträgt, was Sie sagen: / Aber auch dies definiert Eine deterministische Sprache als Eingabesprache für deterministisches Etwas, und dieses Etwas wird deterministisch genannt, weil es deterministische Sprache akzeptiert. Es ist wahr, aber nicht hilfreich :( Bitte, Beispiel wäre mehr als wertvoll!
wvxvw
@wvxvw: Sie lesen das nicht richtig. Es heißt: "Ein PDA ist genau dann deterministisch, wenn jeder Zustand / Symbol / Stacktop-Tripel nur einen nächsten Zustand hat." In dieser Definition steht nichts darüber, welche Sprache der Automat akzeptiert.
Wandering Logic
2
@wvxvw Die Definition von deterministischem PDA oder DPDA, die ich in keiner Weise, Form oder Form gebe, beruht auf der Definition einer deterministischen kontextfreien Sprache. Ich definiere DPDAs nur basierend auf den Eigenschaften des Automaten. Ich definiere dann, was eine deterministische CFL im Sinne einer DPDA-Definition ist. Bitte lesen Sie die Antwort im Lichte dieser und der Kommentare von Wandering Logic noch einmal und versuchen Sie herauszufinden, ob dies Sinn macht. Ich werde mich bemühen, einige kurze Beispiele zu nennen.
Patrick87
q1,b(a+b)q2,b(a+b)Q={q0,...q2}der aktuelle Charakter? Ist meine Interpretation auch richtig? x+- eins oder mehr x, (x)*- null oder mehr x?
wvxvw
@wvxvw Konfiguration bezieht sich auf den aktuellen Status und den aktuellen Inhalt des Stapels. x+bezieht sich typischerweise auf "eines oder mehrere von" x, wohingegen sich x*typischerweise auf "null oder mehrere von" bezieht x; Ich darf xx*anstelle verwenden x+, da diese identisch sind.
Patrick87
7

Hier einige Beispiele (aus Wikipedia):

S0S0|1S1|ε

Eine kontextfreie Sprache ist genau dann deterministisch, wenn mindestens ein deterministischer Push-Down-Automat existiert, der diese Sprache akzeptiert. (Möglicherweise gibt es auch viele nicht deterministische Pushdown-Automaten, die die Sprache akzeptieren, und es handelt sich immer noch um eine deterministische Sprache.) Bei deterministischen Pushdown-Automaten basieren die Maschinenübergänge im Wesentlichen auf dem aktuellen Status. das Eingabesymbol und das aktuell oberste Symbol des Stapels . DeterministischHier bedeutet, dass es nicht mehr als einen Statusübergang für ein Status- / Eingabesymbol- / oberstes Stapelsymbol gibt. Wenn Sie zwei oder mehr nächste Zustände für ein Zustand / Eingabesymbol / oberstes Stapelsymbol-Tripel haben, ist der Automat nicht deterministisch. (Sie müssten "raten", welchen Übergang Sie nehmen müssen, um zu entscheiden, ob der Automat akzeptiert oder nicht.)

Knuth hat bewiesen, dass jede LR (k) -Grammatik einen deterministischen Pushdown-Automaten hat und dass jede deterministische Pushdown-Automate eine LR (k) -Grammatik hat. Somit können LR (k) -Grammatiken und deterministische Pushdown-Automaten dieselbe Menge von Sprachen verarbeiten. Aber die Menge der Sprachen, die einen deterministischen Pushdown-Automaten haben, der sie akzeptiert, sind (per Definition) die deterministischen Sprachen. Das Argument ist nicht kreisförmig.

Deterministische Sprache impliziert also, dass es eine eindeutige Grammatik gibt. Und wir haben eine eindeutige Grammatik gezeigt, die keinen deterministischen Pushdown-Automaten besitzt (und daher eine eindeutige Grammatik, die eine nicht deterministische Sprache akzeptiert).

{anbmcmdn|n,m>0}{anbncmdm|n,m>0}{anbnccdn|n>0}

Wandering Logic
quelle
Können Sie bitte erläutern, warum diese Sprache nicht deterministisch ist, wenn Sie sich die gesamte Zeichenfolge ansehen müssen, bevor Sie die Mitte bestimmen? Ich habe eine andere Erklärung darüber gelesen, was "deterministisch" ist, und dort heißt es: "Wenn Sie beim Parsen nicht zurückgehen müssen, ist diese Sprache deterministisch". Ich sehe keine Notwendigkeit, zurück zu gehen, um diese Sprache zu analysieren ...
wvxvw
1
Betrachten Sie die Eingabezeichenfolge "10011001". Die Pushdown-Automaten wissen nicht, wie lange die Zeichenfolge bis zum Ende ist. Wenn Sie zur zweiten 0 gelangen, müssen Sie eine Auswahl treffen: Ist dies die 4-stellige Zeichenfolge "1001" oder eine längere Zeichenfolge, die wie "100 ???? 001" aussieht? Wenn Sie zum fünften Zeichen kommen, wissen Sie immer noch nicht: Ist dies die 8-stellige Zeichenfolge "10011001" oder eine längere Zeichenfolge, die wie "10011 ???? 11001" aussieht?
Wandering Logic
1
Das "parse the whole string" ist nicht die Definition von nicht deterministisch. Es war nur eine Intuition, die ich hinzufügen wollte. Sowohl @ Patrick87 als auch ich haben Ihnen die wahre Definition von deterministisch gegeben: Von jedem Zustand gibt es höchstens einen nächsten Zustand. Wenn eine Sprache keine eindeutige Grammatik hat, darf sie nicht deterministisch sein. Ich kann nicht auf Ihr Beispiel antworten, ohne mehr zu tun: Sie haben eine mehrdeutige Grammatik gezeigt, aber das ist nicht wichtig. Sie müssen zeigen, dass es keine eindeutige Grammatik gibt, wenn Sie zeigen möchten, dass die Sprache von Natur aus mehrdeutig ist.
Wandering Logic
1
@wvxvw Wenn Sie nach einer Rechenprozedur suchen, haben Sie wahrscheinlich Pech ... Laut en.wikipedia.org/wiki/List_of_undecidable_problems ist es nicht zu entscheiden, ob eine CFG mehrdeutig ist, geschweige denn, ob ihre Sprache von Natur aus mehrdeutig ist ; Es ist auch nicht zu entscheiden, ob eine CFG alle Zeichenfolgen generiert. Angesichts dessen bezweifle ich ernsthaft, dass es entscheidend und viel weniger effizient ist, zu entscheiden, ob die Sprache einer CFG eine deterministische CFL ist.
Patrick87
1
@wvxvw Wenn Sie so viel Glück haben, haben Sie es mit einem von uns als glücklich bezeichneten Fall zu tun, dh nicht mit einem der Fälle, die dies zu einem unentscheidbaren Problem machen. Sie können Heuristiken definieren, die für viele glückliche Fälle funktionieren und den Rest nicht in die Luft jagen, aber nicht für alle glücklichen Fälle funktionieren. Wenn ja, hätten Sie einen Entscheider für das Problem, was nach unserer Prämisse unmöglich ist.
Patrick87
5

Deterministische kontextfreie Sprachen sind diejenigen, die von einem deterministischen Pushdown-Automaten akzeptiert werden (kontextfreie Sprachen sind diejenigen, die von einem nicht deterministischen Pushdown-Automaten akzeptiert werden). Als solches ist es eher eine Eigenschaft einer Sprache als einer Grammatik . Im Gegensatz dazu ist Mehrdeutigkeit eine Eigenschaft einer Grammatik, während inhärente Mehrdeutigkeit eine Eigenschaft einer Sprache ist (eine kontextfreie Sprache ist inhärent mehrdeutig, wenn jede kontextfreie Grammatik für die Sprache mehrdeutig ist).

Es gibt einen Zusammenhang zwischen den beiden Definitionen: Deterministische kontextfreie Sprachen sind niemals inhärent mehrdeutig, wie die Antwort auf diese Frage zeigt .

Yuval Filmus
quelle
Entschuldigung, das ist nicht sehr hilfreich. Eigentlich habe ich mit DPDA angefangen, aber es erklärt nie, warum es als deterministisch bezeichnet wird. Dies ist eine Definition, die bei Wikipedia / Googling für andere Artikel leicht zu finden ist. Aber welche Eigenschaft der Grammatik / Sprache / Parser beschreibt das Wort "deterministisch"? Mit anderen Worten, was sollte in der Grammatik passieren, damit sie als deterministisch bezeichnet wird?
wvxvw
Entschuldigung, wenn ich zu viel kommentiere. Die Verwirrung ist, dass ich nicht sagen kann, ob eine Sprache deterministisch ist oder nicht, und nicht weiß, wo ich anfangen soll, den "Determinismus" der Sprache zu identifizieren. Ein Beispiel für eine Sprache, die deterministisch ist und sich dann so ändert, dass sie nicht deterministisch ist, wäre immens hilfreich.
wvxvw
1
LR(k)
1
Entschuldigung, immer noch nicht hilfreich. Ich verstehe, was Sie sagen, aber es hilft mir nicht, eine deterministische Sprache zu erkennen und sie von der nicht deterministischen zu unterscheiden. Um ein Beispiel zu geben: Wenn eine Sprache eine Produktionsregel hat, die ein Problem mit ausgeglichenen Klammern verursacht, weiß ich sofort, dass sie von FSM nicht analysiert werden kann. (Weil es einen Stapel erfordern würde). Aber wenn Sie nur einen anderen Formalismus erwähnen, wird er nur rekursiv und hilft mir nicht zu verstehen, wie sich diese Sprache von einer anderen unterscheiden sollte.
wvxvw
Mit anderen Worten, Sie möchten (wie Sie in einem vorhergehenden Kommentar erwähnt haben) Beispiele für deterministische und nicht deterministische kontextfreie Sprachen derselben "Art". Vielleicht sollten Sie eine gezielte Frage dazu stellen.
Yuval Filmus
1

{a,b}{w(a+b)w=wR}SaSa|bSb|a|b|ϵababab

PMar
quelle
1

Definitionen

  1. Ein deterministischer Pushdown-Akzeptor (DPDA) ist ein Pushdown-Automat, der keine Wahl hat.
  2. DPDA und NPDA sind nicht gleichwertig.
  3. Eine CFG ist nicht deterministisch, wenn sich auf der rechten Seite mindestens zwei Produktionen mit demselben Terminalpräfix befinden.
  4. Ein CFG ist mehrdeutig, wenn es ein w ∈ L (G) gibt, das mindestens zwei verschiedene Ableitungsbäume hat. Somit hat es zwei oder mehr Ableitungen ganz links oder ganz rechts, die zwei verschiedenen Ableitungsbäumen entsprechen.
  5. Ein CFG ist eindeutig, wenn jeder String höchstens hat eine gültige Ableitung nach dem CFG hat. Ansonsten ist die Grammatik nicht eindeutig.
  6. Eine CFL ist von Natur aus mehrdeutig, wenn sie nicht die Sprache einer eindeutigen CFG ist. Es kann keine DPDA haben.
    Wenn jede Grammatik, die eine CFL erzeugt, mehrdeutig ist, wird die CFL von Natur aus mehrdeutig genannt . So ist es nicht die Sprache von irgendwelchen eindeutige CFG.

Fakten

  1. Jede CFL ist die Sprache unendlich vieler nicht deterministischer PDAs.
  2. Jede CFL ist die Sprache von unendlich vielen mehrdeutiger CFGs.
  3. Eine von einigen akzeptierte CFL DPDA ist von Natur aus nicht mehrdeutig. (Es gibt mindestens eine eindeutige CFG dafür.)
  4. Eine von der NDPDA akzeptierte CFL kann inhärent mehrdeutig sein oder auch nicht, da möglicherweise einige existieren DPDA (oder eine eindeutige CFG) dafür vorhanden ist.
  5. Eine durch mehrdeutiges CFG erzeugte CFL kann inhärent mehrdeutig sein oder nicht, da möglicherweise einige existieren eindeutiges CFG (oder DPDA) dafür vorhanden ist.
  6. Eine von mindestens einer generierte CFL eindeutigen CFG ist nicht von Natur aus mehrdeutig. (Es gibt einige DPDA dafür.)
  7. Eine nicht deterministische Grammatik kann mehrdeutig sein oder auch nicht.

Antwort auf Ihre Frage (Verhältnis zwischen Determinismus und Mehrdeutigkeit)

  1. (Nicht-) Mehrdeutigkeiten betreffen hauptsächlich die Grammatiken (hier CFGs). Der (Nicht-) Determinismus gilt sowohl für Grammatiken als auch für Automaten (hier PDAs).

    Wenn Sie logische Unterschiede wollen, können Sie sich die letzten vier Punkte im Abschnitt "Fakten" ansehen, da sie versuchen, sowohl Mehrdeutigkeit als auch Determinismus in Beziehung zu setzen. Hier wiederhole ich sie noch einmal:

  2. Eine von einem deterministischen PDA akzeptierte CFL ist von Natur aus nicht mehrdeutig . (Es gibt mindestens eine eindeutige CFG dafür.)

  3. Eine von einem nicht deterministischen PDA akzeptierte CFL kann inhärent mehrdeutig sein oder auch nicht, da möglicherweise DPDA vorhanden ist (oder eindeutig ist) CFG) dafür vorhanden ist.
  4. Eine durch mehrdeutiges CFG erzeugte CFL kann von Natur aus mehrdeutig sein oder nicht, da möglicherweise ein eindeutiges CFG (oder ein deterministisches) vorhanden ist PDA) dafür vorhanden ist.
  5. Eine von mindestens einer eindeutigen CFG erzeugte CFL ist nicht von Natur aus mehrdeutig . (Es gibt einige DPDA dafür.)
  6. Eine nicht deterministische Grammatik kann mehrdeutig sein oder auch nicht .

PS:

  1. Die akzeptierte Antwort verwendet Zeilen wie "CFL ist deterministisch", "deterministisch CFL", "CFL kann nicht deterministisch sein", "Eine nicht deterministische CFL". Ich denke, die Adjektive „deterministisch“ und „mehrdeutig“ gelten nicht für CFL, sondern für PDA und CFG (obwohl das Adjektiv „von Natur aus mehrdeutig“ für CFL gilt) weist darauf hin. (Tatsächlich habe ich buchstäblich einige Zeilen aus dieser Antwort kopiert.) Trotzdem hatte ich das Gefühl, dass es korrekter gemacht werden sollte. Also habe ich versucht, die Dinge hier in zwei Teile, Definitionen und Fakten, klarer zu fassen (ich hätte es vielleicht unnötig ausführlich und lang gemacht). Ich denke, ich hätte die ursprüngliche Antwort bearbeiten sollen, aber dann müssen viele Punkte gelöscht werden, die über den Linien liegen. Und ich weiß nicht, ob dies zu einer gültigen Änderung führen wird, da es sich um ein vollständiges Umschreiben handelt.
  2. Beachten Sie, dass ich quantitative Wörter fett und kursiv geschrieben habe , um die Unterschiede zwischen den Definitionen und Fakten hervorzuheben. Die Definitionen sind nur fett gedruckt .
  3. Einige Punkte, die ich selbst gemacht habe, daher brauche ich eine Bestätigung von jemandem, der über die Richtigkeit jedes Punktes Bescheid weiß.
Maha
quelle
PS 1 ist falsch: Es gibt eine Standarddefinition für deterministische / mehrdeutige CFLs, nämlich diejenigen, für die alle CFGs deterministisch / mehrdeutig sind.
Reinierpost
Gerade erkannt, dass Fakt 7 falsch ist. Auch Punkt 6 aus der vorletzten Liste ist gleich und falsch.
Maha
In der Tat ... Determinismus ist zu keinem Zeitpunkt während des Parsens mehrdeutig, daher ist er streng stärker als Mehrdeutigkeit (dh Mehrdeutigkeit auch nach Abschluss des Parsens).
reinierpost