GCSL

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 = (Σ,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 $(\alpha \rightarrow \beta) \in P$ ist, (also eine Regel von G) und $\alpha\not=S$, dann gilt:

• | α | < | β |

2. Streng monotone Grammatiken 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 $\mathbf{GCSL}$ geschrieben.

Charakterisierungen

• $\mathbf{GCSL}$ wird charakterisiert mit quasi streng monotonen Grammatiken.
• $\mathbf{GCSL}$ ist mit schrumpfenden Zweikellerautomaten (sTPDA) charakterisiert.
• $\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

Wir vergleichen $\mathbf{GCSL}$ mit

• $\mathbf{DGCSL}$, den deterministischen wachsenden kontextsensitiven Sprachen
• $\mathbf{CFL}$, den kontextfreien Sprachen
• $\mathbf{CSL}$, den kontextsensitiven Sprachen
• $\mathbf{DCFL}$, den deterministischen kontextfreien Sprachen
• $\mathbf{DCSL}$, den deterministischen kontextsensitiven Sprachen

• Echte Inklusionen:

• $\mathbf{CFL}\subset\mathbf{GCSL}\subset\mathbf{CSL}$
• $\mathbf{DCFL}\subset\mathbf{DGCSL}\subset\mathbf{DCSL}$
• $\mathbf{DGCSL}\subset\mathbf{GCSL}$

• $\mathbf{GCSL}$ ist abgeschlossen unter

• Vereinigung
• Durchschnittbildung mit regulären Sprachen
• Konkatenation
• Kleene-Stern
• ε-freien Homomorphismen
• inversen Homomorphismen

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

• Durchschnitt
• Homomorphismen