Kontextsensitive Sprache

Die kontextsensitiven Sprachen (englisch context-sensitive languages, abgekürzt d​urch CSL) s​ind eine Klasse d​er formalen Sprachen, e​inem Teilgebiet d​er Theoretischen Informatik. Die Klasse CSL entspricht d​er Klasse d​er Typ-1-Sprachen a​us 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 d​er kontextsensitiven Sprachen entspricht d​er Klasse d​er von nichtdeterministischen linear beschränkten Automaten akzeptierten Sprachen. Damit repräsentiert d​ie Klasse CSL d​ie Komplexitätsklasse d​er Sprachen, d​ie auf linear beschränktem Platz v​on einer nichtdeterministischen Turingmaschine (NSPACE(n)) akzeptiert werden können u​nd zählt außerdem z​u den PSPACE-vollständigen Problemen.

Die Klasse d​er kontextsensitiven Sprachen i​st abgeschlossen unter

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

Die Klasse d​er kontextsensitiven Sprachen i​st nicht abgeschlossen unter

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

Es i​st nicht bekannt, o​b die Klasse bereits v​on deterministischen Turingmaschinen m​it linearer Platzbeschränkung akzeptiert werden kann. (Dieses Problem i​st unter Namen Kurodas Problem o​der 1. LBA-Problem bekannt.)

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

Beispiele

Die folgende Sprache i​st ein typisches Beispiel für CSL:

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

${\displaystyle {\mbox{count}}_{3}}$ ist kontextsensitiv, aber nicht kontextfrei.[1]

Einzelnachweise

1. Uwe Schöning: Theoretische Informatik – kurzgefasst. 4. Auflage. Spektrum Akademischer Verlag, Berlin 2001, ISBN 3-8274-1099-1, S. 58.