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 ewe
oder 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 o
aus 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' |
B -> 'o'
ist sie nicht mehr eindeutig ...S
. Durch die Anwendung der Regel erhaltenS := ...
wir...
, ..."Antworten:
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:
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 ista
. Immer wenn dieser PDA versucht, eine Zeichenfolge zu verarbeiten, die mit einem beginnta
, haben Sie die Wahl. Wahl bedeutet nicht deterministisch.Betrachten Sie stattdessen die folgende Übergangstabelle:
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 vonq_0, (a+b)*Z0
,q1, a(a+b)*Z0
undq2, 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:
quelle
x+
- eins oder mehrx
,(x)*
- null oder mehrx
?x+
bezieht sich typischerweise auf "eines oder mehrere von"x
, wohingegen sichx*
typischerweise auf "null oder mehrere von" beziehtx
; Ich darfxx*
anstelle verwendenx+
, da diese identisch sind.Hier einige Beispiele (aus Wikipedia):
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).
quelle
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 .
quelle
quelle
Definitionen
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
Antwort auf Ihre Frage (Verhältnis zwischen Determinismus und Mehrdeutigkeit)
(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:
Eine von einem deterministischen PDA akzeptierte CFL ist von Natur aus nicht mehrdeutig . (Es gibt mindestens eine eindeutige CFG dafür.)
PS:
quelle