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.)

d): N --> Lamda bei Greibach-Normalform?

+1 Punkt
32 Aufrufe
Aufgabenteil Teil d: Wieso ist eine rechtslineare Grammatik automatisch in Greibach-Normalform, wenn bei einer rechtslinearen Grammatik eine Produktion der Form N --> Lamda möglich ist, was bei einer Grammatik in Greibach-Normalform nicht erlaubt ist?

Wenn ich eine rexchtslineare Grammatik mit Abbildungen auf Lamda habe, liegt sie doch nicht in GNF vor, oder sehe ich das falsch?
Gefragt 29, Sep 2015 in 2011-N-02 von uafjv uafjv Tutor(in) (167,990 Punkte)  

2 Antworten

0 Punkte

Du siehst das richtig. In den Folien wird explizit von einer rechtslinearen Grammatik geredet, die Lambda-frei ist. Und ebenfalls ist gilt: PRL ⊆ PGREI ∪ {λ}. Auch hier wird das Lambda wieder extra behandelt. 

In der Frage hätte man wohl besser von einer Lambda-freien rechtslinearen Grammatik sprechen müssen.

Grüße

Simon

 

Beantwortet 29, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
0 Punkte

Sie haben recht, dass die Regel N --> lambda natürlich bei der Greibach Normalform nicht erlaubt ist.

Die Lösung in der Klausur ist das minimal geforderte (und streng genommen auch nicht ganz korrekt), wenn Sie an dieser Stelle geschrieben hätten, dass n--> zu viel ist, dann hätten Sie natürlich auch die volle Punktzahl erhalten.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

 

Beantwortet 29, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...