Die kontextsensitiven Sprachen (engl. Context Sensitive Languages abgekürzt durch CSL) sind eine Klasse der formalen Sprachen, einem Teilgebiet der Theoretischen Informatik. Die Klasse CSL entspricht der Klasse der Typ-1-Sprachen aus der Chomsky-Hierarchie.

Definition

---

Eine formale Sprache ist genau dann kontextsensitiv, wenn eine kontextsensitive Grammatik existiert, die diese Sprache erzeugt. Eine kontextsensitive Grammatik ist eine, die in jeder Regel immer ein Nichtterminal in einem Kontext in eine nichtleere Folge von Zeichen (Nichtterminale oder Terminale) ersetzt. Die monotonen Grammatiken sind den kontextsensitiven äquivalent, sie charakterisieren die kontextsensitiven Sprachen. Eine Grammatik heißt monoton, wenn alle ihre Regeln die Eigenschaft haben, dass die rechte Seite einer jeden Regel mindestens so lang ist wie deren linke Seite.

Eigenschaften

---

Die Klasse der kontextsensitiven Sprachen (CSL) entspricht der Klasse der von nichtdeterministischen linear beschränkten Automaten akzeptierten Sprachen. Damit repräsentiert die Klasse CSL die Komplexitätsklasse der Sprachen, die auf linearem Platz von einer nichtdeterministischen Turingmaschine (NSPACE(n)) akzeptiert werden können.

Die Klasse der kontextsensitiven Sprachen ist abgeschlossen unter

• Vereinigung,
• Konkatenation,
• Komplementbildung,
• Durchschnitt
• Kleene-Operation *
• Inverse Homomorphismen
• $\backslash varepsilon$-freie Homomorphismen
• logarithmisch platzbeschränkter Reduktion

Die Klasse der kontextsensitiven Sprachen ist nicht abgeschlossen unter

• löschenden Homomorphismen
• logarithmisch platzbeschränkter Reduktion
• polynomiell zeitbeschränkter Reduktion

Nicht bekannt ist,

• ob die Klasse bereits von deterministischen Turingmaschinen mit linearer Platzbeschränkung akzeptiert werden können. (Dieses Problem ist unter Namen Kurodas Problem bekannt.)

Beispiele

---

Die folgende Sprache ist ein typisches Beispiel für CSL:

• $\backslash mbox\{count\}\_3:=\backslash \{a^nb^nc^n|n\backslash in\backslash mathbb\{N\}\backslash \}$

KomplexitätstheorieFormale Sprachen

Kontextový jazyk | Context-sensitive language | Linguaggio sensibile al contesto | 文脈依存言語 | Język kontekstowy