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

Kategorien

2 Pluspunkte 0 Minuspunkte
213 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

in 2013-N-03 von urdsc urdsc Lernwillige(r) (870 Punkte)  
Bearbeitet von urdsc urdsc
0 0
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 Pluspunkte 0 Minuspunkte
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)
von urdnp urdnp Tutor(in) (103k Punkte)  
0 0
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.
0 0
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
0 0
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 Pluspunkte 0 Minuspunkte
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 .
von uqdmh uqdmh Lernwillige(r) (140 Punkte)  
0 0
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.
...