Wachsend kontextsensitive Sprache

27. Jun 2007, 11:25

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.

[Bearbeiten] 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 $(\alpha \rightarrow \beta) \in P$ ist, (also eine Regel von $G$ ) und $\alpha\not=S$ , 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 $\mathbf{GCSL}$ geschrieben.

[Bearbeiten] Charakterisierungen

$\mathbf{GCSL}$ wird charakterisiert mit quasi streng monotonen Grammatiken.
$\mathbf{GCSL}$ ist mit schrumpfenden Zweikellerautomaten (sTPDA) charakterisiert.
$\mathbf{GCSL}$ ist charakterisiert mit azyklischen kontextsensitiven Grammatiken.

[Bearbeiten] Definition DGCSL

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