Kontextsensitive Grammatik

Grundidee und Einordnung

Kontextsensitive Grammatiken (CSG, englisch context-sensitive grammar) sind formale Grammatiken der Chomsky-Hierarchie. Sie sind genau die Typ-1-Grammatiken. Ihr entscheidendes Merkmal ist: Ein Nichtterminalsymbol darf nur ersetzt werden, wenn es in einem vorgegebenen Kontext steht. Damit beschreiben sie Sprachen, für deren Bildung nicht nur ein einzelnes Symbol, sondern auch seine Umgebung wichtig sein kann.

Formale Definition und Regeln

Eine kontextsensitive Grammatik ist eine Grammatik G=(V,T,P,S). Dabei ist V ein endliches Vokabular, T\subset V die Menge der Terminalsymbole und N=V\setminus T die Menge der Nichtterminalsymbole. S\in N ist das Startsymbol, P ist die Menge der Produktionsregeln. Manche Autoren schreiben statt dessen G=(N,T,P,S).

Die Regeln haben die Form \alpha X\beta \rightarrow \alpha\gamma\beta, wobei \alpha,\beta\in V^*, X\in N und \gamma\in V^+ gilt. X wird also zwischen dem linken Kontext \alpha und dem rechten Kontext \beta durch \gamma ersetzt. \gamma enthält mindestens ein Terminal- oder Nichtterminalsymbol; \alpha und \beta dürfen dagegen leer sein. Dadurch sind auch \alpha X\rightarrow\alpha\gamma, X\beta\rightarrow\gamma\beta und X\rightarrow\gamma möglich.

Als einzige Ausnahme ist S\rightarrow\varepsilon erlaubt, damit das leere Wort erzeugt werden kann. Dann darf S auf keiner rechten Seite einer Produktionsregel vorkommen. Durch diese Ausnahme sind kontextsensitive Sprachen eine echte Obermenge der kontextfreien Sprachen.

Monotonie und Normalformen

Abgesehen von S\rightarrow\varepsilon verkürzt keine Regel die linke Seite: Für jede Regel w_1\rightarrow w_2 gilt |w_1|\leq|w_2|. Daher ist jede kontextsensitive Grammatik, bis auf die Ausnahme für das leere Wort, auch monoton. Kontextsensitive und monotone Grammatiken erzeugen jedoch dieselbe Sprachklasse. Einige Autoren definieren kontextsensitive Grammatiken deshalb unmittelbar als monotone Grammatiken.

Zu jeder kontextsensitiven Grammatik gibt es eine Grammatik in Kuroda-Normalform. Ihre Regeln haben eine der Formen A\rightarrow a, A\rightarrow B, A\rightarrow BC oder AB\rightarrow CD. Eine Grammatik in Kuroda-Normalform ist im Allgemeinen monoton, aber nicht mehr kontextsensitiv.

Eine kontextsensitive Normalform ist die einseitige Normalform. Sie verwendet Regeln der Art A\rightarrow a, A\rightarrow BC und AB\rightarrow AC. Auch zu jeder kontextsensitiven Grammatik existiert eine Grammatik in dieser Normalform.

Alternative Schreibweise und erzeugte Sprachen

In der Sprachwissenschaft wird der Kontext einer Regel häufig am rechten Ende notiert: X\rightarrow\gamma\;/\alpha\_\_\_\_\beta/. Die Regel besagt ebenfalls, dass X nur im Kontext \alpha und \beta durch \gamma ersetzt werden darf.

Kontextsensitive Grammatiken erzeugen genau die kontextsensitiven Sprachen: Jede solche Grammatik erzeugt eine kontextsensitive Sprache, und für jede kontextsensitive Sprache gibt es eine entsprechende Grammatik.

Dies sind genau die Sprachen, die eine nichtdeterministische, linear beschränkte Turingmaschine erkennen kann. Ihr Band ist durch die Eingabelänge begrenzt: Es gibt eine Konstante a, sodass die Maschine höchstens a\cdot x Bandfelder besitzt, wenn x die Länge des Eingabewortes ist. Deshalb ist das Wortproblem für kontextsensitive Sprachen entscheidbar: Es kann entschieden werden, ob x\in L gilt.