MINT lernen

Reguläre Grammatik und DEA

Jeder Pfeil eines DEA ist eine Regel und jede Regel ein Pfeil — aber was wird aus den Endzuständen?

1

Vom DEA zur Grammatik

Ein Zustand speichert, was über das gelesene Wort bekannt ist — ein Nichtterminal, was über das erzeugte Wort bekannt ist. Das ist dieselbe Information.

  • Zustand → Nichtterminal:jeder Zustand wird ein Nichtterminal; der Startzustand wird zum Startsymbol \(S\).
  • Pfeil → Regel:ein Pfeil \(z\xrightarrow{a}z'\) wird zur Regel \(Z\to aZ'\); ein Pfeil mit „a, b“ ergibt zwei Regeln.
  • Endzustand → ε-Regel:jeder Endzustand \(Z\) bekommt die Regel \(Z\to\varepsilon\).
  • Alphabet:die Terminale sind das Eingabealphabet: \(T=\Sigma\).
  • Fehlerzustand:fällt weg — aus zF entsteht nie ein Wort.

Zerlege den Graphen und lege die Teile als Regeln um: Wähle ein Zeichen auf einem Pfeil (oder die Ende-Marke eines Endzustands) und dann die Regelzeile, in die es gehört. Im Modus „Grammatik → DEA“ geht es rückwärts: Regel wählen, dann den Zustand, auf den der Pfeil zeigt.

Graph zerlegen, Regeln umlegen

Halte fest: Beim Umlegen geht nichts verloren und nichts kommt hinzu — jeder Pfeil wird genau eine Regel, jeder Endzustand eine ε-Regel. Deshalb beschreiben DEA und Grammatik dieselbe Sprache.

2

Von der Grammatik zum DEA

  • Nichtterminal → Zustand:jedes Nichtterminal wird ein Zustand, \(S\) der Startzustand.
  • \(A\to aB\):Pfeil von \(A\) nach \(B\) mit \(a\).
  • \(A\to\varepsilon\):\(A\) wird Endzustand.
  • \(A\to a\):Pfeil mit \(a\) in einen neuen Endzustand zE, von dem kein Pfeil ausgeht.
  • Deterministisch:je Nichtterminal und Zeichen höchstens eine Regel — sonst entsteht kein DEA. Fehlende Übergänge führen nach zF.

Warum beide dieselbe Sprache beschreiben, zeigt der DEA aus dem Applet („Länge durch 3 teilbar“) mit dem Wort abb:

Herleitung:

\(z_0 \xrightarrow{a} z_1 \xrightarrow{b} z_2 \xrightarrow{b} z_0\)
Lauf im DEA
Der DEA liest abb und endet im Endzustand z0 — akzeptiert.
\(S \Rightarrow a\textcolor{#7c5fb5}{A}\)
\(z_0\xrightarrow{a}z_1\)
Der erste Pfeil ist die Regel \(S\to aA\).
\(aA \Rightarrow ab\textcolor{#7c5fb5}{B}\)
\(z_1\xrightarrow{b}z_2\)
Das Nichtterminal am Ende der Satzform ist immer der aktuelle Zustand.
\(abB \Rightarrow abb\textcolor{#7c5fb5}{S}\)
\(z_2\xrightarrow{b}z_0\)
Auch der Rückweg zum Start ist nur eine Regel: \(B\to bS\).
\(abbS \Rightarrow abb\)
\(S\to\varepsilon\)
Weil z0 Endzustand ist, darf S verschwinden. Jeder akzeptierende Lauf ist eine Ableitung und umgekehrt: \(L(\text{DEA})=L(G)\).
Merke

DEA ↔ reguläre Grammatik: Zustand = Nichtterminal, Pfeil \(z\xrightarrow{a}z'\) = Regel \(Z\to aZ'\), Endzustand \(Z\) = Regel \(Z\to\varepsilon\). DEA und reguläre Grammatiken beschreiben genau dieselben Sprachen: die regulären Sprachen.

3

Allgemeine Hinweise

Satzform zeigt den Zustand

Das Nichtterminal am Ende jeder Satzform ist der Zustand, in dem der DEA nach dem bisher erzeugten Anfangsstück steht. So lässt sich jede Umwandlung schnell kontrollieren.

A → a braucht zE

Eine Regel ohne Nichtterminal endet das Wort. Dafür gibt es einen eigenen Endzustand zE ohne ausgehende Pfeile — ein Pfeil zurück nach A würde zu viel akzeptieren.

Zwei Regeln, ein Zeichen

Gibt es \(A\to aB\) und \(A\to aC\), hätte A zwei Pfeile mit a — kein DEA. Dann fasst man B und C zu einem neuen Nichtterminal zusammen, das die Regeln beider übernimmt.

Videos