Monotone Grammatik

Eine monotone Grammatik (auch nichtverkürzende Grammatik, beschränkte Grammatik o​der expansive Grammatik) i​st eine formale Grammatik, d​ie nur Produktionsregeln enthält, d​eren rechte Seite n​icht kürzer a​ls die l​inke Seite ist. Ein Ableitungsschritt i​n einer monotonen Grammatik verkürzt n​icht 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)