Alternativer Lösungsvorschlag

Question

Wäre folgende Grammatik ebenfalls korrekt?

S→   abc | aAB
A→   aAB
AB→ cbA
cb→  bc
cA→  c

Answer 1

Hey updrq,

deine Grammatik ist leider nicht korrekt. Zum einen ist deine Grammatik nicht monoton, was in der Aufgabenstellung gefordert war.
Eine Grammatik ist dann monoton, wenn für alle Regeln die länge der Symbolkette auf der rechten Seite mindestens so groß ist wie die Länge der Symbolkette auf der linken Seite. Deine letzte Regel verstößt dagegen.

Aber ungeachtet davon, könnte mit einer Gramatik mit deiner Regelmenge Wörter produziert werden, die nicht zur Sprache gehören: Ein Beispiel
S ⇒aAB⇒aaABB⇒aacbAB⇒aacbcbA⇒aacbbcA⇒aacbbc


Viele Grüße
Ashvin