Rechtslineare Grammatik

Rechtslineare Grammatik

In der theoretischen Informatik werden formale Grammatiken vom Typ 3 der Chomsky-Hierarchie auch reguläre Grammatiken genannt. Die von diesen Grammatiken erzeugbaren Sprachen heißen dementsprechend reguläre Sprachen.[1]

Definition

Eine reguläre Grammatik G = \left(N,\Sigma,P,S\right) ist eine kontextfreie Grammatik, deren Produktionsregeln weiter eingeschränkt sind. Es gibt rechtsreguläre und linksreguläre Grammatiken, wobei normalerweise mit „regulär“ die rechtsregulären Grammatiken gemeint sind.[2]

Die rechte Seite einer Produktion w2 darf für rechtsreguläre Sprachen nur ein Terminalsymbol oder ein Terminal gefolgt von einem Nichtterminal sein. D.h. ein Wort einer solchen regulären Sprache entsteht durch Anfügen von Terminalsymbolen auf der rechten Seite. Entsprechend gilt für linksreguläre Sprachen, dass die rechte Seite w2 nur ein Terminal oder ein Nichtterminal gefolgt von einem Terminal sein darf.

Für die Produktionen P einer rechtsregulären Grammatik G \in \mbox{Typ}_3 gilt

\forall \left(w_1 \rightarrow w_2\right) \in P : \left(w_1 \in N\right) \and \left(w_2 \in \Sigma \cup \Sigma N\right)

Gültige Produktionen einer regulären Grammatik wären beispielsweise:


    \begin{matrix}
        A \rightarrow & aA & \quad \mathrm{(f\ddot{u}r \ rechtsregul\ddot{a}r)} \\
        A \rightarrow & Aa & \quad \mathrm{(f\ddot{u}r \ linksregul\ddot{a}r)}  \\
        A \rightarrow & a  & \quad A \in N, a \in \Sigma
    \end{matrix}

Von G erzeugte Sprache

Die regulären Grammatiken erzeugen die regulären Sprachen. Das heißt jeder regulären Grammatik lässt sich eine reguläre Sprache und umgekehrt zuordnen.

Diese Sprachen sind abgeschlossen unter Komplementbildung, Konkatenation, Schnitt, Vereinigung und Kleenescher Abschluss. Die regulären Sprachen sind die Sprachen, die von einem endlichen Automaten (deterministisch oder nichtdeterministisch) erkannt werden können.

Rechtsreguläre und linksreguläre Grammatiken erzeugen dieselbe Menge von formalen Sprachen, das heißt, zu jeder linksregulären Grammatik gibt es eine rechtsreguläre Grammatik, die dieselbe Sprache erzeugt und umgekehrt.

Quellen

  1. Lutz Engelmann (Hrsg.): Kleiner Leitfaden Informatik und ihre Anwendung. paetec, Berlin 2000, ISBN 3-89517-615-X.
  2. Peter Rechenberg, Gustav Pomberg (Hrsg.): Informatik-Handbuch. Hanser, München/Wien 2006, ISBN 978-3-446-40185-3.

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

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

  • 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

  • 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

  • Typ-1-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

  • Typ-2-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

  • Typ-3-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”