Was sähe die nicht monotone Grammatik aus?

Question

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!

Answer 1

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