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

Warum ist G' nicht auch in Kuroda-Normalform?

0 Pluspunkte 0 Minuspunkte
77 Aufrufe
Warum ist G' nicht auch in Kuroda-Normalform?
Gefragt 8 Feb in 2016-H-04 von uyjdl uyjdl Lernwillige(r) (190 Punkte)  

Eine Antwort

1 Pluspunkt 0 Minuspunkte
Ja, G' ist auch in Kuroda Normalform (Dies gilt immer, sobald eine Grammatik in CNF vorliegt und es keinen Lambda-Übergang gibt)

LG Nico (Tutor) (Alle Angaben ohne Gewähr)
Beantwortet 8 Feb von unort unort Eins-Komma-Null-Anwärter(in) (3,890 Punkte)  
Bearbeitet 8 Feb von unort unort
Hallo Nico,

eine Frage dazu: CNF ist doch immer in KNF auch ohne die Bed. mit dem Lambdaübergang, da bei beiden dies nur unter der Voraussetzung erlaubt ist, das Lamdba bei S vorkommt und S nicht auf einer der rechten Seiten.

Falls ich falsch liege, gerne berichtigen.

Gruß
Für die Kuroda Normalform hat man Regeln der Form:
A-->a|B|BC und AB-->CD
Hier gibt es überhaupt keine Lambda-Übergänge...auch nicht von S.

Ohne A-->B und AB-->CD sind Grammatiken der Kuroda Normalform auch in CNF.

LG, Nico (Tutor) (Alle Angaben ohne Gewähr)
Hi Nico,

ich würde dir gerne hier den Screenshot zeigen von der VL, aber man kann keine Bilder in den Kommentaren einfügen (nur in extra Fragen)

Bei uns in "VL 11: kontextsensitive und allgemeine Sprachen" ist unter Kuroda NF explizit erwähnt, dass die KNF auch das leere Wort enthalten darf.

Gruß
Ok dann lieg ich da wohl falsch, sorry.
Bei uns gab es die Kuroda Normalform damals nicht.
...