Wachsend kontextsensitive Sprache
Wachsend kontextsensitive Sprachen (englisch 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. Die Sprachklasse wurde 1986 definiert.[1]
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[2]
2002 zeigten Gundula Niemann und Jens Woinowski, dass GCSL mit der Klasse der azyklischen kontextsensitiven Sprachen übereinstimmt.[3]
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 heißt streng monotone Grammatik, wenn Folgendes gilt:
- Alle Regeln aus haben folgende Gestalt:
- Das Nichtterminal taucht nur auf der linken Seite von Regeln in auf
- Wenn ist (also eine Regel von ) und , dann gilt:
- Alle Regeln aus haben folgende Gestalt:
- Streng monotone Grammatiken heißen auch wachsend kontextsensitiv.
- Die Klasse der Sprachen, die von wachsend kontextsensitiven Grammatiken erzeugt werden, sind die 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
- -freien Homomorphismen
- inversen Homomorphismen
GCSL ist nicht abgeschlossen unter
Quellen
- ↑ 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.
- ↑ 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
- ↑ 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, doi:10.1007/3-540-46011-X_16
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
