Lektion 1.3

Minimierung von DEAs

45 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • unerreichbare Zustände eines DEA finden und streichen,

  • äquivalente Zustände mit dem Markierungsverfahren bestimmen und den Äquivalenzklassenautomaten aufstellen,

  • die Nerode-Relation einer Sprache bestimmen und mit dem Satz von Myhill-Nerode zeigen, dass eine Sprache nicht regulär ist,

  • begründen, warum der minimale DEA einer Sprache bis auf Umbenennung der Zustände eindeutig ist.

Vorausgesetzt: Deterministische endliche Automaten (DEA), Nichtdeterministische Automaten und die Potenzmengenkonstruktion

Dieselbe Sprache lässt sich mit sehr verschiedenen Automaten erkennen. Der folgende DEA über {0,1}\{0, 1\} nimmt genau die Wörter an, die auf 00 enden. Er hat fünf Zustände AA bis EE, den Startzustand AA und die Endzustände BB und DD:

Zustandmit 00 nachmit 11 nach
AA (Start)BBCC
BB (Endzustand)DDEE
CCBBCC
DD (Endzustand)DDEE
EEDDCC

Dabei genügen zwei Zustände: „das letzte Zeichen war eine 00“ und „alles andere“. Solche aufgeblähten Automaten entstehen ständig, etwa bei der Potenzmengenkonstruktion. Drei Fragen: Wie findet man systematisch einen kleinsten DEA für dieselbe Sprache? Ist er eindeutig? Und kann man der Sprache selbst ansehen, wie viele Zustände nötig sind, und ob überhaupt endlich viele reichen?

Vermute zuerst

Im Automaten oben: Welche Zustände kann man zusammenlegen, ohne die erkannte Sprache zu ändern?

Definition

Erweiterte Übergangsfunktion, Erreichbarkeit, reguläre Sprache

Sei A=(Q,Σ,δ,q0,F)A = (Q, \Sigma, \delta, q_0, F) ein DEA. Die erweiterte Übergangsfunktion δ^:Q×Σ∗→Q\hat{\delta}: Q \times \Sigma^* \to Q gibt an, wo der Automat landet, wenn er in qq startet und ein ganzes Wort liest (rekursive Definition unten). Mit Induktion über die Länge ∣v∣|v| von vv folgt δ^(q,uv)=δ^(δ^(q,u),v)\hat{\delta}(q, uv) = \hat{\delta}(\hat{\delta}(q, u), v).

Ein Zustand qq heißt erreichbar, wenn δ^(q0,w)=q\hat{\delta}(q_0, w) = q für ein Wort ww gilt, sonst unerreichbar. Eine Sprache L⊆Σ∗L \subseteq \Sigma^* heißt regulär, wenn ein DEA sie erkennt (gleichwertig: ein NEA).

δ^(q,ε)=q,δ^(q,wa)=δ(δ^(q,w),a)fu¨r w∈Σ∗, a∈Σ\hat{\delta}(q, \varepsilon) = q, \qquad \hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a) \quad \text{für } w \in \Sigma^*,\ a \in \Sigma
Beispiel

Ein DEA mit Ballast

Über Σ={a,b}\Sigma = \{a, b\} sei der folgende DEA gegeben; der Pfeil markiert den Start AA, der Stern den einzigen Endzustand EE. Er nimmt genau die Wörter an, die auf abbabb enden. Das Beispiel begleitet uns durch die Lektion.

δab→ABCBBDCBCDBE∗ EBCFEF\begin{array}{c|cc} \delta & a & b \\ \hline \to A & B & C \\ B & B & D \\ C & B & C \\ D & B & E \\ {*}\,E & B & C \\ F & E & F \end{array}

BB bedeutet „endet auf aa“, DD „endet auf abab“, EE „endet auf abbabb“. AA steht für das leere Wort, CC für Wörter, die auf bb, aber weder auf abab noch auf abbabb enden; in beiden Fällen ist am Ende nichts von abbabb angefangen.

Schritt 1: unerreichbare Zustände streichen. Eine Breitensuche ab AA findet BB und CC, dann DD, dann EE. FF wird nie erreicht, denn nur von FF selbst führt ein Pfeil nach FF. Wir streichen FF; die Sprache bleibt gleich, weil kein Lauf ab AA je FF besucht. Die Suche sieht jeden Pfeil höchstens einmal an: O(∣Q∣⋅∣Σ∣)O(|Q| \cdot |\Sigma|) Schritte.

Definition

Äquivalente Zustände

Zwei Zustände p,qp, q heißen äquivalent, p∼qp \sim q, wenn sie für jedes Restwort dieselbe Entscheidung treffen (Formel unten), sonst unterscheidbar. Ein Wort ww, für das genau einer der Zustände δ^(p,w)\hat{\delta}(p, w), δ^(q,w)\hat{\delta}(q, w) in FF liegt, heißt trennendes Wort. Mit Lq={w:δ^(q,w)∈F}L_q = \{w : \hat{\delta}(q, w) \in F\}, der Sprache ab qq, gilt p∼qp \sim q genau dann, wenn Lp=LqL_p = L_q. Also ist ∼\sim eine Äquivalenzrelation; ihre Klassen schreiben wir [q][q].

Beispiel: Im Ballast-Automaten ist A∼CA \sim C: Beide sind keine Endzustände, beide gehen mit aa nach BB und mit bb nach CC.

Gegenbeispiel: A≁DA \not\sim D, denn bb führt DD nach E∈FE \in F und AA nach C∉FC \notin F. Auch zwei Nicht-Endzustände können also unterscheidbar sein. Ein End- und ein Nicht-Endzustand werden immer durch ε\varepsilon getrennt.

p∼q:⟺fu¨r alle w∈Σ∗: δ^(p,w)∈F  ⟺  δ^(q,w)∈Fp \sim q \quad :\Longleftrightarrow \quad \text{für alle } w \in \Sigma^*: \ \hat{\delta}(p, w) \in F \iff \hat{\delta}(q, w) \in F
Satz

Lemma: Äquivalenz vererbt sich auf Nachfolger

Aus p∼qp \sim q folgt δ(p,a)∼δ(q,a)\delta(p, a) \sim \delta(q, a) für jedes a∈Σa \in \Sigma. Gleichwertig: Trennt ww die Zustände δ(p,a)\delta(p, a) und δ(q,a)\delta(q, a), so trennt awaw die Zustände pp und qq.

Kurz geprüft

Welches Wort trennt im Ballast-Automaten die Zustände BB und CC?

Schritt für Schritt

Das Markierungsverfahren am Ballast-Automaten

Nach dem Streichen von FF bleiben A,B,C,D,EA, B, C, D, E mit Endzustand EE, also (52)=10\binom{5}{2} = 10 Paare. Die Schreibweise {A,D}→b{C,E}\{A, D\} \xrightarrow{b} \{C, E\} heißt: δ(A,b)=C\delta(A, b) = C und δ(D,b)=E\delta(D, b) = E.

  1. Runde 0. Markiert werden die Paare mit genau einem Endzustand: {A,E}\{A, E\}, {B,E}\{B, E\}, {C,E}\{C, E\}, {D,E}\{D, E\}. Unmarkiert bleiben {A,B}\{A, B\}, {A,C}\{A, C\}, {A,D}\{A, D\}, {B,C}\{B, C\}, {B,D}\{B, D\}, {C,D}\{C, D\}.

Schritt 1 von 4
Satz

Korrektheit und Laufzeit des Markierungsverfahrens

Sei AA ein DEA mit nn Zuständen über Σ\Sigma. Ein Paar {p,q}\{p, q\} mit p≠qp \neq q ist bis einschließlich Runde kk genau dann markiert, wenn es ein trennendes Wort der Länge höchstens kk hat. Am Ende sind also genau die unterscheidbaren Paare markiert. Das Verfahren braucht O(n3∣Σ∣)O(n^3 |\Sigma|) Schritte.

Definition

Äquivalenzklassenautomat

Der Äquivalenzklassenautomat A/∼A/{\sim} hat die Klassen [q][q] als Zustände, den Start [q0][q_0], die Endzustände [q][q] mit q∈Fq \in F und die Übergänge unten. Das ist unabhängig vom gewählten Vertreter: Nach dem Lemma folgt δ(p,a)∼δ(q,a)\delta(p, a) \sim \delta(q, a) aus p∼qp \sim q, und äquivalente Zustände liegen beide in FF oder beide nicht (Wort ε\varepsilon). Mit Induktion über ∣w∣|w| ist δ^′([q],w)=[δ^(q,w)]\hat{\delta}'([q], w) = [\hat{\delta}(q, w)]. Also nimmt A/∼A/{\sim} ab [q][q] dieselben Wörter an wie AA ab qq, insbesondere L(A/∼)=L(A)L(A/{\sim}) = L(A).

δ′([q],a)=[δ(q,a)]fu¨r q∈Q, a∈Σ\delta'([q], a) = [\delta(q, a)] \qquad \text{für } q \in Q,\ a \in \Sigma
Beispiel

Der verkleinerte Ballast-Automat

Aus den Klassen {A,C}\{A, C\}, {B}\{B\}, {D}\{D\}, {E}\{E\} entsteht ein DEA mit vier Zuständen. Den Übergang einer Klasse liest man an einem beliebigen Vertreter ab, etwa δ′([A],b)=[δ(A,b)]=[C]=[A]\delta'([A], b) = [\delta(A, b)] = [C] = [A].

δ′ab→[A]={A,C}[B][A][B][B][D][D][B][E]∗ [E][B][A]\begin{array}{c|cc} \delta' & a & b \\ \hline \to [A] = \{A, C\} & [B] & [A] \\ [B] & [B] & [D] \\ [D] & [B] & [E] \\ {*}\,[E] & [B] & [A] \end{array}

Jetzt hat jeder Zustand eine Bedeutung: „nichts von abbabb angefangen“, „endet auf aa“, „endet auf abab“, „endet auf abbabb“. Dass drei Zustände nicht reichen, zeigt der Satz von Myhill-Nerode unten.

Endet auf 0: fünf Zustände, wo zwei reichen
0101010101ABCDE

Der Pfeil von links zeigt den Start. Ein Doppelkreis ist ein Zustand, in dem ein Wort angenommen wird. Der hervorgehobene Zustand ist gerade aktiv.

  1. 0
  2. 1
  3. 0
Im Simulator öffnen

Start. Der Automat steht in A. Drücke „Schritt“, um das erste Zeichen zu lesen.

Der Automat aus der Einleitung. Mit Schritt liest er das Wort Zeichen für Zeichen. Über Im Simulator öffnen kannst du eigene Wörter eingeben und den Automaten minimieren lassen.

Probier es aus

Kurz geprüft

Wie viele der 1010 Paare des Automaten „endet auf 00“ bleiben im Markierungsverfahren unmarkiert?

Häufige Fehler

Nur gleiche Zeilen zusammenlegen, unerreichbare Zustände vergessen

Ein verbreiteter Schnellweg: In der Tabelle Zustände mit gleicher Zeile (und gleichem Endzustand-Status) zusammenlegen und den Automaten dann für minimal halten. Bei „endet auf 00“ findet man so AA mit CC und BB mit DD und behält drei Zustände.

Ebenso falsch ist es, unerreichbare Zustände stehen zu lassen. Im Ballast-Automaten ist FF von allen anderen unterscheidbar (von EE durch ε\varepsilon, von den übrigen durch aa), bildet also eine eigene Klasse: Es blieben fünf statt vier Zustände.

Richtig ist

Gleiche Zeilen sind hinreichend für Äquivalenz, aber nicht notwendig: EE geht mit 00 nach DD statt nach BB, und trotzdem ist E∼AE \sim A, weil B∼DB \sim D. Erst das Markierungsverfahren findet alle Äquivalenzen. Die Reihenfolge ist fest: zuerst unerreichbare Zustände streichen, dann markieren.

Definition

Nerode-Relation

Dieselbe Idee funktioniert für Wörter, ganz ohne Automat. Für eine Sprache L⊆Σ∗L \subseteq \Sigma^* heißen x,y∈Σ∗x, y \in \Sigma^* Nerode-äquivalent, x≡Lyx \equiv_L y, wenn kein Anhang zz sie unterscheidet (Formel unten). Das ist eine Äquivalenzrelation mit Klassen [x]L[x]_L; deren Anzahl heißt Index, sie kann unendlich sein. Aus x≡Lyx \equiv_L y folgt xa≡Lyaxa \equiv_L ya, denn ein Anhang zz an xa,yaxa, ya ist der Anhang azaz an x,yx, y.

Beispiel: Für „endet auf 00“ entscheidet bei nichtleerem zz nur das letzte Zeichen von zz. Zwei Wörter sind also äquivalent, wenn beide in LL liegen oder beide nicht. Der Index ist 22.

Gegenbeispiel zur Endlichkeit: L={anbn:n≥0}L = \{a^n b^n : n \geq 0\}, dabei ist ana^n das Wort aus nn Zeichen aa. Für i≠ji \neq j ist aibi∈La^i b^i \in L, aber ajbi∉La^j b^i \notin L; der Anhang bib^i trennt aia^i von aja^j. Die Wörter ε,a,aa,…\varepsilon, a, aa, \dots liegen in lauter verschiedenen Klassen, der Index ist unendlich.

x≡Ly:⟺fu¨r alle z∈Σ∗: xz∈L  ⟺  yz∈Lx \equiv_L y \quad :\Longleftrightarrow \quad \text{für alle } z \in \Sigma^*: \ xz \in L \iff yz \in L
Satz

Satz von Myhill-Nerode

Eine Sprache L⊆Σ∗L \subseteq \Sigma^* ist genau dann regulär, wenn ≡L\equiv_L endlichen Index hat. Dann hat jeder DEA für LL mindestens so viele Zustände, wie ≡L\equiv_L Klassen hat, und es gibt einen mit genau so vielen.

Beispiel

Nicht-Regularität und untere Schranken

Für L={anbn:n≥0}L = \{a^n b^n : n \geq 0\} sind die Wörter a0,a1,a2,…a^0, a^1, a^2, \dots paarweise nicht äquivalent, wie oben gezeigt. Nach Myhill-Nerode gibt es also keinen DEA für LL. Das beweist, was die Lektion über DEAs nur begründet hat.

Ebenso bekommt man untere Schranken. Für „endet auf abbabb“ sind ε\varepsilon, aa, abab, abbabb paarweise nicht äquivalent: abbabb trennt ε\varepsilon von den anderen, ε\varepsilon und aa trennt bbbb, abab trennt bb von ε\varepsilon und aa. Jeder DEA braucht also vier Zustände, der verkleinerte Ballast-Automat ist minimal.

Satz

Eindeutigkeit des Minimalautomaten

Sei LL regulär und A=(Q,Σ,δ,q0,F)A = (Q, \Sigma, \delta, q_0, F) ein DEA für LL mit kleinstmöglicher Zustandszahl. Dann gibt es eine Bijektion φ\varphi von QQ auf die Zustände des Nerode-Automaten mit φ(q0)=[ε]L\varphi(q_0) = [\varepsilon]_L, φ(δ(q,a))=δL(φ(q),a)\varphi(\delta(q, a)) = \delta_L(\varphi(q), a) und q∈F  ⟺  φ(q)q \in F \iff \varphi(q) Endzustand. AA ist also bis auf Umbenennung ALA_L. Außerdem liefert „unerreichbare Zustände streichen, dann A/∼A/{\sim} bilden“ aus jedem DEA für LL einen minimalen.

Zusammenfassung

  • Unerreichbare Zustände findet eine Suche ab dem Start in O(∣Q∣⋅∣Σ∣)O(|Q| \cdot |\Sigma|); sie werden zuerst gestrichen.

  • p∼qp \sim q heißt: gleiche Entscheidung für jedes Restwort. Aus p∼qp \sim q folgt δ(p,a)∼δ(q,a)\delta(p, a) \sim \delta(q, a).

  • Das Markierungsverfahren markiert zuerst End- gegen Nicht-Endzustände, dann jedes Paar, das mit einem Zeichen auf ein markiertes Paar führt. Unmarkiert bleiben genau die äquivalenten Paare; Laufzeit O(n3∣Σ∣)O(n^3 |\Sigma|).

  • Der Äquivalenzklassenautomat A/∼A/{\sim} legt äquivalente Zustände zusammen und erkennt dieselbe Sprache.

  • Satz von Myhill-Nerode: LL ist genau dann regulär, wenn ≡L\equiv_L endlich viele Klassen hat; ihre Zahl ist die Zustandszahl des kleinsten DEA.

  • Unendlich viele paarweise unterscheidbare Wörter beweisen Nicht-Regularität, etwa aia^i für {anbn:n≥0}\{a^n b^n : n \geq 0\}.

  • Der minimale DEA ist bis auf Umbenennung eindeutig; Streichen und Markieren liefern ihn aus jedem DEA.

Übungen

Aufgabe 1Multiple Choice

Ein DEA über {a,b}\{a, b\} hat die Zustände p0,…,p3p_0, \dots, p_3, den Start p0p_0 und die Übergänge δ(p0,a)=p1\delta(p_0, a) = p_1, δ(p0,b)=p0\delta(p_0, b) = p_0, δ(p1,a)=p0\delta(p_1, a) = p_0, δ(p1,b)=p1\delta(p_1, b) = p_1, δ(p2,a)=p3\delta(p_2, a) = p_3, δ(p2,b)=p0\delta(p_2, b) = p_0, δ(p3,a)=p2\delta(p_3, a) = p_2, δ(p3,b)=p3\delta(p_3, b) = p_3. Welche Zustände sind unerreichbar?

Aufgabe 2Numerisch

Ein DEA über {0,1}\{0, 1\} hat die Zustände r0,…,r5r_0, \dots, r_5, den Start r0r_0, die Übergänge δ(ri,0)=ri\delta(r_i, 0) = r_i und δ(ri,1)=r(i+1) mod 6\delta(r_i, 1) = r_{(i + 1) \bmod 6} und die Endzustände r0r_0 und r3r_3. Wie viele Zustände hat der Äquivalenzklassenautomat?

Aufgabe 3Multiple Choice

Sei LL die Sprache der Wörter über {a,b}\{a, b\}, die auf abab enden. Welches Wortpaar ist Nerode-äquivalent bezüglich LL?

Aufgabe 4Numerisch

Sei LL die Sprache der Wörter über {a,b}\{a, b\} mit genau zwei aa. Wie viele Klassen hat ≡L\equiv_L?

Aufgabe 5Freitext

Beweise mit dem Satz von Myhill-Nerode, dass L={anbm:0≤n≤m}L = \{a^n b^m : 0 \leq n \leq m\} nicht regulär ist.

Aufgabe 6Freitext

Sei k≥1k \geq 1 und LkL_k die Sprache der Wörter über {0,1}\{0, 1\}, deren kk-tes Zeichen von hinten eine 11 ist. Zeige, dass jeder DEA für LkL_k mindestens 2k2^k Zustände hat.