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 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 pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
73 Aufrufe

kann mir jmd viell sagen, wie man bei der Produktion des Wortes vorgeht? gibts da nen trick oder probiert man einfach irgendwie rum?

 

in KON-AD von utdbu utdbu Tutor(in) (107k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte
Häufig können Sie die Wörter relativ einfach produzieren, wenn Sie die Idee der Grammatik verstanden haben. Wenn Sie gar nicht weiter kommen, ist es manchmal hilfreich, von hinten anzufangen (d.h. am Anfang des Wortes steht ein a, d.h. sie brauchen auf jeden Fall ein E, da E -> a, etc.).

Freundliche Grüße
Friederike Pfeiffer

PS: Schauen Sie sich bitte den Algorithmus nochmal an, so dass Sie die Musterlösung nachvollziehen können.
von utdbu utdbu Tutor(in) (107k Punkte)  
0 Pluspunkte 0 Minuspunkte

Die Idee ist, sich anzuschauen, aus welchen CNF-Regeln eine Kette x von Terminalen entstanden sein kann. Für eine Teil-Kette x0 der Länge 1 (ganz zu Beginn des Algorithmus) schaut man sich die Regeln an, die auf der rechten Seite genau x0 stehen haben und merkt sich deren linke Seiten, aus denen x0 entstanden sein könnte. Danach schaut man sich an, aus welchen Symbolen diese linken Seiten entstanden sein könnten, wobei man dafür immer zwei Symbole auf einmal betrachten muss, da so der Aufbau der CNF-Regeln ist. So arbeitet man sich zu immer längeren Teilfolgen der Kette, bis man irgendwann weiß, aus welchen Symbolen die gesamte Kette abgeleitet werden kann. Wenn S dabei ist, weiß man, dass man x mit der Grammatik ableiten kann.

Genauer will ich das hier nicht beschreiben, da es ja auf den Vorlesungsfolien genau beschrieben ist. Außerdem ist diese Animation hilfreich für das Verständnis. Falls Sie aber noch konkrete Fragen haben, beantworten wir die natürlich gerne.

Viele Grüße

Lukas König

 
von utdbu utdbu Tutor(in) (107k Punkte)  
...