Kontextsensitive Sprache

Die kontextsensitiven Sprachen (englisch 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 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 linear beschränktem Platz von einer nichtdeterministischen Turingmaschine (NSPACE(n)) akzeptiert werden können und zählt außerdem zu den PSPACE-vollständigen Problemen.

Die Klasse der kontextsensitiven Sprachen ist abgeschlossen unter

• Vereinigung,
• Konkatenation,
• Komplementbildung,
• Durchschnitt,
• Kleene-Operation *,
• inversen Homomorphismen,
• $\varepsilon$-freien Homomorphismen,
• logarithmisch platzbeschränkter Reduktion.

Die Klasse der kontextsensitiven Sprachen ist nicht abgeschlossen unter

• löschenden Homomorphismen,
• polynomiell zeitbeschränkter Reduktion.

Es ist nicht bekannt, ob die Klasse bereits von deterministischen Turingmaschinen mit linearer Platzbeschränkung akzeptiert werden kann. (Dieses Problem ist unter Namen Kurodas Problem oder 1. LBA-Problem bekannt.)

Da die Ableitungen niemals kürzer werden, ist auch $x\in L$ (Wortproblem), mit L kontextsensitive Sprache, entscheidbar.

Beispiele

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

${\mbox{count}}_{3}:=\{a^{n}b^{n}c^{n}\mid n\in \mathbb {N} \}$

${\mbox{count}}_{3}$ ist kontextsensitiv, aber nicht kontextfrei.