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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
75 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?
in 2011-N-02 von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte

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

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 Pluspunkte 0 Minuspunkte

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

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...