Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Greibach Normal Form

0 Punkte
65 Aufrufe
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
Gefragt 7, Feb 2017 in MON-AB von uodys uodys Lernwillige(r) (870 Punkte)  

Eine Antwort

+1 Punkt
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).
Beantwortet 7, Feb 2017 von Lukas König Dozent (10,065,100 Punkte)  
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]@
...