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.

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.

2002 zeigten Gundula Niemann und Jens Woinowski, dass GCSL mit der Klasse der azyklischen kontextsensitiven Sprachen übereinstimmt.

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.

1. ↑ 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.
2. ↑ 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
3. ↑ 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