Monotone Grammatik

2018-12-18T00:11:02Z

2.203.190.224: Korrektur der Definition der Produktionsregeln.

Eine '''monotone Grammatik''' (auch '''nichtverkürzende Grammatik''', '''beschränkte Grammatik''' oder '''expansive Grammatik''') ist eine [[formale Grammatik]], die nur [[Produktionsregel]]n enthält, deren rechte Seite nicht kürzer als die linke Seite ist. Ein [[Ableitung (Informatik)|Ableitungsschritt]] in einer monotonen Grammatik verkürzt nicht die abzuleitende Satzform.

== Definition ==
Formal ist eine monotone Grammatik definiert als 4-Tupel <math>G = \left(V, T, P, S\right)</math> mit
* einer endlichen Menge V, genannt ''Vokabular'' (''Symbolmenge''),
* [[Terminalsymbol]]en <math>T \subset V</math> (''Alphabet''),
* [[Nichtterminalsymbol]]en <math>N =</math> [[Differenzmenge|<math>V\setminus{T}</math>]] (''Metasymbole'', ''Variablen'')
* [[Produktionsregel]]n <math>P \subseteq V^+ \times V^+</math>, für die gilt:
*:Für jede Regel <math>w_1 \to w_2</math> ist <math>\left|w_1\right|\leq \left|w_2\right|</math>, d. h. <math>w_1</math> ist nicht länger als <math>w_2</math>.
* einem ''Startsymbol'' <math>S \in N</math> (auch ''Startvariable'' genannt).

Manche Autoren benutzen alternativ das Quadrupel <math>(N, T, P, S)</math> zur Kennzeichnung einer Grammatik <math>G</math>.

Erlaubt man für monotone Grammatiken zusätzlich die Ausnahmeregel <math>S \to \varepsilon</math>, sofern <math>S</math> in keiner rechten Seite einer Regel vorkommt, so erzeugen die monotonen Grammatiken genau die [[Kontextsensitive Sprache|kontextsensitiven Sprachen]] und sind somit äquivalent zu den [[Kontextsensitive Grammatik|kontextsensitiven Grammatiken]].

== Beispiel ==
Die Grammatik <math>G = \left(V, T, S, P\right)</math> mit <math>V = N \cup T</math>,   <math>N = \left\{S, B\right\}</math>,   <math>T = \left\{a, b, c\right\}</math>  und <math>P</math>:
:<math>\begin{alignat}{2}S &&{}\to{}& aSBc\\
S &&{}\to{}& abc\\
cB &&{}\to{}& Bc\\
bB &&{}\to{}& bb\end{alignat}</math>
erzeugt die Sprache <math>L = \left\{a^n b^n c^n \mid n \geq 1\right\}</math>.

== 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 ({{Google Buch|BuchID=Qc9s48Kv-Y4C}})

[[Kategorie:Theorie formaler Sprachen]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

Monotone Grammatik