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

1 Pluspunkt 1 Minuspunkt
68 Aufrufe
Kann man bei der äquivalenten monotonen Grammatik die Non-Terminalzeichen N und E einfach beibehalten? In der Musterlösung wurden diese aufgeteilt in N0, N1, E0, E1, was ist der Sinn dahinter?
in HU-3-1 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hallo,

ich probiere Dir den Gedankengang der Produktionsregeln mal zu verdeutlichen. Vielleicht wird der Sinn dann klarer.

Also zuerst enthält die zweimal dieselbe Anordnung von Zeichen also kann man w folgendermaßen aufteilen: w = xx.

Der erste Teil wird dabei direkt aus A erzeugt und wird auch anschließend nicht mehr verändert.

Hier ein kleines Beispiel:

AT  -> 0ANT -> 00ANNT -> 001AENNT -> 0011AEENNT

Wenn der erste Teil, also x, vollständig erzeugt wurde, wird das A "herausgelöscht" Man erhält somit 0011EENNT.

Nun fällt auf, dass sich die hinteren Nonterminalsymbole noch in der falschen Reihenfolge befinden. Denn das Wort der Sprache, zu dem wir gelangen wollen, lautet 00110011.

Der nächste Schritt ist somit, dass wir das letzte Nonterminalsymbol (T ausgenommen) durch ein Terminalsymbol ersetzen. Anschließend bleibt uns laut den Produktionsregeln nichts anderes übrig als die erzeugte 0 mindestens einmal nach links durchlaufen zu lassen (0011EE0NT). Ab dann sind zwei grundsätzliche Produktionen möglich (Variationen gehen natürlich auch):

0011EE0NT -> 0011EE00T -> 0011E0E0T -> 0011E00ET -> 0011E001T -> 00110E01T -> 001100E1T -> 0011001ET -> 00110011T -> 00110011

oder

0011E0ENT -> 00110EENT -> 00110EE0T -> 00110E0ET -> 001100EET -> 001100E1T -> 0011001ET -> 00110011T -> 00110011

Abschließend wird dieser ganze Aufwand betrieben, um einfach abzusichern, dass im zweiten Teil die Reihenfolge wie benötigt umgedreht wird.

Sollte dies Deine Frage nicht beantwortet haben, konkretisiere sie bitte erneut.

Viele Grüße

Christoph (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
@Christoph Meine Frage bezieht sich eigentlich nur auf die Umformung zur monotonen Grammatik. Mir ist klar warum man dort A und T in jeweils 2 Hilfsvariablen augeteilt hat, aber nicht warum man analog dazu N und E ebenfalls aufteilt in jeweils 2 Variablen. Soll das nur der Verdeutlichung dienen?!
0 0
Hallo,

hmm... das ist eine gute Frage! Die Aufgabe ist nicht ganz leicht, und als wir sie vor Jahren erstellt haben, waren wir der Meinung, dass man diese Aufspaltung in N0/N1 usw. braucht. Auf den ersten Blick sehe ich im Augenblick aber auch nicht, warum. Vielleicht können Sie ja mal eine Alternativlösung entwerfen, und wir schauen dann, ob sie auch funktioniert...

Viele Grüße

Lukas König, Friederike Pfeiffer-Bohnen und Micaela Wünsche
0 0
Hallo zusammen, ich möchte diese Frage gerne noch einmal aufgreifen. Mein alternativer Lösungsvorschlag wäre, N und E eben nicht aufzuteilen.

Ich habe meinen Vorschlag in den xWizzard getippt, hoffe das passt so:
http://www.xwizard.de:8080/Wizz?template=ID-22139
...