Minimierung von DEAs
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 nimmt genau die Wörter an, die auf enden. Er hat fünf Zustände bis , den Startzustand und die Endzustände und :
| Zustand | mit nach | mit nach |
|---|---|---|
| (Start) | ||
| (Endzustand) | ||
| (Endzustand) | ||
Dabei genügen zwei Zustände: „das letzte Zeichen war eine “ 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?
Im Automaten oben: Welche Zustände kann man zusammenlegen, ohne die erkannte Sprache zu ändern?
Erweiterte Übergangsfunktion, Erreichbarkeit, reguläre Sprache
Sei ein DEA. Die erweiterte Übergangsfunktion gibt an, wo der Automat landet, wenn er in startet und ein ganzes Wort liest (rekursive Definition unten). Mit Induktion über die Länge von folgt .
Ein Zustand heißt erreichbar, wenn für ein Wort gilt, sonst unerreichbar. Eine Sprache heißt regulär, wenn ein DEA sie erkennt (gleichwertig: ein NEA).
Ein DEA mit Ballast
Ein DEA mit Ballast
Über sei der folgende DEA gegeben; der Pfeil markiert den Start , der Stern den einzigen Endzustand . Er nimmt genau die Wörter an, die auf enden. Das Beispiel begleitet uns durch die Lektion.
bedeutet „endet auf “, „endet auf “, „endet auf “. steht für das leere Wort, für Wörter, die auf , aber weder auf noch auf enden; in beiden Fällen ist am Ende nichts von angefangen.
Schritt 1: unerreichbare Zustände streichen. Eine Breitensuche ab findet und , dann , dann . wird nie erreicht, denn nur von selbst führt ein Pfeil nach . Wir streichen ; die Sprache bleibt gleich, weil kein Lauf ab je besucht. Die Suche sieht jeden Pfeil höchstens einmal an: Schritte.
Äquivalente Zustände
Zwei Zustände heißen äquivalent, , wenn sie für jedes Restwort dieselbe Entscheidung treffen (Formel unten), sonst unterscheidbar. Ein Wort , für das genau einer der Zustände , in liegt, heißt trennendes Wort. Mit , der Sprache ab , gilt genau dann, wenn . Also ist eine Äquivalenzrelation; ihre Klassen schreiben wir .
Beispiel: Im Ballast-Automaten ist : Beide sind keine Endzustände, beide gehen mit nach und mit nach .
Gegenbeispiel: , denn führt nach und nach . Auch zwei Nicht-Endzustände können also unterscheidbar sein. Ein End- und ein Nicht-Endzustand werden immer durch getrennt.
Lemma: Äquivalenz vererbt sich auf Nachfolger
Aus folgt für jedes . Gleichwertig: Trennt die Zustände und , so trennt die Zustände und .
Es ist und ebenso für . Treffen und für dieselbe Entscheidung, so treffen und für dieselbe. Das gilt für jedes .
Welches Wort trennt im Ballast-Automaten die Zustände und ?
Das Markierungsverfahren am Ballast-Automaten
Das Markierungsverfahren am Ballast-Automaten
Nach dem Streichen von bleiben mit Endzustand , also Paare. Die Schreibweise heißt: und .
Runde 0. Markiert werden die Paare mit genau einem Endzustand: , , , . Unmarkiert bleiben , , , , , .
Korrektheit und Laufzeit des Markierungsverfahrens
Sei ein DEA mit Zuständen über . Ein Paar mit ist bis einschließlich Runde genau dann markiert, wenn es ein trennendes Wort der Länge höchstens hat. Am Ende sind also genau die unterscheidbaren Paare markiert. Das Verfahren braucht Schritte.
Beweisidee: Induktion, einmal über die Runde, einmal über die Wortlänge.
Markiert, also trennbar. In Runde trennt . Wird in Runde wegen markiert, so war in einer Runde markiert. Nach Induktionsvoraussetzung trennt ein mit dieses Paar, nach dem Lemma trennt die Zustände , und .
Trennbar, also markiert. Induktion über die Länge eines trennenden Wortes . Für ist : Markierung in Runde . Für mit trennt die (also verschiedenen) Nachfolger , ; ihr Paar ist nach Induktionsvoraussetzung bis Runde markiert, also spätestens in Runde . Das Anhalten nach einer leeren Runde schadet nicht, denn jede weitere Runde fände dieselbe Tabelle vor.
Laufzeit. Eine Runde kostet . „Kein trennendes Wort der Länge “ ist eine Äquivalenzrelation auf ; jede Runde, die etwas markiert, zerlegt eine ihrer Klassen. Da es höchstens Klassen gibt, markieren höchstens Runden nach Runde etwas, insgesamt gibt es also höchstens Runden. Der Algorithmus von Hopcroft schafft sogar .
Äquivalenzklassenautomat
Der Äquivalenzklassenautomat hat die Klassen als Zustände, den Start , die Endzustände mit und die Übergänge unten. Das ist unabhängig vom gewählten Vertreter: Nach dem Lemma folgt aus , und äquivalente Zustände liegen beide in oder beide nicht (Wort ). Mit Induktion über ist . Also nimmt ab dieselben Wörter an wie ab , insbesondere .
Der verkleinerte Ballast-Automat
Der verkleinerte Ballast-Automat
Aus den Klassen , , , entsteht ein DEA mit vier Zuständen. Den Übergang einer Klasse liest man an einem beliebigen Vertreter ab, etwa .
Jetzt hat jeder Zustand eine Bedeutung: „nichts von angefangen“, „endet auf “, „endet auf “, „endet auf “. Dass drei Zustände nicht reichen, zeigt der Satz von Myhill-Nerode unten.
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
- 1
- 0
Start. Der Automat steht in A. Drücke „Schritt“, um das erste Zeichen zu lesen.
Probier es aus
Wie viele der Paare des Automaten „endet auf “ bleiben im Markierungsverfahren unmarkiert?
Nur gleiche Zeilen zusammenlegen, unerreichbare Zustände vergessen
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 “ findet man so mit und mit und behält drei Zustände.
Ebenso falsch ist es, unerreichbare Zustände stehen zu lassen. Im Ballast-Automaten ist von allen anderen unterscheidbar (von durch , von den übrigen durch ), bildet also eine eigene Klasse: Es blieben fünf statt vier Zustände.
Gleiche Zeilen sind hinreichend für Äquivalenz, aber nicht notwendig: geht mit nach statt nach , und trotzdem ist , weil . Erst das Markierungsverfahren findet alle Äquivalenzen. Die Reihenfolge ist fest: zuerst unerreichbare Zustände streichen, dann markieren.
Nerode-Relation
Dieselbe Idee funktioniert für Wörter, ganz ohne Automat. Für eine Sprache heißen Nerode-äquivalent, , wenn kein Anhang sie unterscheidet (Formel unten). Das ist eine Äquivalenzrelation mit Klassen ; deren Anzahl heißt Index, sie kann unendlich sein. Aus folgt , denn ein Anhang an ist der Anhang an .
Beispiel: Für „endet auf “ entscheidet bei nichtleerem nur das letzte Zeichen von . Zwei Wörter sind also äquivalent, wenn beide in liegen oder beide nicht. Der Index ist .
Gegenbeispiel zur Endlichkeit: , dabei ist das Wort aus Zeichen . Für ist , aber ; der Anhang trennt von . Die Wörter liegen in lauter verschiedenen Klassen, der Index ist unendlich.
Satz von Myhill-Nerode
Eine Sprache ist genau dann regulär, wenn endlichen Index hat. Dann hat jeder DEA für mindestens so viele Zustände, wie Klassen hat, und es gibt einen mit genau so vielen.
Beweisidee: Ein DEA führt zwei Wörter nur dann in denselben Zustand, wenn sie Nerode-äquivalent sind; umgekehrt bilden die Klassen selbst einen DEA.
DEA, also endlicher Index. Sei ein DEA für . Aus folgt für jedes , also . Wörter aus verschiedenen Klassen landen also in verschiedenen Zuständen, und es gibt höchstens Klassen.
Endlicher Index, also DEA. Der Nerode-Automat hat die Klassen als Zustände, die Übergänge , den Start und die Endzustände mit . Wohldefiniert ist das, weil aus auch folgt und der Anhang zeigt, dass äquivalente Wörter beide in liegen oder beide nicht. Mit Induktion ist , also .
Nicht-Regularität und untere Schranken
Nicht-Regularität und untere Schranken
Für sind die Wörter paarweise nicht äquivalent, wie oben gezeigt. Nach Myhill-Nerode gibt es also keinen DEA für . Das beweist, was die Lektion über DEAs nur begründet hat.
Ebenso bekommt man untere Schranken. Für „endet auf “ sind , , , paarweise nicht äquivalent: trennt von den anderen, und trennt , trennt von und . Jeder DEA braucht also vier Zustände, der verkleinerte Ballast-Automat ist minimal.
Eindeutigkeit des Minimalautomaten
Sei regulär und ein DEA für mit kleinstmöglicher Zustandszahl. Dann gibt es eine Bijektion von auf die Zustände des Nerode-Automaten mit , und Endzustand. ist also bis auf Umbenennung . Außerdem liefert „unerreichbare Zustände streichen, dann bilden“ aus jedem DEA für einen minimalen.
Nach Myhill-Nerode ist der Index von . Jeder Zustand ist erreichbar, sonst gäbe es durch Streichen einen kleineren DEA. Setze für ein mit ; nach dem ersten Beweisteil oben hängt das nicht von der Wahl von ab. ist surjektiv, weil , und wegen gleicher Elementzahl bijektiv. Führt nach , so nach , also . Und .
Zum Zusatz: Nach Streichen und Zusammenlegen ist jeder Zustand erreichbar, und je zwei verschiedene Zustände sind unterscheidbar, weil Zustände aus verschiedenen Klassen von nicht äquivalent sind. Führen in verschiedene Zustände, die trennt, so ist genau eines von in , also . Es gibt also höchstens so viele Zustände wie Nerode-Klassen und nach Myhill-Nerode mindestens so viele.
Zusammenfassung
Unerreichbare Zustände findet eine Suche ab dem Start in ; sie werden zuerst gestrichen.
heißt: gleiche Entscheidung für jedes Restwort. Aus folgt .
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 .
Der Äquivalenzklassenautomat legt äquivalente Zustände zusammen und erkennt dieselbe Sprache.
Satz von Myhill-Nerode: ist genau dann regulär, wenn endlich viele Klassen hat; ihre Zahl ist die Zustandszahl des kleinsten DEA.
Unendlich viele paarweise unterscheidbare Wörter beweisen Nicht-Regularität, etwa für .
Der minimale DEA ist bis auf Umbenennung eindeutig; Streichen und Markieren liefern ihn aus jedem DEA.
Übungen
Ein DEA über hat die Zustände , den Start und die Übergänge , , , , , , , . Welche Zustände sind unerreichbar?
Ein DEA über hat die Zustände , den Start , die Übergänge und und die Endzustände und . Wie viele Zustände hat der Äquivalenzklassenautomat?
Sei die Sprache der Wörter über , die auf enden. Welches Wortpaar ist Nerode-äquivalent bezüglich ?
Sei die Sprache der Wörter über mit genau zwei . Wie viele Klassen hat ?
Beweise mit dem Satz von Myhill-Nerode, dass nicht regulär ist.
Sei und die Sprache der Wörter über , deren -tes Zeichen von hinten eine ist. Zeige, dass jeder DEA für mindestens Zustände hat.