Greibach Normal Form

Question

Hallo,

muss man die Schritte für die Erzeugung der GNF aus einer beliebigen kontextfreien Grammatik wissen ? oder nur die Schritte für die CNF

 

danke

Answer 1

Haben Sie sich mal den Algorithmus für die GNF angeschaut? Im Lehrbuch wird der beschrieben - über 10 Seiten oder so! Nicht dass das nicht ein spannender Algorithmus wäre, aber nein, den müssen Sie nicht kennen.

Sie müssen aber wissen, was die GNF ist und ein paar grundlegende Eigenschaften kennen (siehe alte Klausuren).

Comments

Was ist denn etwa der Unterschied zwischen der Ableitung des Wortes $aabbab$ durch die folgende kontextfreie Grammatik - und durch die äquivalente GNF-Grammatik darunter (http://www.xwizard.de:8080/Wizz?template=ID-C22768)?

@[ID-C22768]@

@[ID-C22767]@

---

Wenn es um die Anzahl an Schritte für die Ableitung des Wortes geht
dann ist es durch GNF = |w|= 6 > durch die äquivalente kontextfreie Grammatik = 7

---

Ja, genau darauf wollte ich hinaus. Und wie ist es mit der CNF?

---

in der CNF habe ich 2|w| am Anfang gedacht aber mit Beispielen ergibt sich immer 2|w| -1. Ich verstehe nicht wo -1 herkommt.
( |w| für die Regel der Form N-->T, T Terminalsymbol
und |w| für die Regel der Form N--> AB, (mit A,B Nonterminalsymbole)

---

Das liegt daran, dass am Anfang $S$ ja schon "dasteht". Von $S$ aus erzeugen wir in jedem Schritt aus einem Nonterminal zwei, bis die Wortlänge erreicht ist - das sind also $|w|-1$ Ableitungen. Und dann muss noch jedes Nonterminal in ein Terminal überführt werden, was weitere $|w|$ Schritte benötigt. Hier ist die CNF zur obigen Grammatik:
@[ID-22792]@