Wikipedia · einfach zusammengefasst · Stand
Kontextsensitive Sprache
Die kontextsensitiven Sprachen (englisch context-sensitive languages, abgekürzt durch CSL) sind eine Klasse der formalen Sprachen, einem Teilgebiet der …
Inhalt5 Abschnitte
Kernidee und Einordnung
Kontextsensitive Sprachen (englisch context-sensitive languages, CSL) sind eine Klasse formaler Sprachen in der Theoretischen Informatik. In der Chomsky-Hierarchie entsprechen sie genau den Typ-1-Sprachen.
Definition durch Grammatiken
Eine formale Sprache heißt genau dann kontextsensitiv, wenn es eine kontextsensitive Grammatik gibt, die diese Sprache erzeugt.
Bei einer kontextsensitiven Grammatik ersetzt jede Regel ein Nichtterminal innerhalb eines Kontextes durch eine nichtleere Folge aus Nichtterminalen oder Terminalen. Nichtterminale sind Zeichen, die im Verlauf einer Ableitung weiter ersetzt werden können; Terminale bilden schließlich die Wörter der Sprache.
Äquivalent dazu können kontextsensitive Sprachen durch monotone Grammatiken charakterisiert werden. Eine Grammatik heißt monoton, wenn bei jeder Regel die rechte Seite mindestens so lang wie die linke Seite ist. Eine Ableitung kann ein erzeugtes Wort daher niemals verkürzen.
Automaten und Berechnungskomplexität
Die kontextsensitiven Sprachen sind genau die Sprachen, die von nichtdeterministischen linear beschränkten Automaten akzeptiert werden. Ein solcher Automat ist eine Turingmaschine, deren verfügbarer Speicherplatz höchstens linear mit der Länge der Eingabe wächst.
Damit repräsentiert CSL die Komplexitätsklasse NSPACE(n): die Sprachen, die eine nichtdeterministische Turingmaschine mit linear beschränktem Speicherplatz akzeptieren kann. Die Klasse zählt außerdem zu den PSPACE-vollständigen Problemen.
Ungeklärt ist, ob bereits deterministische Turingmaschinen mit linearer Platzbeschränkung alle kontextsensitiven Sprachen akzeptieren können. Diese offene Frage heißt Kurodas Problem oder 1. LBA-Problem.
Weil Ableitungen niemals kürzer werden, ist das Wortproblem entscheidbar: Für eine kontextsensitive Sprache L und ein Wort x lässt sich also durch ein Verfahren mit sicherem Ende feststellen, ob x ∈ L gilt.
Abschlusseigenschaften
Die Klasse der kontextsensitiven Sprachen ist abgeschlossen unter folgenden Operationen: Wendet man eine davon auf passende kontextsensitive Sprachen an, entsteht wieder eine kontextsensitive Sprache.
- Vereinigung
- Konkatenation
- Komplementbildung
- Durchschnitt
- Kleene-Operation *
- inverse Homomorphismen
- ε-freie Homomorphismen
- logarithmisch platzbeschränkte Reduktion
Nicht abgeschlossen ist die Klasse unter löschenden Homomorphismen und unter polynomiell zeitbeschränkter Reduktion.
Typisches Beispiel
Ein typisches Beispiel ist
count₃ := {aⁿbⁿcⁿ | n ∈ ℕ}.
Die Sprache enthält somit Wörter mit jeweils gleich vielen aufeinanderfolgenden Zeichen a, b und c. count₃ ist kontextsensitiv, aber nicht kontextfrei.
