Wachsend kontextsensitive Sprache

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

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.

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
• ${\displaystyle \varepsilon }$-freien Homomorphismen
• inversen Homomorphismen

GCSL ist nicht abgeschlossen unter

• Durchschnitt
• Homomorphismen