Problem mit ε in Grammatiken

Ark · 14. September 2009, 12:08

Hallo,

ich habe eine Frage, die bisher nicht zu meiner Zufriedenheit beantwortet werden konnte. Es betrifft folgende Aussagen in der Wikipedia über kontextsensitive Grammatiken:

Einzige Ausnahme zu obiger Form bildet die Regel S → ε, die eventuell benötigt wird, das leere Wort ε abzuleiten. Sie darf aber nur dann verwendet werden, wenn das Startsymbol S auf keiner rechten Regelseite vorkommt.

Man nehme nun folgende Produktionsregeln an:

S → A
S → b
S → ε
A → B
A → a
B → A
B → b
B → ε

Von welchem Typ ist diese Grammatik? Was mir Kopfzerbrechen bereitet, ist die oben fett hervorgehobene Regel. Nach dem, was in der Wikipedia steht, ist es nicht erlaubt, diese Regel in

A → S

zu ändern, wenn es eine Typ-1-Grammatik werden will, obwohl im dargestellten Fall genau das gleiche rauskommen würde.

Kann mir das jemand erklären?

Ark

Luna · 14. September 2009, 14:43

CH-0 ist sie ja auf jeden Fall, ansonsten... oje. Ich erinnere mich noch, dass das mit dem Startsymbol immer so ein Sonderfall war, der Probleme gemacht hat.
Wieso willst du A -> B denn in A -> S aendern?
Nachdem da ja nur im Kreis geleitet (und nix zusaetzlich erzeugt) wird, wuerd ich einfach
S → A
A → B
B → A
B → b
B → ε
verkuerzen in
S → b
S → ε
und noch ein
S → a
hinzufuegen, weil aus A ja auch ein kleines a abgeleitet/erzeugt werden kann. Das waere dann das, was im Endeffekt alles aus S -> A erzeugt werden kann.

Nachdem das aber am Anfang sowieso schon teilweise in der Grammatik steht, wuerd ich die komplette Grammatik einfach entsprechend kuerzen und noch ein S → a hinzufuegen:
S → a
S → b
S → ε

Damit muesste es dann auch CH-1 sein.

Was die Sache mit dem S → ε und S auf der rechten Seite angeht - ich glaub, das ist auch definitionsabhaengig. Da gibt es, soweit ich mich erinnere, sowohl die eine als auch die andere Variante, also dass rechts kein S vorkommen darf, oder halt schon. Muss man wohl einfach so hinnehmen und damit arbeiten, wie es einem in der Schule/Vorlesung definiert wurde.
Letztendlich geht es hauptsaechlich darum, dass in Klausuren eben einheitlich gearbeitet wird.

Ark · 14. September 2009, 15:41

Zugegeben, das Beispiel ist wirklich sehr konstruiert, und die von dir genannten Regeln hätten es auch getan, wie du geschrieben hast (wäre sogar Typ 3). Dennoch muss es ja irgendeinen sinnvollen Hintergrund geben, ich meine, solche Restriktionen denkt man sich üblicherweise nicht aus. oo

Ark

EDIT:

Mir wurde freundlicherweise dieser Link geschickt. Vielen Dank dafür noch einmal.

Damit ich sichergehen kann, es richtig verstanden zu haben, gebe ich noch einmal wieder, wie ich das lese:

Generell darf nur Typ 0 ein ε auf der rechten Seite haben. Alle anderen Typen dürfen auf der rechten Seite kein ε haben. Einzige Ausnahme ist die Produktionsregel S → ε, sie darf auch in Typ>=1-Grammatiken vorkommen. Dass man Grammatiken vom Typ >= 2 auch mit Epsilons auf der rechten Seite findet, ist eher nur der Bequemlichkeit geschuldet. Tatsächlich lassen sich diese Regeln nämlich so umformen, dass sie (bis auf ein eventuelles S → ε) kein ε auf der rechten Seite haben, womit die Bedingung wieder erfüllt ist.

Ist das so korrekt?

Ark

Teilen