Mehdeutige(ambiguous) Kontextfreie Grammatik eindeutig machen
-
Hallo,
ich habe folgende Grammatik:
S -> aSb | abS | epsilonDie ist wie man sieht mehrdeutig.
Jetzt habe ich versucht eine Grammatik zu entwickeln die die gleiche Sprache akzeptiert aber nicht mehrdeutig ist:
S -> aSbS | epsilonBin mir aber nicht ganz sicher ob es richtig ist. Kann mir jemand einen Hinweis geben ob der Ansatz richtig ist oder ich mich auf einem Holzweg befinde?
-
also wenn ich dich richtig verstehe, sollten deine beiden grammatiken gleich sein? das sind sie auf jeden fall nicht, weil
mit Grammatik 1 ist sowas möglich: aεb
mit Grammatik 2 ist sowas nicht möglich.
-
beselbube schrieb:
also wenn ich dich richtig verstehe, sollten deine beiden grammatiken gleich sein? das sind sie auf jeden fall nicht, weil
mit Grammatik 1 ist sowas möglich: aεb
mit Grammatik 2 ist sowas nicht möglich.
ε ist das leere Wort. Das Wort das Du abgeleitet hast ist also "ab", das lässt sich in beiden Grammatiken ableiten. Mir sieht das schon korrekt aus, allerdings würde ich die Grammatik nicht als kontextfrei bezeichnen, weil eine Epsilon-Produktion drin ist.
-
Jester schrieb:
allerdings würde ich die Grammatik nicht als kontextfrei bezeichnen, weil eine Epsilon-Produktion drin ist.
Nanu? Von der Definition hab ich noch nie was gehört.
-
Jester schrieb:
beselbube schrieb:
also wenn ich dich richtig verstehe, sollten deine beiden grammatiken gleich sein? das sind sie auf jeden fall nicht, weil
mit Grammatik 1 ist sowas möglich: aεb
mit Grammatik 2 ist sowas nicht möglich.
ε ist das leere Wort. Das Wort das Du abgeleitet hast ist also "ab", das lässt sich in beiden Grammatiken ableiten. Mir sieht das schon korrekt aus, allerdings würde ich die Grammatik nicht als kontextfrei bezeichnen, weil eine Epsilon-Produktion drin ist.
Oh OK, ist schon etwas her, daran hab ich nich mehr gedacht
-
Bashar schrieb:
Jester schrieb:
allerdings würde ich die Grammatik nicht als kontextfrei bezeichnen, weil eine Epsilon-Produktion drin ist.
Nanu? Von der Definition hab ich noch nie was gehört.
Die rechte Seite einer Regel muß mindestens Länge 1 haben. Das ist sogar für kontextsensitive Grammatiken so. Einzige Ausnahme bildet das Startsymbol. Allerdings darf das Startsymbol in diesem Fall sonst nirgendwo mehr auf der rechten Seite auftauchen.
Streng genommen ist obige Grammatik sogar nichtmal kontext-sensitiv. Siehe http://de.wikipedia.org/wiki/Kontextsensitive_Grammatik
-
Jester schrieb:
Bashar schrieb:
Jester schrieb:
allerdings würde ich die Grammatik nicht als kontextfrei bezeichnen, weil eine Epsilon-Produktion drin ist.
Nanu? Von der Definition hab ich noch nie was gehört.
Die rechte Seite einer Regel muß mindestens Länge 1 haben.
Das sagtest du ja bereits.
Auf Wikipedia-Seiten zu verweisen ist bei solchen Diskussionen ziemlich sinnfrei. Schau auf die englische, die lässt das leere Wort auf der rechten Seite zu. Was stimmt nun? Jeder definiert es so, wie er will. Wenn man jetzt kontextfreie Grammatiken mit Epsilon-Produktionen nicht als kontextfrei bezeichnen will, muss man wissen, was einem das bringt. Für meine Zwecke ergibt das keinen Sinn.
-
Bashar schrieb:
Auf Wikipedia-Seiten zu verweisen ist bei solchen Diskussionen ziemlich sinnfrei. Schau auf die englische, die lässt das leere Wort auf der rechten Seite zu. Was stimmt nun? Jeder definiert es so, wie er will. Wenn man jetzt kontextfreie Grammatiken mit Epsilon-Produktionen nicht als kontextfrei bezeichnen will, muss man wissen, was einem das bringt. Für meine Zwecke ergibt das keinen Sinn.
Bei kontextsensitiven Grammatiken muß man das fordern, da tut es auch die englische Wikipedia und auch jedes andere Buch, schließlich ist das der einzige Unterschied zur CH-0 Grammatik.
Damit nun eine kontextfreie Grammatik insbesondere auch kontextsensitiv ist, ist diese Forderung sinnvoll, da anderenfalls diese beiden keine Hierarchie bilden und es eben kontextfreie Grammatiken gäbe, die nicht kontextsensitiv sind. Für mich ist das ein guter Grund die Definition so zu wählen, weil es die Inklusioneigenschaften von Grammatiken und Sprachen ähnlicher macht.
Darf ich fragen für welche Zwecke du das anders machst?
-
Bashar schrieb:
Auf Wikipedia-Seiten zu verweisen ist bei solchen Diskussionen ziemlich sinnfrei.
Dem muß ich mal ganz klar widersprechen. Offensichtlich kennen wir beide verschiedene Definitionen von "kontextfreie Grammatik". Es ist also nicht sinnfrei durch einen solchen Verweis klar zu machen, dass die jeweils andere Definition so wirklich existiert. Oder kannst Du die andere Definition und wolltest mich nur mal auflaufen lassen?
-
Jester schrieb:
Bei kontextsensitiven Grammatiken muß man das fordern, da tut es auch die englische Wikipedia und auch jedes andere Buch, schließlich ist das der einzige Unterschied zur CH-0 Grammatik.
Kann sein. CH-1 ist noch uneinheitlicher definiert, da kann man nämlich entweder monotone oder kontextsensitive Grammatiken benutzen (die die gleiche Sprachfamilie erzeugen), wobei jetzt wieder manche monotone Grammatiken als kontextsensitiv bezeichnen.
BTW, wieso ist das der einzige Unterschied zur CH-0 Grammatik? Bei einer kontextsensitiven Grammatik darf nur ein Nichtterminal ersetzt werden, der linke und rechte Kontext muss erhalten bleiben. Dass das Nichtterminal jetzt gerade mal nicht durch eps ersetzt werden darf, keine Ahnung was damit ist, aber das zentrale Merkmal ist es jedenfalls nicht.
Zumal die englische Wikipedia hier schon wieder fragwürdiges Zeug schreibt:
A formal grammar G = (N, Σ, P, S) is context-sensitive if all rules in P are of the form
αAβ → αγβ
where A ∈ N (i.e., A is a single nonterminal), α,β ∈ (N U Σ)* (i.e., α and β are strings of nonterminals and terminals) and γ ∈ (N U Σ)+ (i.e., γ is a nonempty string of nonterminals and terminals).Some definitions also add that for any production rule of the form u → v of a context-sensitive grammar, it shall be true that |u|≤|v|. Here |u| and |v| denote the length of the strings respectively.
Die Forderung, gamma solle nicht leer sein, ist äquivalent zu |u| <= |v|, was aber angeblich nur "some definitions" fordern.
Für mich ist das ein guter Grund die Definition so zu wählen, weil es die Inklusioneigenschaften von Grammatiken und Sprachen ähnlicher macht.
Darf ich fragen für welche Zwecke du das anders machst?
Ganz einfach: Spezifikation von Grammatiken für Programmiersprachen, die von einem handelsüblichen Parsergenerator gelesen werden können. Wenn du das Drachenbuch aufschlägst und dir die Theorie dazu anguckst, dann werden da auch immer epsilon-Produktionen mit berücksichtigt.
kannst Du die andere Definition und wolltest mich nur mal auflaufen lassen?
Nein, das würde ich nie tun. Ich bin mir höchstens bewusst, dass es widersprüchliche Definitionen geben kann (nicht welcher Art die sind), und finde daher einen Hinweis auf Wikipedia als Autorität wie gesagt sinnlos.
-
4711_EchtKoelsch schrieb:
Hallo,
ich habe folgende Grammatik:
S -> aSb | abS | epsilonDie ist wie man sieht mehrdeutig.
Jetzt habe ich versucht eine Grammatik zu entwickeln die die gleiche Sprache akzeptiert aber nicht mehrdeutig ist:
S -> aSbS | epsilonBin mir aber nicht ganz sicher ob es richtig ist. Kann mir jemand einen Hinweis geben ob der Ansatz richtig ist oder ich mich auf einem Holzweg befinde?
Beschreib mal die Produktion, die du haben willst!
S -> 'a' S 'b' | 'a' 'b' S | epsilon // a rausziehen S -> A S 'b' | A 'b' S | epsilon // | A -> 'a' S -> 'a' O | epsilon // a rausziehen war nicht notwenig O -> S 'b' | 'b' SSollte doch eindeutig sein?
-
Bashar schrieb:
Die Forderung, gamma solle nicht leer sein, ist äquivalent zu |u| <= |v|, was aber angeblich nur "some definitions" fordern.
Diesen Abschnitt kann man auch so interpretieren, dass er Sinn macht, nämlich analog zu
http://de.wikipedia.org/wiki/Metrischer_Raum schrieb:
Die Nicht-Negativität d(x,y) ≥ 0 wird oft als zusätzliches Axiom angegeben, folgt aber aus den anderen Bedingungen und ist daher überflüssig.
-
Bashar schrieb:
BTW, wieso ist das der einzige Unterschied zur CH-0 Grammatik? Bei einer kontextsensitiven Grammatik darf nur ein Nichtterminal ersetzt werden, der linke und rechte Kontext muss erhalten bleiben. Dass das Nichtterminal jetzt gerade mal nicht durch eps ersetzt werden darf, keine Ahnung was damit ist, aber das zentrale Merkmal ist es jedenfalls nicht.
Letztlich hängt es genau an dieser Eigenschaft der Nichtverkürzung, dass CH-1-Sprachen noch entscheidbar sind, CH-0 aber eben nicht. Für mich ist das ein sehr zentrales Merkmal. Allerdings gebe ich zu, dass ich eher aus einem komplexitätstheoretischen Blickwinkel als aus einem Compilerbau-Blickwinkel auf die ganze Sache schaue.