Monotone Grammatik

Monotone Grammatik

Eine monotone Grammatik (auch nichtverkürzende Grammatik) ist eine formale Grammatik mit Produktionsregeln, 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 G = \left(N, T, P, S\right) mit

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

\begin{align}S &\mapsto aSBc\\
S &\mapsto abc\\
cB &\mapsto Bc\\
bB &\mapsto bb\end{align}

erzeugt die Sprache L = \left\{a^n b^n c^n \mid n \geq 1\right\}

Literatur


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kontextsensitive Grammatik — Die kontextsensitiven Grammatiken (kurz CSG, von engl. context sensitive grammar) sind eine Klasse formaler Grammatiken und identisch mit den Typ 1 Grammatiken der Chomsky Hierarchie. Sie zeichnen sich dadurch aus, dass einzelne… …   Deutsch Wikipedia

  • Kontext-sensitive Grammatik — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Typ-0-Grammatik — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Formale Grammatik — Formale Grammatiken sind mathematische Modelle von Grammatiken, die mit Hilfe des Semi Thue Systems angegeben werden und durch die formale Sprachen beschrieben und erzeugt werden können. Sie werden in der theoretischen Informatik, insbesondere in …   Deutsch Wikipedia

  • Tripel-Graph-Grammatik — Als Tripel Graph Grammatik (engl. triple graph grammar, kurz: TGG) bezeichnet man eine spezielle Art von Graphgrammatik, die vor allem für bidirektionale Modell zu Modell Transformationen verwendet wird. Besonderheit von Tripel Graph Grammatiken… …   Deutsch Wikipedia

  • Chomsky-Hierarchie — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der Theoretischen Informatik. Sie ist eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Chomsky-Typ — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Chomsky Hierarchie — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Chomskyhierarchie — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Typ-0-Sprache — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”