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 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

Die Grammatik mit ,   ,    und :

erzeugt die Sprache .

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)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.