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

0 Pluspunkte 0 Minuspunkte
104 Aufrufe
Mir ist aufgefallen, dass in Altklausuren  mit Aufgaben zur Chomsky-Normalform häufig in Auggabenteil a) das Umwandeln einer Garmmatik in CNF gefordert ist. Im Aufgabenteil b) soll dann ein Testwort abgeleitet werden, wobei dafür entweder die ursprüngliche Grammatik oder die Grammatik in CNF verwendet werden kann. Da es offensichtlich wenig Sinn macht ein potentiell falsches Zwischenergebnis zu verwenden hätte ich folgende Fragen:

1. Ist es im Allgemeinen einfacher ein Wort mit einer Grammatik in CNF abzuleiten?

2. Gibt es ein strukturiertes Vorgehen zum Ableiten von Wörtern?
in KON-AA von  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hallo,

Zur ersten Frage:

Eine CNF besitzt eine sehr eingeschränkte Regelmenge, d.h. Ableitungsmöglichkeiten, da lediglich erlaubt ist:  N -> NN | T. Damit erhält man ein etwas sequentielleres und strukturierteres Vorgehen beim Ableiten eines Testworts.

Im Gegensatz dazu sind bei beispielsweise Kontextfreien Grammatiken (aus denen oft  eine CNF abgeleitet wird) die Ableitungen von einem N beliebig. Daher können diese sehr unschön aussehen, müssen allerdings nicht.

Im Allgemeinen ist es daher sinnvoll von einer CNF auszugehen. Ist die ursprüngliche Grammatik aber direkt einleuchtend, kann auch diese verwendet werden.

Zur zweiten Frage:

Nein gibt es leider nicht. Es ist aber immer sinnvoll, sich vorab eine grobe Struktur zu überlegen, über welche Schritte das Testwort erreicht werden kann. 

Viele Grüße,

Timon (Tutor)

von ubetd ubetd Tutor(in) (101k Punkte)  
...