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

S' -> S entspricht nicht der CNF

2 Pluspunkte 0 Minuspunkte
298 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.
von ufehc ufehc Lernwillige(r) (430 Punkte)  

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.
von urdsc urdsc Lernwillige(r) (870 Punkte)  
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
von urdnp urdnp Tutor(in) (103k Punkte)  
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?
von urdsc urdsc Lernwillige(r) (870 Punkte)  
Bearbeitet von urdsc urdsc
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.
von urdsc urdsc Lernwillige(r) (870 Punkte)  
Powered by Question2Answer
...