Reguläre Grammatiken

Eine formale Grammatik ist ein 4-Tupel \( G = (V, \Sigma, P, S) \) mit:

• \( V \) – Menge der Nichtterminale (Variablen)
• \( \Sigma \) – Menge der Terminale (Eingabesymbole), \( V \cap \Sigma = \emptyset \)
• \( P \) – Menge der Produktionsregeln der Form \( \alpha \rightarrow \beta \)
• \( S \in V \) – Startsymbol

Die Sprache der Grammatik ist die Menge aller Wörter aus \( \Sigma^* \), die sich aus \( S \) durch Anwenden der Regeln ableiten lassen.

Eine Grammatik heißt rechtslinear (Typ 3), wenn alle Produktionen die Form

\[ A \rightarrow aB \quad \text{oder} \quad A \rightarrow a \quad \text{oder} \quad A \rightarrow \varepsilon \]

haben, wobei \( A, B \in V \) und \( a \in \Sigma \). Das Nichtterminal steht rechts vom Terminal. Symmetrisch dazu gibt es linkslineare Grammatiken (\( A \rightarrow Ba \)). Beide erzeugen genau die regulären Sprachen.

Sprache: alle Wörter über \( \{a, b\} \) mit gerader Anzahl von as. Grammatik:

S → bS | aA | ε
A → bA | aS

Ableitung von abba:

S ⇒ aA ⇒ abA ⇒ abbA ⇒ abbaS ⇒ abba

Sprache: \( L = \{a^n b \mid n \geq 0\} \).

S → aS | b

Ableitung von aaab: \( S \Rightarrow aS \Rightarrow aaS \Rightarrow aaaS \Rightarrow aaab \). Die Grammatik hat genau eine Variable und zwei Regeln – minimaler geht es kaum.

Jede reguläre Grammatik lässt sich direkt in einen NEA übersetzen und umgekehrt. Konstruktion: Für jedes Nichtterminal \( A \) gibt es einen Zustand \( q_A \). Eine Regel \( A \rightarrow aB \) wird zur Kante \( q_A \xrightarrow{a} q_B \). Eine Regel \( A \rightarrow a \) wird zur Kante in einen Endzustand. Damit sind reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten drei gleichwertige Beschreibungen derselben Sprachklasse.

Sprachen wie \( \{a^n b^n \mid n \geq 1\} \) lassen sich nicht durch eine reguläre Grammatik erzeugen, weil sie eine Zählfähigkeit benötigen. Dazu braucht man kontextfreie Grammatiken (Typ 2). Das Pumping-Lemma für reguläre Sprachen liefert dafür den formalen Beweis.

Mischung von rechts- und linkslinearen Regeln in einer Grammatik (das ist nicht mehr Typ 3!), zwei Nichtterminale auf der rechten Seite (verboten), Startsymbol vergessen, Verwechslung von \( \varepsilon \) (leeres Wort) und einem fehlenden Symbol.

Zusammenfassung: Reguläre Grammatiken sind Typ-3-Grammatiken. Sie erzeugen genau die regulären Sprachen und sind äquivalent zu endlichen Automaten und regulären Ausdrücken.

Abitur-Tipp: Wenn du eine reguläre Grammatik konstruierst, zeichne parallel den zugehörigen Automaten – Fehler in einem werden im anderen sofort sichtbar.