Wachsend kontextsensitive Sprachen (engl.: Growing Context Sensitive Languages, abgekürzt: GCSL) sind ein Begriff aus der Theorie der Formalen Sprachen, einem Teilgebiet der Theoretischen Informatik. Eine wachsend kontextsensitive Sprache wird mit formalen Grammatiken definiert, deren Regeln die folgende Eigenschaft haben: Die rechte Seite ist stets länger als die linke. Diese Sprachklasse hat in der Theorie folgende Bedeutung: Sie stellt eine echte Erweiterung der Klasse der kontextfreien Sprachen dar, bleibt aber eine Teilklasse von P. Robert McNaughton würdigte diese Klasse einmal mit dem Titel einer Arbeit: Hat Noam Chomsky eine Sprachklasse vergessen?

Analog zu den deterministisch kontextfreien Sprachen werden auch die deterministisch wachsend kontextsensitiven Sprachen definiert: Die deterministische Variante des charakterisierenden Automaten wird hier als Definition gewählt. Hier ist bekannt, dass diese Klasse mit den Church-Rosser-Sprachen übereinstimmt.

Definitionen

---

1. Eine Grammatik $G\; =\; (\backslash Sigma,T,S,P)$ heißt streng monotone Grammatik, wenn folgendes gilt:

• Alle Regeln aus $P$ haben folgende Gestalt:

• Das Nichtterminal $S$ taucht nur auf der linken Seite der Regel in $P$ auf

• Wenn $(\backslash alpha\; \backslash rightarrow\; \backslash beta)\; \backslash in\; P$ ist, (also eine Regel von $G$) und $\backslash alpha\backslash not=S$, dann gilt:

2. Streng monotone Gramatiken heißen auch wachsend kontextsensitiv

3. Die Klasse der Sprachen die von wachsend kontextsensitiven Grammatiken erzeugt werden, sind die wachsend kontextsensitiven Sprachen. Als Formelzeichen wird $\backslash mathbf\{GCSL\}$ geschrieben.

Charakterisierungen

---

• $\backslash mathbf\{GCSL\}$ wird charakterisiert mit quasi streng monotonen Grammatiken.
• $\backslash mathbf\{GCSL\}$ ist mit schrumpfenden Zweikellerautomaten (sTPDA) charakterisiert.
• $\backslash mathbf\{GCSL\}$ ist charakterisiert mit azyklischen kontextsensitiven Grammatiken.

Definition DGCSL

---

Alle Sprachen, die von einem deterministischen schrumpfenden Zweikellerautomaten akzeptiert werden, heißen deterministisch wachsend kontextsensitiv.

Eigenschaften

---

• Echte Inklusionen:

• $\backslash mathbf\{CFL\}\backslash subset\backslash mathbf\{GCSL\}\backslash subset\backslash mathbf\{CSL\}$

• $\backslash mathbf\{DCFL\}\backslash subset\backslash mathbf\{DGCSL\}\backslash subset\backslash mathbf\{DCSL\}$
• $\backslash mathbf\{DGCSL\}\backslash subset\backslash mathbf\{GCSL\}$

• $\backslash mathbf\{GCSL\}$ ist abgeschlossen unter

• Vereinigung

• Durchschnittbildung mit regulären Sprachen
• Konkatenation
• Kleene-Stern
• $\backslash epsilon$-freien Homomorphismen
• inversen Homomorphismen
  • $\backslash mathbf\{GCSL\}$ ist nicht abgeschlossen unter

• Durchschnitt

• Homomorphismen

formale Sprachen