imported>UKoch: /* Definitionen */ Formulierung, Zeichensetzung

2024-07-23T15:45:56Z

Definitionen: Formulierung, Zeichensetzung

Neue Seite

'''Wachsend kontextsensitive Sprachen''' ({{enS|Growing Context Sensitive Languages}}, abgekürzt: '''GCSL''') sind ein Begriff aus der [[Formale Sprache|Theorie der Formalen Sprachen]], einem Teilgebiet der [[Theoretische Informatik|Theoretischen Informatik]]. Eine wachsend kontextsensitive Sprache wird mit [[Formale Grammatik|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: [http://www.sciencedirect.com/science/article/pii/0022000086900620/pdf?md5=b050cd8c37d8e2f3ce0183c85c53e2a8&pid=1-s2.0-0022000086900620-main.pdf ''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 [[Kontextfreie Sprache|kontextfreien Sprachen]] dar, bleibt aber eine Teilklasse von [[P (Komplexitätsklasse)|'''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, {{DOI|10.1007/3-540-46011-X_16}}</ref>

Analog zu den [[Deterministisch kontextfreie Sprache|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-Sprache]]n übereinstimmt.

== Definitionen ==
# Eine [[Formale Grammatik|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 [[Zweikellerautomat]]en (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 [[Deterministisch wachsende kontextsensitive Sprache|deterministischen wachsenden kontextsensitiven Sprachen]]
* CFL, den [[Kontextfreie Sprache|kontextfreien Sprachen]]
* CSL, den [[Kontextsensitive Sprache|kontextsensitiven Sprachen]] (äquivalent den [[Monotone Grammatik|monotonen Grammatiken]])
* DCFL, den [[Deterministisch kontextfreie Sprache|deterministischen kontextfreien Sprachen]]
* DCSL, den [[Deterministisch kontextsensitive Sprache|deterministischen kontextsensitiven Sprachen]]

Echte Inklusionen:
* CFL ⊊ GCSL ⊊ CSL
* DCFL ⊊ DGCSL ⊊ DCSL
* DGCSL ⊊ GCSL

GCSL ist [[Hüllenoperator|abgeschlossen]] unter
* [[Menge (Mathematik)#Vereinigung (Vereinigungsmenge)|Vereinigung]]
* Durchschnittbildung mit [[Reguläre Sprache|regulären Sprachen]]
* [[Konkatenation (Formale Sprache)|Konkatenation]]
* [[Kleene-Stern]]
* <math>\varepsilon</math>-[[Homomorphismus|freien Homomorphismen]]
* [[Homomorphismus|inversen Homomorphismen]]

GCSL ist nicht abgeschlossen unter
* [[Schnittmenge|Durchschnitt]]
* [[Homomorphismus|Homomorphismen]]

== Quellen ==
<references />

== 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: [http://www.uni-kassel.de/upress/online/frei/978-3-89958-002-0.volltext.frei.pdf ''Church-Rosser Languages and Related Classes'']. Dissertation, Univ. Kassel, ISBN 3-89958-002-8, 2002.

== Weblinks ==
* {{Complexity Zoo|GCSL|G#gcsl}}
* [http://www.tcs.uni-luebeck.de/en/mitarbeiter/buntrock/gcsl.html ''Growing Context-Sensitive Languages'']

[[Kategorie:Theorie formaler Sprachen]]

Wachsend kontextsensitive Sprache - Versionsgeschichte

imported>UKoch: /* Definitionen */ Formulierung, Zeichensetzung