Reguläre Grammatik: Unterschied zwischen den Versionen
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,…“ |
Keine Bearbeitungszusammenfassung |
||
| Zeile 2: | Zeile 2: | ||
==Definition== | ==Definition== | ||
Eine '''reguläre Grammatik''' ist eine [[Formale Grammatik|formale Grammatik]] <math>G = (N | Eine '''reguläre Grammatik''' ist eine [[Formale Grammatik|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. Dabei sind <math>A</math> und <math>B</math> Nichtterminale, und <math>a</math> ist ein Terminal. Zusätzlich ist die Regel <math>S \to \varepsilon</math> erlaubt, wenn <math>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]]. | 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]]. Was sie nicht leisten, zeigt der Abschnitt [[Kontextfreie Grammatik#Grenzen regulärer Sprachen|Grenzen regulärer Sprachen]]. | ||
==Rechtslineare Grammatik== | ==Rechtslineare Grammatik== | ||
Eine '''rechtslineare Grammatik''' ist allgemeiner: Ihre Regeln haben die Form <math>A \to wB</math> oder <math>A \to w</math> | Eine '''rechtslineare Grammatik''' ist allgemeiner: Ihre Regeln haben die Form <math>A \to wB</math> oder <math>A \to w</math>, wobei <math>w</math> ein beliebiges Wort aus Terminalen ist, auch das leere. Das Nichtterminal steht höchstens am rechten Ende der rechten Seite. Mit <math>w = \varepsilon</math> sind auch die Regeln <math>A \to B</math> und <math>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. | Jede rechtslineare Grammatik lässt sich in eine gleichwertige reguläre Grammatik umformen. Drei Arten von Regeln werden dafür nacheinander ersetzt: | ||
:<math>A \to a_1 H_1 | # '''Regel mit mehreren Terminalen:''' Für lange Terminalfolgen werden Hilfs-Nichtterminale eingeführt. Eine Regel <math>A \to a_1 a_2 \dots a_k B</math> mit <math>k \geq 2</math> Terminalen wird durch <math>k</math> Regeln ersetzt: | ||
#:<math>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>H_1</math> bis <math>H_{k-1}</math> sind neue Nichtterminale. Jedes steht für den noch fehlenden Rest der Terminalfolge. Bei einer Regel <math>A \to a_1 \dots a_k</math> ohne Nichtterminal endet die Kette mit <math>H_{k-1} \to a_k</math>. | |||
# '''Regel ohne Terminal:''' Eine Regel <math>A \to B</math> wird gestrichen. Dafür erhält <math>A</math> alle rechten Seiten von <math>B</math>: Was <math>B</math> erzeugt, erzeugt <math>A</math> dann direkt. Entsteht dabei wieder eine Regel ohne Terminal, wird der Schritt wiederholt. Eine Regel, die schon gestrichen wurde, kommt dabei nicht wieder hinzu. | |||
# '''Regel mit dem leeren Wort:''' Eine Regel <math>B \to \varepsilon</math> wird gestrichen. Dafür kommt zu jeder Regel <math>A \to aB</math> die Regel <math>A \to a</math> hinzu: Das Wort darf an dieser Stelle enden. Die Regel <math>A \to aB</math> bleibt bestehen, wenn <math>B</math> noch andere Regeln hat. | |||
<math> | Für das Startsymbol gilt im dritten Schritt eine Ausnahme: Die Regel <math>S \to \varepsilon</math> bleibt erhalten, sonst ginge das leere Wort verloren. Das ist nur erlaubt, wenn <math>S</math> auf keiner rechten Regelseite vorkommt. Kommt <math>S</math> dort vor, erhält die Grammatik ein neues Startsymbol <math>S'</math>. Es bekommt alle Regeln von <math>S</math> und die Regel <math>S' \to \varepsilon</math>. Die Regel <math>S \to \varepsilon</math> wird danach wie bei jedem anderen Nichtterminal gestrichen und ausgeglichen. | ||
Steht in einer Regel ein Nichtterminal nicht am rechten Ende, etwa in <math>S \to AB</math>, ist die Grammatik nicht rechtslinear. Erzeugt sie trotzdem eine reguläre Sprache, gibt es eine gleichwertige rechtslineare Grammatik. Sie entsteht in zwei Schritten: Zuerst wird beschrieben, welche Wörter jedes Nichtterminal erzeugt. Danach werden neue Regeln aufgestellt, die diese Wörter von links nach rechts aufbauen, sodass in jeder Regel höchstens ein Nichtterminal am rechten Ende steht. | |||
==Vom Automaten zur Grammatik== | ==Vom Automaten zur Grammatik== | ||
Aus einem [[Deterministischer endlicher Automat|DEA]] entsteht eine reguläre Grammatik, die dieselbe Sprache erzeugt: | Aus einem [[Deterministischer endlicher Automat|DEA]] entsteht eine reguläre Grammatik, die dieselbe Sprache erzeugt: | ||
# Jeder Zustand wird zu einem Nichtterminal. Zum Zustand <math>p</math> gehört das Nichtterminal <math>P</math>. Der Startzustand | # Jeder Zustand wird zu einem Nichtterminal. Zum Zustand <math>p</math> gehört das Nichtterminal <math>P</math>. Der Startzustand <math>q_0</math> wird zum Startsymbol <math>S</math>. | ||
# Aus jedem Übergang <math>\delta(p | # Aus jedem Übergang <math>\delta(p; a) = q</math> wird die Regel <math>P \to aQ</math>. | ||
# Ist <math>q</math> ein Endzustand, kommt zusätzlich die Regel <math>P \to a</math> hinzu. | # Ist <math>q</math> ein Endzustand, kommt zusätzlich die Regel <math>P \to a</math> hinzu. Mit ihr endet das Wort im Endzustand, mit <math>P \to aQ</math> geht es von dort aus weiter. | ||
# Ist | # Ist <math>q_0</math> ein Endzustand, kommt zusätzlich die Regel <math>S \to \varepsilon</math> hinzu. Kommt <math>S</math> auf einer rechten Regelseite vor, braucht die Grammatik dafür ein neues Startsymbol <math>S'</math> mit denselben rechten Seiten wie <math>S</math>. Nur <math>S'</math> erhält dann die Regel <math>S' \to \varepsilon</math>. | ||
# Zustände, von denen aus kein | # Zustände, von denen aus kein Endzustand mehr erreichbar ist, brauchen kein Nichtterminal. Das gilt für den [[Deterministischer endlicher Automat#Vollständiger DEA und Fehlerzustand|Fehlerzustand]] <math>q_F</math>. Alle Regeln <math>P \to aQ</math> mit einem solchen Zustand <math>Q</math> entfallen. Führen von einem Endzustand <math>q</math> alle Übergänge in den Fehlerzustand, braucht auch <math>q</math> kein Nichtterminal: Von einem Übergang <math>\delta(p; a) = q</math> bleibt dann nur die Regel <math>P \to a</math>. | ||
==Von der Grammatik zum Automaten== | ==Von der Grammatik zum Automaten== | ||
| Zeile 37: | Zeile 43: | ||
===Grammatik zum Kaffeeautomaten angeben=== | ===Grammatik zum Kaffeeautomaten angeben=== | ||
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]] | [[Datei:DEA Kaffeeautomat vollständig.png|mini|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 [[Formale Sprache#Sprache als Menge angeben|Sprache als Menge angeben]]. | Gesucht ist eine reguläre Grammatik für den DEA im Bild. Der Kaffeeautomat akzeptiert Wörter aus <math>K</math> (Kaffee, zählt 1) und <math>E</math> (Espresso, zählt 2), die zusammen genau vier Einheiten ergeben, siehe [[Formale Sprache#Sprache als Menge angeben|Sprache als Menge angeben]]. | ||
Die Zustände werden zu Nichtterminalen: | Die Zustände werden zu Nichtterminalen: <math>q_0</math> wird <math>S</math>, <math>q_1</math> wird <math>A</math>, <math>q_2</math> wird <math>B</math>, <math>q_3</math> wird <math>C</math>. Vom Endzustand <math>q_4</math> führen alle Übergänge in den Fehlerzustand <math>q_F</math>. Der Endzustand <math>q_4</math> braucht deshalb kein Nichtterminal: Die Übergänge nach <math>q_4</math> ergeben Regeln mit nur einem Terminal. Auch der Fehlerzustand <math>q_F</math> erhält kein Nichtterminal. | ||
* | * <math>q_0</math> liest <math>K</math> und geht nach <math>q_1</math>, liest <math>E</math> und geht nach <math>q_2</math>. Das ergibt <math>S \to KA \mid EB</math>. | ||
* | * <math>q_1</math> liest <math>K</math> und geht nach <math>q_2</math>, liest <math>E</math> und geht nach <math>q_3</math>. Das ergibt <math>A \to KB \mid EC</math>. | ||
* | * <math>q_2</math> liest <math>K</math> und geht nach <math>q_3</math>, liest <math>E</math> und geht nach <math>q_4</math>. Das ergibt <math>B \to KC \mid E</math>. | ||
* | * <math>q_3</math> liest <math>K</math> und geht nach <math>q_4</math>. Das ergibt <math>C \to K</math>. Bei <math>E</math> geht <math>q_3</math> nach <math>q_F</math>, dieser Übergang entfällt. | ||
Die Grammatik hat die Regeln: | Die Grammatik hat die Regeln: | ||
| Zeile 53: | Zeile 59: | ||
:<math>C \to K</math> | :<math>C \to K</math> | ||
Das Wort < | Das Wort <math>KEK</math> wird so abgeleitet: | ||
:<math>S \Rightarrow KA \Rightarrow KEC \Rightarrow KEK</math> | :<math>S \Rightarrow KA \Rightarrow KEC \Rightarrow KEK</math> | ||
Die Ableitung folgt dem Lauf des Automaten: Von | Die Ableitung folgt dem Lauf des Automaten: Von <math>q_0</math> führt <math>K</math> nach <math>q_1</math> (<math>S \to KA</math>), von <math>q_1</math> führt <math>E</math> nach <math>q_3</math> (<math>A \to EC</math>), von <math>q_3</math> führt <math>K</math> in den Endzustand <math>q_4</math> (<math>C \to K</math>). | ||
===Grammatik zu einem DEA mit weiterführendem Endzustand angeben=== | |||
[[Datei:DEA Teilwort KE.png|mini|DEA für Wörter mit dem Teilwort KE]] | |||
Der DEA im Bild akzeptiert alle Wörter über <math>\Sigma = \{K; E\}</math>, die das Teilwort <math>KE</math> enthalten, siehe [[Deterministischer endlicher Automat#DEA entwerfen|DEA entwerfen]]. Anders als beim Kaffeeautomaten geht es im Endzustand <math>q_2</math> weiter: Er hat eine Schleife für <math>K</math> und <math>E</math>. | |||
Die Zustände werden zu Nichtterminalen: <math>q_0</math> wird <math>S</math>, <math>q_1</math> wird <math>A</math>, <math>q_2</math> wird <math>B</math>. Jeder Übergang ergibt eine Regel. Zu jedem Übergang in den Endzustand <math>q_2</math> kommt eine zweite Regel ohne Nichtterminal hinzu: | |||
* <math>q_0</math>: <math>K</math> führt nach <math>q_1</math>, <math>E</math> führt nach <math>q_0</math>. Das ergibt <math>S \to KA \mid ES</math>. | |||
* <math>q_1</math>: <math>K</math> führt nach <math>q_1</math>, <math>E</math> führt in den Endzustand <math>q_2</math>. Das ergibt <math>A \to KA \mid EB \mid E</math>. | |||
* <math>q_2</math>: <math>K</math> und <math>E</math> führen in den Endzustand <math>q_2</math>. Das ergibt <math>B \to KB \mid EB \mid K \mid E</math>. | |||
:<math>S \to KA \mid ES</math> | |||
:<math>A \to KA \mid EB \mid E</math> | |||
:<math>B \to KB \mid EB \mid K \mid E</math> | |||
Die Regel <math>A \to E</math> beendet ein Wort direkt nach dem ersten <math>KE</math>. So entsteht das kürzeste Wort der Sprache: | |||
:<math>S \Rightarrow KA \Rightarrow KE</math> | |||
Die Regel <math>A \to EB</math> lässt weitere Zeichen folgen. Das Wort <math>EKEK</math> braucht sie, weil nach dem <math>KE</math> noch ein Zeichen kommt: | |||
:<math>S \Rightarrow ES \Rightarrow EKA \Rightarrow EKEB \Rightarrow EKEK</math> | |||
Der Startzustand ist kein Endzustand, deshalb gibt es keine Regel <math>S \to \varepsilon</math>. | |||
===Grammatik zu einem DEA angeben, der das leere Wort akzeptiert=== | |||
[[Datei:DEA Reste der Einheiten.png|mini|DEA für die Reste 0, 1 und 2]] | |||
Der DEA im Bild akzeptiert alle Bestellfolgen, deren Summe der Einheiten durch 3 teilbar ist, siehe [[Deterministischer endlicher Automat#DEA für Reste entwerfen|DEA für Reste entwerfen]]. Sein Startzustand <math>q_0</math> ist zugleich der einzige Endzustand. Der DEA akzeptiert deshalb auch das leere Wort. | |||
'''Schritt 1: Zustände und Übergänge übertragen.''' <math>q_0</math> wird <math>S</math>, <math>q_1</math> wird <math>A</math>, <math>q_2</math> wird <math>B</math>. Jeder Übergang ergibt eine Regel. Die beiden Übergänge in den Endzustand <math>q_0</math> ergeben zusätzlich je eine Regel ohne Nichtterminal: <math>A \to E</math> und <math>B \to K</math>. | |||
:<math>S \to KA \mid EB</math> | |||
:<math>A \to KB \mid ES \mid E</math> | |||
:<math>B \to KS \mid K \mid EA</math> | |||
Diese Grammatik erzeugt alle Wörter des Automaten außer dem leeren Wort. | |||
'''Schritt 2: Leeres Wort ergänzen.''' Die Regel <math>S \to \varepsilon</math> ist in einer regulären Grammatik nur erlaubt, wenn <math>S</math> auf keiner rechten Regelseite vorkommt. Hier kommt <math>S</math> in <math>A \to ES</math> und in <math>B \to KS</math> vor. Die Grammatik erhält deshalb ein neues Startsymbol <math>S'</math> mit denselben rechten Seiten wie <math>S</math> und der zusätzlichen Regel <math>S' \to \varepsilon</math>: | |||
:<math>S' \to KA \mid EB \mid \varepsilon</math> | |||
:<math>S \to KA \mid EB</math> | |||
:<math>A \to KB \mid ES \mid E</math> | |||
:<math>B \to KS \mid K \mid EA</math> | |||
'''Schritt 3: Prüfen.''' Das leere Wort entsteht direkt mit <math>S' \Rightarrow \varepsilon</math>. Für <math>KE</math> mit 1 + 2 = 3 Einheiten gilt: | |||
:<math>S' \Rightarrow KA \Rightarrow KE</math> | |||
Das Wort <math>KK</math> mit 2 Einheiten ist nicht ableitbar: Nach <math>S' \Rightarrow KA \Rightarrow KKB</math> steht noch das Nichtterminal <math>B</math> da, und jede Regel für <math>B</math> erzeugt mindestens ein weiteres Zeichen. | |||
===Rechtslineare Grammatik konstruieren=== | |||
Gesucht ist eine rechtslineare Grammatik für alle Wörter über <math>\{K; E\}</math>, die mindestens ein <math>E</math> enthalten, zum Beispiel <math>E</math>, <math>KE</math>, <math>EK</math> und <math>KEKE</math>. | |||
'''Schritt 1: Gedächtnis festlegen.''' Wie die Zustände eines DEA merken sich die Nichtterminale, was bisher erzeugt wurde: <math>S</math> steht für „noch kein <math>E</math> erzeugt“, <math>A</math> steht für „mindestens ein <math>E</math> erzeugt“. | |||
'''Schritt 2: Regeln aufstellen.''' Solange noch kein <math>E</math> erzeugt ist, darf ein <math>K</math> folgen (<math>S \to KS</math>) oder das erste <math>E</math> (<math>S \to EA</math>). Danach dürfen beliebige Zeichen folgen (<math>A \to KA</math> und <math>A \to EA</math>), oder das Wort endet (<math>A \to \varepsilon</math>): | |||
:<math>S \to KS \mid EA</math> | |||
:<math>A \to KA \mid EA \mid \varepsilon</math> | |||
'''Schritt 3: Prüfen.''' Das Wort <math>KEK</math> ist ableitbar: | |||
:<math>S \Rightarrow KS \Rightarrow KEA \Rightarrow KEKA \Rightarrow KEK</math> | |||
Ein Wort ohne <math>E</math> lässt sich nicht ableiten: Nur die Regel <math>S \to EA</math> führt zu <math>A</math>, und nur bei <math>A</math> kann eine Ableitung enden. | |||
'''Schritt 4: In die reguläre Form bringen.''' Die Regel <math>A \to \varepsilon</math> ist in einer regulären Grammatik nicht erlaubt. Sie wird gestrichen. Zum Ausgleich kommt zu jeder Regel, deren rechte Seite mit <math>A</math> endet, eine Regel ohne <math>A</math> hinzu: zu <math>S \to EA</math> die Regel <math>S \to E</math>, zu <math>A \to KA</math> die Regel <math>A \to K</math> und zu <math>A \to EA</math> die Regel <math>A \to E</math>: | |||
:<math>S \to KS \mid EA \mid E</math> | |||
:<math>A \to KA \mid EA \mid K \mid E</math> | |||
Das Wort <math>KEK</math> braucht jetzt einen Schritt weniger, weil die Ableitung mit <math>A \to K</math> endet: | |||
:<math>S \Rightarrow KS \Rightarrow KEA \Rightarrow KEK</math> | |||
Dieselbe reguläre Grammatik entsteht auch aus dem DEA im Beispiel [[Deterministischer endlicher Automat#Akzeptierte Sprache eines DEA beschreiben|Akzeptierte Sprache eines DEA beschreiben]]: <math>S</math> entspricht dort dem Zustand <math>q_0</math>, <math>A</math> dem Zustand <math>q_1</math>. | |||
===Regel ohne Terminal ersetzen=== | |||
Die folgende rechtslineare Grammatik erzeugt alle Wörter aus beliebig vielen <math>K</math>, auf die mindestens ein <math>E</math> folgt: | |||
:<math>S \to KS \mid A</math> | |||
:<math>A \to EA \mid E</math> | |||
Die Regel <math>S \to A</math> hat rechts kein Terminal und ist deshalb in einer regulären Grammatik nicht erlaubt. Sie wird gestrichen. Dafür erhält <math>S</math> die rechten Seiten von <math>A</math>, also <math>EA</math> und <math>E</math>: | |||
:<math>S \to KS \mid EA \mid E</math> | |||
:<math>A \to EA \mid E</math> | |||
Das Wort <math>KEE</math> zeigt den Unterschied. Die erste Grammatik braucht den Zwischenschritt von <math>S</math> nach <math>A</math>, die zweite nicht: | |||
:<math>S \Rightarrow KS \Rightarrow KA \Rightarrow KEA \Rightarrow KEE</math> | |||
:<math>S \Rightarrow KS \Rightarrow KEA \Rightarrow KEE</math> | |||
===Rechtslineare Grammatik umformen=== | ===Rechtslineare Grammatik umformen=== | ||
| Zeile 71: | Zeile 169: | ||
:<math>A \to EA \mid E</math> | :<math>A \to EA \mid E</math> | ||
Beide Grammatiken erzeugen dieselbe Sprache: < | Beide Grammatiken erzeugen dieselbe Sprache: <math>K</math> allein oder <math>KE</math> gefolgt von mindestens einem weiteren <math>E</math>. Die Wörter sind <math>K</math>, <math>KEE</math>, <math>KEEE</math> und so weiter. Das Wort <math>KEE</math> zeigt den Unterschied der Ableitungen. Die erste Grammatik braucht zwei Schritte, die zweite einen zusätzlichen Schritt über <math>B</math>: | ||
:<math>S \Rightarrow KEA \Rightarrow KEE</math> | :<math>S \Rightarrow KEA \Rightarrow KEE</math> | ||
:<math>S \Rightarrow KB \Rightarrow KEA \Rightarrow KEE</math> | :<math>S \Rightarrow KB \Rightarrow KEA \Rightarrow KEE</math> | ||
===Automaten zu einer regulären Grammatik konstruieren=== | |||
[[Datei:NEA aus regulärer Grammatik.png|mini|NEA zur regulären Grammatik]] | |||
Gesucht ist ein endlicher Automat für die reguläre Grammatik aus dem vorigen Beispiel: | |||
:<math>S \to KB \mid K</math> | |||
:<math>B \to EA</math> | |||
:<math>A \to EA \mid E</math> | |||
'''Schritt 1: Zustände anlegen.''' Die Nichtterminale <math>S</math>, <math>B</math> und <math>A</math> werden zu Zuständen. Dazu kommt der neue Endzustand <math>X</math>. Der Startzustand ist <math>S</math>. | |||
'''Schritt 2: Regeln mit Nichtterminal übertragen.''' <math>S \to KB</math> ergibt einen Übergang von <math>S</math> nach <math>B</math> mit <math>K</math>. <math>B \to EA</math> ergibt einen Übergang von <math>B</math> nach <math>A</math> mit <math>E</math>. <math>A \to EA</math> ergibt eine Schleife an <math>A</math> mit <math>E</math>. | |||
'''Schritt 3: Regeln ohne Nichtterminal übertragen.''' <math>S \to K</math> ergibt einen Übergang von <math>S</math> nach <math>X</math> mit <math>K</math>. <math>A \to E</math> ergibt einen Übergang von <math>A</math> nach <math>X</math> mit <math>E</math>. | |||
{| class="wikitable" style="text-align:center" | |||
! <math>\delta</math> !! <math>K</math> !! <math>E</math> | |||
|- | |||
| <math>\rightarrow S</math> || <math>\{B; X\}</math> || – | |||
|- | |||
| <math>B</math> || – || <math>\{A\}</math> | |||
|- | |||
| <math>A</math> || – || <math>\{A; X\}</math> | |||
|- | |||
| <math>{}^*X</math> || – || – | |||
|} | |||
Der Automat ist ein NEA: In <math>S</math> gibt es für <math>K</math> zwei Folgezustände, in <math>A</math> für <math>E</math> ebenfalls. Für das Wort <math>KEE</math> gibt es diese Pfade: | |||
* <math>S \xrightarrow{K} B \xrightarrow{E} A \xrightarrow{E} A</math> (kein Endzustand) | |||
* <math>S \xrightarrow{K} B \xrightarrow{E} A \xrightarrow{E} X</math> (akzeptiert) | |||
* <math>S \xrightarrow{K} X</math> (bricht ab) | |||
Ein Pfad liest das ganze Wort und endet im Endzustand <math>X</math>. Der Automat akzeptiert <math>KEE</math>, so wie die Grammatik das Wort erzeugt. | |||
===Grammatik in eine rechtslineare Grammatik umformen=== | |||
Die folgende Grammatik ist nicht rechtslinear, denn in der Regel für <math>S</math> steht das Nichtterminal <math>A</math> am Anfang: | |||
:<math>S \to AE</math> | |||
:<math>A \to KA \mid K</math> | |||
'''Schritt 1: Sprache beschreiben.''' <math>A</math> erzeugt ein oder mehrere <math>K</math>: Die Regel <math>A \to KA</math> setzt ein weiteres <math>K</math> davor, die Regel <math>A \to K</math> beendet die Folge. <math>S \to AE</math> hängt genau ein <math>E</math> an. Die Sprache ist <math>\{K^n E \mid n \geq 1\}</math>, dabei ist <math>K^n</math> eine [[Wort#Wortpotenz|Wortpotenz]]. | |||
'''Schritt 2: Wörter von links nach rechts aufbauen.''' Jedes Wort beginnt mit <math>K</math>. Danach folgt entweder ein weiteres Wort derselben Sprache oder das abschließende <math>E</math>: | |||
:<math>S \to KS \mid KE</math> | |||
'''Schritt 3: Vergleichen.''' Das Wort <math>KKE</math> lässt sich mit beiden Grammatiken ableiten: | |||
:<math>S \Rightarrow AE \Rightarrow KAE \Rightarrow KKE</math> | |||
:<math>S \Rightarrow KS \Rightarrow KKE</math> | |||
Die neue Grammatik ist rechtslinear. Die Regel <math>S \to KE</math> hat noch zwei Terminale. Für die reguläre Form wird sie wie im Beispiel [[#Rechtslineare Grammatik umformen|Rechtslineare Grammatik umformen]] durch <math>S \to KB</math> und <math>B \to E</math> ersetzt. | |||
[[Kategorie:Formale Sprachen]] | [[Kategorie:Formale Sprachen]] | ||
[[Kategorie:AHR I Informatik LK]] | [[Kategorie:AHR I Informatik LK]] | ||
Aktuelle Version vom 12. November 2026, 05:09 Uhr
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. Dabei sind [math]\displaystyle{ A }[/math] und [math]\displaystyle{ B }[/math] Nichtterminale, und [math]\displaystyle{ a }[/math] ist ein Terminal. 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. Was sie nicht leisten, zeigt der Abschnitt Grenzen regulärer Sprachen.
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], wobei [math]\displaystyle{ w }[/math] ein beliebiges Wort aus Terminalen ist, auch das leere. Das Nichtterminal steht höchstens am rechten Ende der rechten Seite. Mit [math]\displaystyle{ w = \varepsilon }[/math] sind auch die Regeln [math]\displaystyle{ A \to B }[/math] und [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. Drei Arten von Regeln werden dafür nacheinander ersetzt:
- Regel mit mehreren Terminalen: 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 }[/math] bis [math]\displaystyle{ 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].
- Regel ohne Terminal: Eine Regel [math]\displaystyle{ A \to B }[/math] wird gestrichen. Dafür erhält [math]\displaystyle{ A }[/math] alle rechten Seiten von [math]\displaystyle{ B }[/math]: Was [math]\displaystyle{ B }[/math] erzeugt, erzeugt [math]\displaystyle{ A }[/math] dann direkt. Entsteht dabei wieder eine Regel ohne Terminal, wird der Schritt wiederholt. Eine Regel, die schon gestrichen wurde, kommt dabei nicht wieder hinzu.
- Regel mit dem leeren Wort: Eine Regel [math]\displaystyle{ B \to \varepsilon }[/math] wird gestrichen. Dafür kommt zu jeder Regel [math]\displaystyle{ A \to aB }[/math] die Regel [math]\displaystyle{ A \to a }[/math] hinzu: Das Wort darf an dieser Stelle enden. Die Regel [math]\displaystyle{ A \to aB }[/math] bleibt bestehen, wenn [math]\displaystyle{ B }[/math] noch andere Regeln hat.
Für das Startsymbol gilt im dritten Schritt eine Ausnahme: Die Regel [math]\displaystyle{ S \to \varepsilon }[/math] bleibt erhalten, sonst ginge das leere Wort verloren. Das ist nur erlaubt, wenn [math]\displaystyle{ S }[/math] auf keiner rechten Regelseite vorkommt. Kommt [math]\displaystyle{ S }[/math] dort vor, erhält die Grammatik ein neues Startsymbol [math]\displaystyle{ S' }[/math]. Es bekommt alle Regeln von [math]\displaystyle{ S }[/math] und die Regel [math]\displaystyle{ S' \to \varepsilon }[/math]. Die Regel [math]\displaystyle{ S \to \varepsilon }[/math] wird danach wie bei jedem anderen Nichtterminal gestrichen und ausgeglichen.
Steht in einer Regel ein Nichtterminal nicht am rechten Ende, etwa in [math]\displaystyle{ S \to AB }[/math], ist die Grammatik nicht rechtslinear. Erzeugt sie trotzdem eine reguläre Sprache, gibt es eine gleichwertige rechtslineare Grammatik. Sie entsteht in zwei Schritten: Zuerst wird beschrieben, welche Wörter jedes Nichtterminal erzeugt. Danach werden neue Regeln aufgestellt, die diese Wörter von links nach rechts aufbauen, sodass in jeder Regel höchstens ein Nichtterminal am rechten Ende steht.
Vom Automaten zur Grammatik
Aus einem DEA entsteht eine reguläre Grammatik, die dieselbe Sprache erzeugt:
- Jeder Zustand wird zu einem Nichtterminal. Zum Zustand [math]\displaystyle{ p }[/math] gehört das Nichtterminal [math]\displaystyle{ P }[/math]. Der Startzustand [math]\displaystyle{ q_0 }[/math] wird zum Startsymbol [math]\displaystyle{ S }[/math].
- Aus jedem Übergang [math]\displaystyle{ \delta(p; a) = q }[/math] wird die Regel [math]\displaystyle{ P \to aQ }[/math].
- Ist [math]\displaystyle{ q }[/math] ein Endzustand, kommt zusätzlich die Regel [math]\displaystyle{ P \to a }[/math] hinzu. Mit ihr endet das Wort im Endzustand, mit [math]\displaystyle{ P \to aQ }[/math] geht es von dort aus weiter.
- Ist [math]\displaystyle{ q_0 }[/math] 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].
- Zustände, von denen aus kein Endzustand mehr erreichbar ist, brauchen kein Nichtterminal. Das gilt für den Fehlerzustand [math]\displaystyle{ q_F }[/math]. Alle Regeln [math]\displaystyle{ P \to aQ }[/math] mit einem solchen Zustand [math]\displaystyle{ Q }[/math] entfallen. Führen von einem Endzustand [math]\displaystyle{ q }[/math] alle Übergänge in den Fehlerzustand, braucht auch [math]\displaystyle{ q }[/math] kein Nichtterminal: Von einem Übergang [math]\displaystyle{ \delta(p; a) = q }[/math] bleibt dann nur 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:
- Jedes Nichtterminal wird zu einem Zustand. Dazu kommt ein neuer Endzustand. Das Startsymbol wird zum Startzustand.
- 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].
- 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].
- 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

Gesucht ist eine reguläre Grammatik für den DEA im Bild. Der Kaffeeautomat akzeptiert Wörter aus [math]\displaystyle{ K }[/math] (Kaffee, zählt 1) und [math]\displaystyle{ E }[/math] (Espresso, zählt 2), die zusammen genau vier Einheiten ergeben, siehe Sprache als Menge angeben.
Die Zustände werden zu Nichtterminalen: [math]\displaystyle{ q_0 }[/math] wird [math]\displaystyle{ S }[/math], [math]\displaystyle{ q_1 }[/math] wird [math]\displaystyle{ A }[/math], [math]\displaystyle{ q_2 }[/math] wird [math]\displaystyle{ B }[/math], [math]\displaystyle{ q_3 }[/math] wird [math]\displaystyle{ C }[/math]. Vom Endzustand [math]\displaystyle{ q_4 }[/math] führen alle Übergänge in den Fehlerzustand [math]\displaystyle{ q_F }[/math]. Der Endzustand [math]\displaystyle{ q_4 }[/math] braucht deshalb kein Nichtterminal: Die Übergänge nach [math]\displaystyle{ q_4 }[/math] ergeben Regeln mit nur einem Terminal. Auch der Fehlerzustand [math]\displaystyle{ q_F }[/math] erhält kein Nichtterminal.
- [math]\displaystyle{ q_0 }[/math] liest [math]\displaystyle{ K }[/math] und geht nach [math]\displaystyle{ q_1 }[/math], liest [math]\displaystyle{ E }[/math] und geht nach [math]\displaystyle{ q_2 }[/math]. Das ergibt [math]\displaystyle{ S \to KA \mid EB }[/math].
- [math]\displaystyle{ q_1 }[/math] liest [math]\displaystyle{ K }[/math] und geht nach [math]\displaystyle{ q_2 }[/math], liest [math]\displaystyle{ E }[/math] und geht nach [math]\displaystyle{ q_3 }[/math]. Das ergibt [math]\displaystyle{ A \to KB \mid EC }[/math].
- [math]\displaystyle{ q_2 }[/math] liest [math]\displaystyle{ K }[/math] und geht nach [math]\displaystyle{ q_3 }[/math], liest [math]\displaystyle{ E }[/math] und geht nach [math]\displaystyle{ q_4 }[/math]. Das ergibt [math]\displaystyle{ B \to KC \mid E }[/math].
- [math]\displaystyle{ q_3 }[/math] liest [math]\displaystyle{ K }[/math] und geht nach [math]\displaystyle{ q_4 }[/math]. Das ergibt [math]\displaystyle{ C \to K }[/math]. Bei [math]\displaystyle{ E }[/math] geht [math]\displaystyle{ q_3 }[/math] nach [math]\displaystyle{ q_F }[/math], 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 [math]\displaystyle{ KEK }[/math] wird so abgeleitet:
- [math]\displaystyle{ S \Rightarrow KA \Rightarrow KEC \Rightarrow KEK }[/math]
Die Ableitung folgt dem Lauf des Automaten: Von [math]\displaystyle{ q_0 }[/math] führt [math]\displaystyle{ K }[/math] nach [math]\displaystyle{ q_1 }[/math] ([math]\displaystyle{ S \to KA }[/math]), von [math]\displaystyle{ q_1 }[/math] führt [math]\displaystyle{ E }[/math] nach [math]\displaystyle{ q_3 }[/math] ([math]\displaystyle{ A \to EC }[/math]), von [math]\displaystyle{ q_3 }[/math] führt [math]\displaystyle{ K }[/math] in den Endzustand [math]\displaystyle{ q_4 }[/math] ([math]\displaystyle{ C \to K }[/math]).
Grammatik zu einem DEA mit weiterführendem Endzustand angeben

Der DEA im Bild akzeptiert alle Wörter über [math]\displaystyle{ \Sigma = \{K; E\} }[/math], die das Teilwort [math]\displaystyle{ KE }[/math] enthalten, siehe DEA entwerfen. Anders als beim Kaffeeautomaten geht es im Endzustand [math]\displaystyle{ q_2 }[/math] weiter: Er hat eine Schleife für [math]\displaystyle{ K }[/math] und [math]\displaystyle{ E }[/math].
Die Zustände werden zu Nichtterminalen: [math]\displaystyle{ q_0 }[/math] wird [math]\displaystyle{ S }[/math], [math]\displaystyle{ q_1 }[/math] wird [math]\displaystyle{ A }[/math], [math]\displaystyle{ q_2 }[/math] wird [math]\displaystyle{ B }[/math]. Jeder Übergang ergibt eine Regel. Zu jedem Übergang in den Endzustand [math]\displaystyle{ q_2 }[/math] kommt eine zweite Regel ohne Nichtterminal hinzu:
- [math]\displaystyle{ q_0 }[/math]: [math]\displaystyle{ K }[/math] führt nach [math]\displaystyle{ q_1 }[/math], [math]\displaystyle{ E }[/math] führt nach [math]\displaystyle{ q_0 }[/math]. Das ergibt [math]\displaystyle{ S \to KA \mid ES }[/math].
- [math]\displaystyle{ q_1 }[/math]: [math]\displaystyle{ K }[/math] führt nach [math]\displaystyle{ q_1 }[/math], [math]\displaystyle{ E }[/math] führt in den Endzustand [math]\displaystyle{ q_2 }[/math]. Das ergibt [math]\displaystyle{ A \to KA \mid EB \mid E }[/math].
- [math]\displaystyle{ q_2 }[/math]: [math]\displaystyle{ K }[/math] und [math]\displaystyle{ E }[/math] führen in den Endzustand [math]\displaystyle{ q_2 }[/math]. Das ergibt [math]\displaystyle{ B \to KB \mid EB \mid K \mid E }[/math].
- [math]\displaystyle{ S \to KA \mid ES }[/math]
- [math]\displaystyle{ A \to KA \mid EB \mid E }[/math]
- [math]\displaystyle{ B \to KB \mid EB \mid K \mid E }[/math]
Die Regel [math]\displaystyle{ A \to E }[/math] beendet ein Wort direkt nach dem ersten [math]\displaystyle{ KE }[/math]. So entsteht das kürzeste Wort der Sprache:
- [math]\displaystyle{ S \Rightarrow KA \Rightarrow KE }[/math]
Die Regel [math]\displaystyle{ A \to EB }[/math] lässt weitere Zeichen folgen. Das Wort [math]\displaystyle{ EKEK }[/math] braucht sie, weil nach dem [math]\displaystyle{ KE }[/math] noch ein Zeichen kommt:
- [math]\displaystyle{ S \Rightarrow ES \Rightarrow EKA \Rightarrow EKEB \Rightarrow EKEK }[/math]
Der Startzustand ist kein Endzustand, deshalb gibt es keine Regel [math]\displaystyle{ S \to \varepsilon }[/math].
Grammatik zu einem DEA angeben, der das leere Wort akzeptiert

Der DEA im Bild akzeptiert alle Bestellfolgen, deren Summe der Einheiten durch 3 teilbar ist, siehe DEA für Reste entwerfen. Sein Startzustand [math]\displaystyle{ q_0 }[/math] ist zugleich der einzige Endzustand. Der DEA akzeptiert deshalb auch das leere Wort.
Schritt 1: Zustände und Übergänge übertragen. [math]\displaystyle{ q_0 }[/math] wird [math]\displaystyle{ S }[/math], [math]\displaystyle{ q_1 }[/math] wird [math]\displaystyle{ A }[/math], [math]\displaystyle{ q_2 }[/math] wird [math]\displaystyle{ B }[/math]. Jeder Übergang ergibt eine Regel. Die beiden Übergänge in den Endzustand [math]\displaystyle{ q_0 }[/math] ergeben zusätzlich je eine Regel ohne Nichtterminal: [math]\displaystyle{ A \to E }[/math] und [math]\displaystyle{ B \to K }[/math].
- [math]\displaystyle{ S \to KA \mid EB }[/math]
- [math]\displaystyle{ A \to KB \mid ES \mid E }[/math]
- [math]\displaystyle{ B \to KS \mid K \mid EA }[/math]
Diese Grammatik erzeugt alle Wörter des Automaten außer dem leeren Wort.
Schritt 2: Leeres Wort ergänzen. Die Regel [math]\displaystyle{ S \to \varepsilon }[/math] ist in einer regulären Grammatik nur erlaubt, wenn [math]\displaystyle{ S }[/math] auf keiner rechten Regelseite vorkommt. Hier kommt [math]\displaystyle{ S }[/math] in [math]\displaystyle{ A \to ES }[/math] und in [math]\displaystyle{ B \to KS }[/math] vor. Die Grammatik erhält deshalb ein neues Startsymbol [math]\displaystyle{ S' }[/math] mit denselben rechten Seiten wie [math]\displaystyle{ S }[/math] und der zusätzlichen Regel [math]\displaystyle{ S' \to \varepsilon }[/math]:
- [math]\displaystyle{ S' \to KA \mid EB \mid \varepsilon }[/math]
- [math]\displaystyle{ S \to KA \mid EB }[/math]
- [math]\displaystyle{ A \to KB \mid ES \mid E }[/math]
- [math]\displaystyle{ B \to KS \mid K \mid EA }[/math]
Schritt 3: Prüfen. Das leere Wort entsteht direkt mit [math]\displaystyle{ S' \Rightarrow \varepsilon }[/math]. Für [math]\displaystyle{ KE }[/math] mit 1 + 2 = 3 Einheiten gilt:
- [math]\displaystyle{ S' \Rightarrow KA \Rightarrow KE }[/math]
Das Wort [math]\displaystyle{ KK }[/math] mit 2 Einheiten ist nicht ableitbar: Nach [math]\displaystyle{ S' \Rightarrow KA \Rightarrow KKB }[/math] steht noch das Nichtterminal [math]\displaystyle{ B }[/math] da, und jede Regel für [math]\displaystyle{ B }[/math] erzeugt mindestens ein weiteres Zeichen.
Rechtslineare Grammatik konstruieren
Gesucht ist eine rechtslineare Grammatik für alle Wörter über [math]\displaystyle{ \{K; E\} }[/math], die mindestens ein [math]\displaystyle{ E }[/math] enthalten, zum Beispiel [math]\displaystyle{ E }[/math], [math]\displaystyle{ KE }[/math], [math]\displaystyle{ EK }[/math] und [math]\displaystyle{ KEKE }[/math].
Schritt 1: Gedächtnis festlegen. Wie die Zustände eines DEA merken sich die Nichtterminale, was bisher erzeugt wurde: [math]\displaystyle{ S }[/math] steht für „noch kein [math]\displaystyle{ E }[/math] erzeugt“, [math]\displaystyle{ A }[/math] steht für „mindestens ein [math]\displaystyle{ E }[/math] erzeugt“.
Schritt 2: Regeln aufstellen. Solange noch kein [math]\displaystyle{ E }[/math] erzeugt ist, darf ein [math]\displaystyle{ K }[/math] folgen ([math]\displaystyle{ S \to KS }[/math]) oder das erste [math]\displaystyle{ E }[/math] ([math]\displaystyle{ S \to EA }[/math]). Danach dürfen beliebige Zeichen folgen ([math]\displaystyle{ A \to KA }[/math] und [math]\displaystyle{ A \to EA }[/math]), oder das Wort endet ([math]\displaystyle{ A \to \varepsilon }[/math]):
- [math]\displaystyle{ S \to KS \mid EA }[/math]
- [math]\displaystyle{ A \to KA \mid EA \mid \varepsilon }[/math]
Schritt 3: Prüfen. Das Wort [math]\displaystyle{ KEK }[/math] ist ableitbar:
- [math]\displaystyle{ S \Rightarrow KS \Rightarrow KEA \Rightarrow KEKA \Rightarrow KEK }[/math]
Ein Wort ohne [math]\displaystyle{ E }[/math] lässt sich nicht ableiten: Nur die Regel [math]\displaystyle{ S \to EA }[/math] führt zu [math]\displaystyle{ A }[/math], und nur bei [math]\displaystyle{ A }[/math] kann eine Ableitung enden.
Schritt 4: In die reguläre Form bringen. Die Regel [math]\displaystyle{ A \to \varepsilon }[/math] ist in einer regulären Grammatik nicht erlaubt. Sie wird gestrichen. Zum Ausgleich kommt zu jeder Regel, deren rechte Seite mit [math]\displaystyle{ A }[/math] endet, eine Regel ohne [math]\displaystyle{ A }[/math] hinzu: zu [math]\displaystyle{ S \to EA }[/math] die Regel [math]\displaystyle{ S \to E }[/math], zu [math]\displaystyle{ A \to KA }[/math] die Regel [math]\displaystyle{ A \to K }[/math] und zu [math]\displaystyle{ A \to EA }[/math] die Regel [math]\displaystyle{ A \to E }[/math]:
- [math]\displaystyle{ S \to KS \mid EA \mid E }[/math]
- [math]\displaystyle{ A \to KA \mid EA \mid K \mid E }[/math]
Das Wort [math]\displaystyle{ KEK }[/math] braucht jetzt einen Schritt weniger, weil die Ableitung mit [math]\displaystyle{ A \to K }[/math] endet:
- [math]\displaystyle{ S \Rightarrow KS \Rightarrow KEA \Rightarrow KEK }[/math]
Dieselbe reguläre Grammatik entsteht auch aus dem DEA im Beispiel Akzeptierte Sprache eines DEA beschreiben: [math]\displaystyle{ S }[/math] entspricht dort dem Zustand [math]\displaystyle{ q_0 }[/math], [math]\displaystyle{ A }[/math] dem Zustand [math]\displaystyle{ q_1 }[/math].
Regel ohne Terminal ersetzen
Die folgende rechtslineare Grammatik erzeugt alle Wörter aus beliebig vielen [math]\displaystyle{ K }[/math], auf die mindestens ein [math]\displaystyle{ E }[/math] folgt:
- [math]\displaystyle{ S \to KS \mid A }[/math]
- [math]\displaystyle{ A \to EA \mid E }[/math]
Die Regel [math]\displaystyle{ S \to A }[/math] hat rechts kein Terminal und ist deshalb in einer regulären Grammatik nicht erlaubt. Sie wird gestrichen. Dafür erhält [math]\displaystyle{ S }[/math] die rechten Seiten von [math]\displaystyle{ A }[/math], also [math]\displaystyle{ EA }[/math] und [math]\displaystyle{ E }[/math]:
- [math]\displaystyle{ S \to KS \mid EA \mid E }[/math]
- [math]\displaystyle{ A \to EA \mid E }[/math]
Das Wort [math]\displaystyle{ KEE }[/math] zeigt den Unterschied. Die erste Grammatik braucht den Zwischenschritt von [math]\displaystyle{ S }[/math] nach [math]\displaystyle{ A }[/math], die zweite nicht:
- [math]\displaystyle{ S \Rightarrow KS \Rightarrow KA \Rightarrow KEA \Rightarrow KEE }[/math]
- [math]\displaystyle{ S \Rightarrow KS \Rightarrow KEA \Rightarrow KEE }[/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: [math]\displaystyle{ K }[/math] allein oder [math]\displaystyle{ KE }[/math] gefolgt von mindestens einem weiteren [math]\displaystyle{ E }[/math]. Die Wörter sind [math]\displaystyle{ K }[/math], [math]\displaystyle{ KEE }[/math], [math]\displaystyle{ KEEE }[/math] und so weiter. Das Wort [math]\displaystyle{ KEE }[/math] 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]
Automaten zu einer regulären Grammatik konstruieren

Gesucht ist ein endlicher Automat für die reguläre Grammatik aus dem vorigen Beispiel:
- [math]\displaystyle{ S \to KB \mid K }[/math]
- [math]\displaystyle{ B \to EA }[/math]
- [math]\displaystyle{ A \to EA \mid E }[/math]
Schritt 1: Zustände anlegen. Die Nichtterminale [math]\displaystyle{ S }[/math], [math]\displaystyle{ B }[/math] und [math]\displaystyle{ A }[/math] werden zu Zuständen. Dazu kommt der neue Endzustand [math]\displaystyle{ X }[/math]. Der Startzustand ist [math]\displaystyle{ S }[/math].
Schritt 2: Regeln mit Nichtterminal übertragen. [math]\displaystyle{ S \to KB }[/math] ergibt einen Übergang von [math]\displaystyle{ S }[/math] nach [math]\displaystyle{ B }[/math] mit [math]\displaystyle{ K }[/math]. [math]\displaystyle{ B \to EA }[/math] ergibt einen Übergang von [math]\displaystyle{ B }[/math] nach [math]\displaystyle{ A }[/math] mit [math]\displaystyle{ E }[/math]. [math]\displaystyle{ A \to EA }[/math] ergibt eine Schleife an [math]\displaystyle{ A }[/math] mit [math]\displaystyle{ E }[/math].
Schritt 3: Regeln ohne Nichtterminal übertragen. [math]\displaystyle{ S \to K }[/math] ergibt einen Übergang von [math]\displaystyle{ S }[/math] nach [math]\displaystyle{ X }[/math] mit [math]\displaystyle{ K }[/math]. [math]\displaystyle{ A \to E }[/math] ergibt einen Übergang von [math]\displaystyle{ A }[/math] nach [math]\displaystyle{ X }[/math] mit [math]\displaystyle{ E }[/math].
| [math]\displaystyle{ \delta }[/math] | [math]\displaystyle{ K }[/math] | [math]\displaystyle{ E }[/math] |
|---|---|---|
| [math]\displaystyle{ \rightarrow S }[/math] | [math]\displaystyle{ \{B; X\} }[/math] | – |
| [math]\displaystyle{ B }[/math] | – | [math]\displaystyle{ \{A\} }[/math] |
| [math]\displaystyle{ A }[/math] | – | [math]\displaystyle{ \{A; X\} }[/math] |
| [math]\displaystyle{ {}^*X }[/math] | – | – |
Der Automat ist ein NEA: In [math]\displaystyle{ S }[/math] gibt es für [math]\displaystyle{ K }[/math] zwei Folgezustände, in [math]\displaystyle{ A }[/math] für [math]\displaystyle{ E }[/math] ebenfalls. Für das Wort [math]\displaystyle{ KEE }[/math] gibt es diese Pfade:
- [math]\displaystyle{ S \xrightarrow{K} B \xrightarrow{E} A \xrightarrow{E} A }[/math] (kein Endzustand)
- [math]\displaystyle{ S \xrightarrow{K} B \xrightarrow{E} A \xrightarrow{E} X }[/math] (akzeptiert)
- [math]\displaystyle{ S \xrightarrow{K} X }[/math] (bricht ab)
Ein Pfad liest das ganze Wort und endet im Endzustand [math]\displaystyle{ X }[/math]. Der Automat akzeptiert [math]\displaystyle{ KEE }[/math], so wie die Grammatik das Wort erzeugt.
Grammatik in eine rechtslineare Grammatik umformen
Die folgende Grammatik ist nicht rechtslinear, denn in der Regel für [math]\displaystyle{ S }[/math] steht das Nichtterminal [math]\displaystyle{ A }[/math] am Anfang:
- [math]\displaystyle{ S \to AE }[/math]
- [math]\displaystyle{ A \to KA \mid K }[/math]
Schritt 1: Sprache beschreiben. [math]\displaystyle{ A }[/math] erzeugt ein oder mehrere [math]\displaystyle{ K }[/math]: Die Regel [math]\displaystyle{ A \to KA }[/math] setzt ein weiteres [math]\displaystyle{ K }[/math] davor, die Regel [math]\displaystyle{ A \to K }[/math] beendet die Folge. [math]\displaystyle{ S \to AE }[/math] hängt genau ein [math]\displaystyle{ E }[/math] an. Die Sprache ist [math]\displaystyle{ \{K^n E \mid n \geq 1\} }[/math], dabei ist [math]\displaystyle{ K^n }[/math] eine Wortpotenz.
Schritt 2: Wörter von links nach rechts aufbauen. Jedes Wort beginnt mit [math]\displaystyle{ K }[/math]. Danach folgt entweder ein weiteres Wort derselben Sprache oder das abschließende [math]\displaystyle{ E }[/math]:
- [math]\displaystyle{ S \to KS \mid KE }[/math]
Schritt 3: Vergleichen. Das Wort [math]\displaystyle{ KKE }[/math] lässt sich mit beiden Grammatiken ableiten:
- [math]\displaystyle{ S \Rightarrow AE \Rightarrow KAE \Rightarrow KKE }[/math]
- [math]\displaystyle{ S \Rightarrow KS \Rightarrow KKE }[/math]
Die neue Grammatik ist rechtslinear. Die Regel [math]\displaystyle{ S \to KE }[/math] hat noch zwei Terminale. Für die reguläre Form wird sie wie im Beispiel Rechtslineare Grammatik umformen durch [math]\displaystyle{ S \to KB }[/math] und [math]\displaystyle{ B \to E }[/math] ersetzt.