Monotone Grammatik

Eine monotone Grammatik (auch nichtverkürzende Grammatik) ist eine formale Grammatik mit Produktionsregeln, deren rechte Seite nicht kürzer als die linke Seite ist. Ein Ableitungsschritt in einer monotonen Grammatik verkürzt nicht die abzuleitende Satzform.

Definition

Formal ist eine monotone Grammatik definiert als 4-Tupel $G = \left(N, T, P, S\right)$ mit

• Nichtterminalsymbole N
• Terminalsymbole T
  • Symbolmenge $\Sigma := N\cup T$
• Produktionen $P \subseteq \Sigma^+ \times \Sigma^+$, für die gilt:

  Für jede Regel $w_1 \mapsto w_2$ ist $\left|w_1\right|\leq \left|w_2\right|$, d.h. w₁ ist kürzer als w₂.

• Startsymbol $S \in N$

Erlaubt man für monotone Grammatiken die Ausnahmeregel $S \mapsto \varepsilon$, sofern S in keiner rechten Seite einer Regel vorkommt, so erzeugen die monotonen Grammatiken genau die kontextsensitiven Sprachen und sind somit äquivalent zu den kontextsensitiven Grammatiken.

Beispiel

Die Grammatik $G = \left(N, T, S, P\right)$ mit $N = \left\{S, B\right\}$, $T = \left\{a, b, c\right\}$ und P:

$\begin{align}S &\mapsto aSBc\\ S &\mapsto abc\\ cB &\mapsto Bc\\ bB &\mapsto bb\end{align}$

erzeugt die Sprache $L = \left\{a^n b^n c^n \mid n \geq 1\right\}$

Literatur

• Carlos Martín Vide, Victor Mitrana, Gheorghe Păun (Hrsg.): Formal languages and applications. (Studies in Fuzziness and Soft Computing Vol. 148), Springer, Heidelberg u. a. 2004, ISBN 3-540-20907-7 (Eingeschränkte Vorschau in der Google Buchsuche)