Frage zu Eigenschaften der angegebenen Grammatik

Question

Hier hab ich auch nochmal ne Frage. 

Die in der Lösung angegebene Grammatik ist monoton, aber nicht kontextsensitiv oder? Weil die Nichtterminalsymbole auf der rechten Seite nie "Kontext" auf beiden Seiten haben?? :)

Mit der rechten Seite meine ich die rechten Seiten der Produktionsregeln der Regelmenge

 

Answer 1

Hallo,

ja, die Grammatik ist nicht kontextsensitiv. Im Fall AB->BA zum Beispiel werden auf einen Schlag 2 Nonterminalsymbole ersetzt, kontextsensitive Grammatiken schreiben aber vor, dass man lediglich ein N durch eine nichtleere Kette aus N und T ersetzt und den Rest, also den Kontext, gleich lässt.

Viele Grüße,

Vivian (Tutor)

 

Comments

Kurzer Anmerkung hierzu:

Der Kontext darf bei einer kontextsensitiven Grammatik auch fehlen, das Problem ist hier aber, wie Vivian schon gesagt hat, dass hier mehr als ein Nonterminalsymbol umgewandelt wird.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

---

Wenn ich das also richtig verstehe, ist eine kontextsensitive Grammatik eine monotone Grammatik, aber eine monotone Grammatik nicht zwangsläufig eine kontextsensitive?

---

Genau, da die Produktionsregeln einer kontextsensitiven Grammatik eine Verminderung der Zeichen verhindern.

Max (Tutor)