Die regulären Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ-3-Grammatiken der Chomsky-Hierarchie.

Definition

---

Eine reguläre Grammatik $G\; =\; (N,\backslash Sigma,P,S)$ ist eine kontextfreie Grammatik, deren Produktionsregeln weiter eingeschränkt sind. Es gibt rechtsreguläre als auch linksreguläre Grammatiken, wobei normalerweise mit regulär die rechtsregulären Grammatiken gemeint sind.

Die rechte Seite einer Produktion $w\_2$ 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 $w\_2$ nur ein Terminal oder ein Nichtterminal gefolgt von einem Terminal sein darf..

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

$\backslash forall\; (w\_1\; \backslash rightarrow\; w\_2)\; \backslash in\; P\; :\; (w\_1\; \backslash in\; N)\; \backslash and\; \backslash left(w\_2\; \backslash in\; \backslash Sigma\; \backslash cup\; \backslash Sigma\; N\backslash 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 deterministischen endlichen Automaten erkannt werden können.

Siehe auch

---

• Formale Grammatik
• Chomsky-Hierarchie

Formale Sprachen | Theoretische Informatik