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

Schöne Ferien!
 

 

S' -> S entspricht nicht der CNF

+2 Punkte
170 Aufrufe

Hallo,

ich bin gerade über die Lösung zu dieser Aufgabe gestolpert.

Die Überführung S' -> S entspricht nicht der Chomsky-Normalform, da sich auf der rechten Seite keine zwei Nonterminalsymbole befinden oder sehe ich das falsch?

Siehe Bild inklusive Lösungsvorschlag.

LG urdsc

Gefragt 14, Feb 2016 in 2013-N-03 von urdsc urdsc Lernwillige(r) (870 Punkte)  
Bearbeitet 14, Feb 2016 von urdsc urdsc
Hallo,

ich wüsste jetzt schon gerne,
1. als Ausnahme der CNF gilt (so steht es auf Wikipedia)
2. ob ich es in der Klausur morgen so schreiben darf!

Ich hoffe es kommt noch eine Antwort.

2 Antworten

0 Punkte
Hallo,

deine frage wurde schonmal beantwortet:

http://info2.aifb.kit.edu/qa/index.php?qa=2670&qa_1=müsste-man-die-umbennung-nicht-im-2-schritt-eliminieren

 

liebe Grüße,

Maren (tutorin)
Beantwortet 14, Feb 2016 von urdnp urdnp Tutor(in) (103,400 Punkte)  
Hallo Maren,
danke für die Antwort.
Leider muss ich dir widersprechen. Ich habe den Thread bereits gesehen, aber dieser geht auf den zweiten Schritt des CNF-Verfahrens ein, während sich meine Frage auf den vierten Schritt bzw. die Form bezieht.
Oh mist sorry,
Dann muss aber gelten:
S'-> AG / AB/ lambda
Wenn du das AB weglassen würdest, hättest du die produktion einfach "gelöscht"
Liebe Grüße
Kein Problem. Stimmt, du hast recht, sonst könnte ich das Wort "ab" nicht schreiben.
Demnach ist die gegebene Lösung als CNF aber falsch?
0 Punkte
Laut 3-32 gilt für Schritt 4 folgendes : Ersetze jede Regel der Form A-> B1...Bn

mit n >=3 . und das würde ja auf S-> S´ nicht zutreffen , da hier nur n=1 gilt .
Beantwortet 14, Feb 2016 von uqdmh uqdmh Lernwillige(r) (140 Punkte)  
Rein nach dem Verfahren würde ich dir recht geben, allerdings wäre das inkonsistent mit der Definition der CNF. Hierbei dürfen ausschließlich zwei Nonterminalsymbole auf der rechten Seite existieren (oder eben ein Terminalsymbol).
Ich denke dieser Fall wurde in dem Verfahren nicht berücksichtigt, weil nach der "Eliminierung reiner Umbennenungen" (Schritt 2) kein Nonterminalsymbol auf einer rechten Seite existieren sollte.
Allerdings besagt der Satz auf Folie 3-30 auch nur, dass jede kontextfreie Sprache auch durch eine Grammatik in CNF beschrieben werden kann, wenn man dabei das leere Wort ausschließt.
...