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.

Inhaltsverzeichnis

1 Definition
2 Eigenschaften
3 Beispiele
4 Siehe auch

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
$\varepsilon$ -freie Homomorphismen
logarithmisch platzbeschränkter Reduktion

Die Klasse der kontextsensitiven Sprachen ist nicht abgeschlossen unter

löschenden Homomorphismen
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:

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

Siehe auch

Automatentheorie: Formale Sprachen und Formale Grammatiken
Chomsky- Hierarchie	Grammatiken	Sprachen	Minimaler Automat
Typ-0	uneingeschränkt	rekursiv aufzählbar	Turingmaschine
	uneingeschränkt	rekursiv	Turingmaschine
Typ-1	kontextsensitiv	kontextsensitiv	linear beschränkt
Typ-2	kontextfrei	kontextfrei	Kellerautomat
Typ-3	Regulär	Regulär	Endlich
Jede Klasse einer Sprache oder Grammatik ist eine echte Teilmenge der Klasse darüber.