Wachsend kontextsensitive Sprache

Wachsend kontextsensitive Sprachen ({{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}}, 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. Die Sprachklasse wurde 1986 definiert.<ref>E. Dahlhaus und M. K. Warmuth: Membership for growing context-sensitive grammars is polynomial. In: Journal of Computer and System Sciences. Band 33, S. 456–472, 1986.</ref>

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 als fehlende Sprachklasse in der Chomsky-Hierarchie.<ref>Robert McNaughton: An Insertion into the Chomsky Hierarchy?. In: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa. S. 204–212, 1999</ref>

2002 zeigten Gundula Niemann und Jens Woinowski, dass GCSL mit der Klasse der azyklischen kontextsensitiven Sprachen übereinstimmt.<ref>Gundula Niemann, Jens R. Woinowski: The Growing Context-Sensitive Languages Are the Acyclic Context-Sensitive Languages. In: Developments in Language Theory. Lecture Notes in Computer Science, Band 2295, Seite 197–205, 2002, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}</ref>

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

Eine Grammatik <math>G = (\Sigma,T,S,P)</math> heißt streng monotone Grammatik, wenn Folgendes gilt:
- Alle Regeln aus <math>P</math> haben folgende Gestalt:
  - Das Nichtterminal <math>S</math> taucht nur auf der linken Seite von Regeln in <math>P</math> auf
  - Wenn <math>(\alpha \rightarrow \beta) \in P</math> ist (also eine Regel von <math>G</math>) und <math>\alpha\not=S</math>, dann gilt: <math>|\alpha|<|\beta|</math>
Streng monotone Grammatiken heißen auch wachsend kontextsensitiv.
Die Klasse der Sprachen, die von wachsend kontextsensitiven Grammatiken erzeugt werden, ist die Klasse der wachsend kontextsensitiven Sprachen.

Alternative Charakterisierungen

GCSL lässt sich auf verschiedene Arten beschreiben:

durch quasi streng monotone Grammatiken
durch schrumpfende Zweikellerautomaten (sTPDA)
durch azyklisch kontextsensitive Grammatiken

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

Eigenschaften

GCSL werden hier verglichen mit

DGCSL, den deterministischen wachsenden kontextsensitiven Sprachen
CFL, den kontextfreien Sprachen
CSL, den kontextsensitiven Sprachen (äquivalent den monotonen Grammatiken)
DCFL, den deterministischen kontextfreien Sprachen
DCSL, den deterministischen kontextsensitiven Sprachen

Echte Inklusionen:

CFL ⊊ GCSL ⊊ CSL
DCFL ⊊ DGCSL ⊊ DCSL
DGCSL ⊊ GCSL

GCSL ist abgeschlossen unter

Vereinigung
Durchschnittbildung mit regulären Sprachen
Konkatenation
Kleene-Stern
<math>\varepsilon</math>-freien Homomorphismen
inversen Homomorphismen

GCSL ist nicht abgeschlossen unter

Quellen

Literatur

Gerhard Buntrock und Krzysztof Lorys: On Growing Context-Sensitive Languages. In: Proceedings of the 19th International Colloquium on Automata, Languages and Programming. S. 77–88, 1992.
Gundula Niemann: Church-Rosser Languages and Related Classes. Dissertation, Univ. Kassel, ISBN 3-89958-002-8, 2002.

Weblinks

GCSL. In: Complexity Zoo. (englisch)
Growing Context-Sensitive Languages