Die kontextsensitiven Grammatiken sind eine Klasse formaler Grammatiken und identisch mit den Typ-1-Grammatiken der Chomsky-Hierarchie.

Definition

---

Eine formale Grammatik $G$ ist kontextsensitiv (Typ-1), wenn für jede Produktionsregel $w\_1\; \backslash rightarrow\; w\_2$ gilt: $\backslash left|\; w\_1\; \backslash right|\; \backslash le\; \backslash left|\; w\_2\; \backslash right|$. Weniger formal bedeutet das: alle rechten Regelseiten sind nicht kürzer als die zugehörigen linken Regelseiten.

Man schreibt $G\; \backslash in\; \backslash mbox\{Typ\}\_1$.

Im Gegensatz zu kontextfreien Grammatiken kann die Anzahl der Symbole auf der linken Regelseite auch größer als 1 sein.

Typ-1-Grammatiken besitzen Regeln der Form $\backslash alpha\; A\; \backslash beta\; \backslash rightarrow\; \backslash alpha\; x\; \backslash beta$, wobei $A$ ein Nichtterminal und $\backslash alpha,\; \backslash beta,\; x$ Wörter bestehend aus Terminalen ($\backslash Sigma$) und Nichtterminalen ($N$) sind. Die Wörter $\backslash alpha$ und $\backslash beta$ können leer sein, aber $x$ muss mindestens ein Symbol (also ein Terminal oder ein Nichtterminal) enthalten.

An diesem Beispiel kann auch die Bezeichnung kontextsensitiv erklärt werden. Durch Regeln der Form $\backslash alpha\; A\; \backslash beta\; \backslash rightarrow\; \backslash alpha\; x\; \backslash beta$ ist es möglich die Variable $A$ durch $x$ zu ersetzen aber nur dann, wenn $A$ in einem bestimmten Kontext also hier zwischen $\backslash alpha$ und $\backslash beta$ steht.

Einzige Ausnahme zu obiger Form bildet die Regel $S\; \backslash rightarrow\; \backslash varepsilon$, die eventuell benötigt wird, das leere Wort $\backslash varepsilon$ abzuleiten. Sie darf aber nur dann verwendet werden, wenn das Startsymbol $S$ auf keiner rechten Regelseite vorkommt.

Von $G$ erzeugte Sprache

---

Mit Hilfe kontextsensitiver Grammatiken lassen sich genau die kontextsensitiven Sprachen erzeugen. D.h. jede Typ-1-Grammatik erzeugt eine kontextsensitive Sprache und zu jeder kontextsensitiven Sprache existiert eine Typ-1-Grammatik, die diese erzeugt.

Die kontextsensitiven Sprachen sind genau die Sprachen, die von einer nichtdeterministischen, linear beschränkten Turingmaschine erkannt werden können; d.h. von einer nichtdeterministischen Turing-Maschine, deren Band linear durch die Länge der Eingabe beschränkt ist (d.h. es gibt eine konstante Zahl $a$ so dass das Band der Turing-Maschine höchstens $a\; \backslash cdot\; x$ Felder besitzt, wobei $x$ die Länge des Eingabewortes ist).

Grammatik

Kontextová gramatika | Context-sensitive grammar | Gramáticas sensibles al contexto | Grammatica sensibile al contesto | 文脈依存文法 | Gramáticas sensíveis ao contexto | Kontextovo citlivá gramatika