Kontextsensitive Grammatik

Bei einer kontextsensitiven Grammatik geht aus der Regelmenge hervor, dass die Abbildung von einem Nichtterminalsymbol von  dem “Kontext” dieses Nichtterminalsymbols abhängt. Je nachdem, von welchen Wörtern, d.h. Kombinationen aus Nichtterminal- und Terminalsymbolen ein Nichtterminalsymbol umgeben ist, wird es auf verschiedene Nichtterminal-/Terminalsymbole abgebildet. Die Grammatik reagiert also sensitiv auf den Kontext! 

Außerdem Ist zu beachten, dass kontextsensitive Grammatiken vorschreiben, dass man lediglich ein Nichtterminalsymbol durch eine nichtleere Kette aus Nichterminal- und Terminalsymbolen ersetzten darf – und den Rest, also den Kontext, gleich lässt. Folglich wäre eine Regel der folgenden Form NICHT kontextsensitiv:

AB -> BA

Warum? Die Produktionsregel oben ersetzt auf einen Schlag zwei Nichtterminalsymbole – es ändert sich also auch der Kontext!