Monotone Grammatik

Eine monotone Grammatik (auch nichtverkürzende Grammatik, beschränkte Grammatik oder expansive Grammatik) ist eine formale Grammatik, die nur Produktionsregeln enthält, 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 ${\displaystyle G=\left(V,T,P,S\right)}$ mit

• einer endlichen Menge V, genannt Vokabular (Symbolmenge),
• Terminalsymbolen ${\displaystyle T\subset V}$ (Alphabet),
• Nichtterminalsymbolen ${\displaystyle N=}$ ${\displaystyle V\setminus {T}}$ (Metasymbole, Variablen)
• Produktionsregeln ${\displaystyle P\subseteq V^{+}\times V^{+}}$, für die gilt:

  Für jede Regel ${\displaystyle w_{1}\to w_{2}}$ ist ${\displaystyle \left|w_{1}\right|\leq \left|w_{2}\right|}$, d. h. ${\displaystyle w_{1}}$ ist nicht länger als ${\displaystyle w_{2}}$.

• einem Startsymbol ${\displaystyle S\in N}$ (auch Startvariable genannt).

Manche Autoren benutzen alternativ das Quadrupel ${\displaystyle (N,T,P,S)}$ zur Kennzeichnung einer Grammatik ${\displaystyle G}$.

Erlaubt man für monotone Grammatiken zusätzlich die Ausnahmeregel ${\displaystyle S\to \varepsilon }$, sofern ${\displaystyle 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 ${\displaystyle G=\left(V,T,S,P\right)}$ mit ${\displaystyle V=N\cup T}$,   ${\displaystyle N=\left\{S,B\right\}}$,   ${\displaystyle T=\left\{a,b,c\right\}}$  und ${\displaystyle P}$:

${\displaystyle {\begin{alignedat}{2}S&&{}\to {}&aSBc\\S&&{}\to {}&abc\\cB&&{}\to {}&Bc\\bB&&{}\to {}&bb\end{alignedat}}}$

erzeugt die Sprache ${\displaystyle 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)