Kleines Nachschlagewerk Informatik
kontextsensitive Sprachen
Worum geht es?
Bisher waren Ersetzungsregeln so formuliert, dass links ein Nichtterminalsymbol stand. Dieses konnte beliebig ersetzt werden. Was jedoch noch nicht vorkam, sind Ersetzungsregeln, die von einem Kontext, also einem Umfeld an Terminalsymbolen, abhängig waren. Man spricht - wegen dieser Abhängigkeit vom Kontext - von kontextsensitiven Sprachen.
Produktionsregeln
Produktionsregeln können wie folgt erweitert werden: Links dürfen beliebige Kombinationen aus Terminal- und Nichtterminalsymbolen stehen, wobei mindestens ein Nichtterminalsymbol enthalten sein muss. Weiterhin wird gefordert, dass die linke Seite nicht länger sein darf als die rechte Seite.

Somit sind folgende Produktionsregeln denkbar, die weder regulär noch kontextfrei sind:

      AB -> BA
      aB -> aa
      bB -> bb
      etc.
            
Beispiel a^n b^n b^n
Ein Wort einer Sprache sei so definiert, dass es aus einer Folge von a, b und c besteht, diese aber immer in gleicher Anzahl vorkommen müssen. Beispiele sind abc, aabbcc, nicht jedoch abbc oder aabbc.

      S -> aSBC
      S -> aBC
      CB -> BC
      aB -> ab
      bB -> bb
      bC -> bc
      cC -> cc
            
Die Regeln wurden dem Buch Vossen/Witt: Grundlagen der theoretischen Informatik entnommen.