Kontextsensitive Sprache
aus Wikipedia, der freien Enzyklopädie
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.
[Bearbeiten] 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.
[Bearbeiten] 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
-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.)
[Bearbeiten] Beispiele
Die folgende Sprache ist ein typisches Beispiel für CSL:
