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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 0 Minuspunkte
78 Aufrufe
Hallo,

Leider komme ich nicht auf die zugehörige nicht-monotone Grammatik, die man selbst herausfinden soll... Wie kann ich da vorgehen?

Vielen Dank schon einmal im Vorraus!
in MON-AB von ubetd ubetd Tutor(in) (101k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
Hallo,

nicht monoton bedeutet ja nur, dass es auch Übergänge geben kann, bei denen die rechte Seite kürzer ist als die linke. Da man hierbei also nicht darauf achten muss, dass die Grammatik monoton ist, sollte es einem einfacher fallen eine entsprechende Grammatik zu finden. Hier gibt es viele verschiedene Ansätze.
Wenn man hier auf keinen Ansatz kommt, und die Grammatik trotzdem so gestalten will, dass es einen verkürzenden Übergang gibt kann man ja auch einfach einen bestehenden Übergang so umstellen/ aufteilen, dass sich ein verkürzender Übergang ergibt. Bsp. Statt: S-> bb|b
schreibt man S -> bA , A ->b|lambda. Ist dann wahrscheinlich nicht im Sinne der Aufgabe, aber wäre eine Möglichkeit möglichst schnell und ohne viel Aufwand eine nicht monotone Grammatik zu bekommen.

Grüße, Sören
von updrr updrr Eins-Komma-Null-Anwärter(in) (4.7k Punkte)  
nicht monotone Grammatik Vorschlag
...