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 minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort 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 pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

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