- 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.
Inhaltsverzeichnis
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
ist, (also eine Regel von G) und
, 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
geschrieben.
Charakterisierungen
wird charakterisiert mit quasi streng monotonen Grammatiken.
ist mit schrumpfenden Zweikellerautomaten (sTPDA) charakterisiert.
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
mit
-
, den deterministischen wachsenden kontextsensitiven Sprachen
, den kontextfreien Sprachen
, den kontextsensitiven Sprachen
, den deterministischen kontextfreien Sprachen
, den deterministischen kontextsensitiven Sprachen
- Echte Inklusionen:
ist abgeschlossen unter
-
- Vereinigung
- Durchschnittbildung mit regulären Sprachen
- Konkatenation
- Kleene-Stern
- ε-freien Homomorphismen
- inversen Homomorphismen
ist nicht abgeschlossen unter
Wikimedia Foundation.