Reguläre Grammatik

Version vom 8. November 2026, 09:12 Uhr von Flbkwikiadmin (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Reguläre Grammatiken beschreiben mit einfachen Regeln genau die Sprachen, die endliche Automaten erkennen. ==Definition== Eine '''reguläre Grammatik''' ist eine formale Grammatik <math>G = (N, T, P, S)</math>, deren Regeln nur die Formen <math>A \to aB</math> und <math>A \to a</math> haben, mit <math>A, B \in N</math> und <math>a \in T</math>. Zusätzlich ist die Regel <math>S \to \varepsilon</math> erlaubt,…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Reguläre Grammatiken beschreiben mit einfachen Regeln genau die Sprachen, die endliche Automaten erkennen.

Definition

Eine reguläre Grammatik ist eine formale Grammatik [math]\displaystyle{ G = (N, T, P, S) }[/math], deren Regeln nur die Formen [math]\displaystyle{ A \to aB }[/math] und [math]\displaystyle{ A \to a }[/math] haben, mit [math]\displaystyle{ A, B \in N }[/math] und [math]\displaystyle{ a \in T }[/math]. Zusätzlich ist die Regel [math]\displaystyle{ S \to \varepsilon }[/math] erlaubt, wenn [math]\displaystyle{ S }[/math] auf keiner rechten Regelseite vorkommt. Das leere Wort entsteht dann nur direkt aus dem Startsymbol.

Reguläre Grammatiken erzeugen genau die Sprachen, die ein endlicher Automat erkennt. Diese Sprachen heißen reguläre Sprachen. Sie bilden Typ 3 der Chomsky-Hierarchie.

Rechtslineare Grammatik

Eine rechtslineare Grammatik ist allgemeiner: Ihre Regeln haben die Form [math]\displaystyle{ A \to wB }[/math] oder [math]\displaystyle{ A \to w }[/math] mit [math]\displaystyle{ w \in T^* }[/math]. Das Nichtterminal steht höchstens am rechten Ende der rechten Seite. Mit [math]\displaystyle{ w = \varepsilon }[/math] ist auch [math]\displaystyle{ A \to \varepsilon }[/math] erlaubt, bei jedem Nichtterminal. Auch rechtslineare Grammatiken erzeugen genau die regulären Sprachen.

Jede rechtslineare Grammatik lässt sich in eine gleichwertige reguläre Grammatik umformen. Für lange Terminalfolgen werden Hilfs-Nichtterminale eingeführt. Eine Regel [math]\displaystyle{ A \to a_1 a_2 \dots a_k B }[/math] mit [math]\displaystyle{ k \geq 2 }[/math] Terminalen wird durch [math]\displaystyle{ k }[/math] Regeln ersetzt:

[math]\displaystyle{ A \to a_1 H_1, \quad H_1 \to a_2 H_2, \quad \dots, \quad H_{k-1} \to a_k B }[/math]

[math]\displaystyle{ H_1, \dots, H_{k-1} }[/math] sind neue Nichtterminale. Jedes steht für den noch fehlenden Rest der Terminalfolge. Bei einer Regel [math]\displaystyle{ A \to a_1 \dots a_k }[/math] ohne Nichtterminal endet die Kette mit [math]\displaystyle{ H_{k-1} \to a_k }[/math].

Vom Automaten zur Grammatik

Aus einem DEA entsteht eine reguläre Grammatik, die dieselbe Sprache erzeugt:

  1. Jeder Zustand wird zu einem Nichtterminal. Zum Zustand [math]\displaystyle{ p }[/math] gehört das Nichtterminal [math]\displaystyle{ P }[/math]. Der Startzustand q0 wird zum Startsymbol [math]\displaystyle{ S }[/math].
  2. Aus jedem Übergang [math]\displaystyle{ \delta(p, a) = q }[/math] wird die Regel [math]\displaystyle{ P \to aQ }[/math].
  3. Ist [math]\displaystyle{ q }[/math] ein Endzustand, kommt zusätzlich die Regel [math]\displaystyle{ P \to a }[/math] hinzu.
  4. Ist q0 ein Endzustand, kommt zusätzlich die Regel [math]\displaystyle{ S \to \varepsilon }[/math] hinzu. Kommt [math]\displaystyle{ S }[/math] auf einer rechten Regelseite vor, braucht die Grammatik dafür ein neues Startsymbol [math]\displaystyle{ S' }[/math] mit denselben rechten Seiten wie [math]\displaystyle{ S }[/math]. Nur [math]\displaystyle{ S' }[/math] erhält dann die Regel [math]\displaystyle{ S' \to \varepsilon }[/math].
  5. Zustände, von denen aus kein weiteres Zeichen mehr zu einem Endzustand führt, brauchen kein Nichtterminal. Das gilt für den Fehlerzustand qF und für Endzustände ohne weiteren Weg. Alle Regeln dieser Zustände und alle Regeln [math]\displaystyle{ P \to aQ }[/math] mit einem solchen [math]\displaystyle{ Q }[/math] entfallen. Ist der Zustand ein Endzustand, bleibt von dem Übergang die Regel [math]\displaystyle{ P \to a }[/math].

Von der Grammatik zum Automaten

Aus einer regulären Grammatik entsteht ein endlicher Automat, der dieselbe Sprache erkennt:

  1. Jedes Nichtterminal wird zu einem Zustand. Dazu kommt ein neuer Endzustand. Das Startsymbol wird zum Startzustand.
  2. Aus jeder Regel [math]\displaystyle{ A \to aB }[/math] wird ein Übergang von [math]\displaystyle{ A }[/math] nach [math]\displaystyle{ B }[/math] mit dem Zeichen [math]\displaystyle{ a }[/math].
  3. Aus jeder Regel [math]\displaystyle{ A \to a }[/math] wird ein Übergang von [math]\displaystyle{ A }[/math] in den neuen Endzustand mit dem Zeichen [math]\displaystyle{ a }[/math].
  4. Gehört [math]\displaystyle{ S \to \varepsilon }[/math] zur Grammatik, ist auch der Startzustand ein Endzustand.

Es entsteht meist ein NEA, weil ein Nichtterminal mehrere Regeln mit demselben Terminal haben kann. Die Potenzmengenkonstruktion macht daraus einen DEA.

Beispiele

Grammatik zum Kaffeeautomaten angeben

 
Vollständiger DEA des Kaffeeautomaten

Gesucht ist eine reguläre Grammatik für den DEA im Bild. Der Kaffeeautomat akzeptiert Wörter aus K (Kaffee, zählt 1) und E (Espresso, zählt 2), die zusammen genau vier Einheiten ergeben, siehe Sprache als Menge angeben.

Die Zustände werden zu Nichtterminalen: q0 = S, q1 = A, q2 = B, q3 = C. Der Endzustand q4 hat nur Übergänge in den Fehlerzustand qF. Er braucht kein Nichtterminal. Die Übergänge nach q4 ergeben deshalb Regeln mit nur einem Terminal. Der Fehlerzustand qF entfällt.

  • q0 liest K und geht nach q1, liest E und geht nach q2. Das ergibt [math]\displaystyle{ S \to KA \mid EB }[/math].
  • q1 liest K und geht nach q2, liest E und geht nach q3. Das ergibt [math]\displaystyle{ A \to KB \mid EC }[/math].
  • q2 liest K und geht nach q3, liest E und geht nach q4. Das ergibt [math]\displaystyle{ B \to KC \mid E }[/math].
  • q3 liest K und geht nach q4. Das ergibt [math]\displaystyle{ C \to K }[/math]. Bei E geht q3 nach qF, dieser Übergang entfällt.

Die Grammatik hat die Regeln:

[math]\displaystyle{ S \to KA \mid EB }[/math]
[math]\displaystyle{ A \to KB \mid EC }[/math]
[math]\displaystyle{ B \to KC \mid E }[/math]
[math]\displaystyle{ C \to K }[/math]

Das Wort KEK wird so abgeleitet:

[math]\displaystyle{ S \Rightarrow KA \Rightarrow KEC \Rightarrow KEK }[/math]

Die Ableitung folgt dem Lauf des Automaten: Von q0 führt K nach q1 ([math]\displaystyle{ S \to KA }[/math]), von q1 führt E nach q3 ([math]\displaystyle{ A \to EC }[/math]), von q3 führt K in den Endzustand q4 ([math]\displaystyle{ C \to K }[/math]).

Rechtslineare Grammatik umformen

Die folgende Grammatik ist rechtslinear, hat aber noch nicht die Form einer regulären Grammatik:

[math]\displaystyle{ S \to KEA \mid K }[/math]
[math]\displaystyle{ A \to EA \mid E }[/math]

Die Regel [math]\displaystyle{ S \to KEA }[/math] hat zwei Terminale vor dem Nichtterminal. Ein Hilfs-Nichtterminal [math]\displaystyle{ B }[/math] übernimmt das zweite Terminal: Aus [math]\displaystyle{ S \to KEA }[/math] werden [math]\displaystyle{ S \to KB }[/math] und [math]\displaystyle{ B \to EA }[/math]. Die übrigen Regeln haben schon die reguläre Form und bleiben. Es entsteht:

[math]\displaystyle{ S \to KB \mid K }[/math]
[math]\displaystyle{ B \to EA }[/math]
[math]\displaystyle{ A \to EA \mid E }[/math]

Beide Grammatiken erzeugen dieselbe Sprache: K oder KE gefolgt von mindestens einem E. Die Wörter sind K, KEE, KEEE und so weiter. Das Wort KEE zeigt den Unterschied der Ableitungen. Die erste Grammatik braucht zwei Schritte, die zweite einen zusätzlichen Schritt über [math]\displaystyle{ B }[/math]:

[math]\displaystyle{ S \Rightarrow KEA \Rightarrow KEE }[/math]
[math]\displaystyle{ S \Rightarrow KB \Rightarrow KEA \Rightarrow KEE }[/math]