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

Bearbeiten

Formal ist eine monotone Grammatik definiert als 4-Tupel   mit

  • einer endlichen Menge V, genannt Vokabular (Symbolmenge),
  • Terminalsymbolen   (Alphabet),
  • Nichtterminalsymbolen     (Metasymbole, Variablen)
  • Produktionsregeln  , für die gilt:
    Für jede Regel   ist  , d. h.   ist nicht länger als  .
  • einem Startsymbol   (auch Startvariable genannt).

Manche Autoren benutzen alternativ das Quadrupel   zur Kennzeichnung einer Grammatik  .

Erlaubt man für monotone Grammatiken zusätzlich die Ausnahmeregel  , sofern   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

Bearbeiten

Die Grammatik   mit  ,    ,      und  :

 

erzeugt die Sprache  .

Literatur

Bearbeiten
  • 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)