+ All Categories
Transcript
Page 1: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

Endliche Automaten

Prof. Dr. W. Vogler

Sommersemester 2011

1

Page 2: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

INHALTSVERZEICHNIS i

Inhaltsverzeichnis

1 Wörter und Monoide 1

2 Endliche Automaten 5

3 Anwendung: Diophantische Gleichungen 11

4 Minimierung endlicher Automaten 15

4.1 Der Minimalautomat und der Satz von Nerode . . . . . . . . . . . . . . . . . 15

4.2 Ein Verfahren zur Minimierung . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.3 Minimierungsverfahren von Hopcroft . . . . . . . . . . . . . . . . . . . . . . . 20

4.4 Gleicheit regulärer Sprachen und Größe minimaler Automaten . . . . . . . . . 24

5 Pumping–Lemma 28

6 Mealy-Automaten 31

7 Moore-Automaten 37

8 Abschlußeigenschaften 42

9 Büchi-Automaten 49

9.1 Definition und Abschlusseigenschaften . . . . . . . . . . . . . . . . . . . . . . 50

9.2 Model Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

9.3 Variationen von Büchi-Automaten . . . . . . . . . . . . . . . . . . . . . . . . 56

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 3: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

1 WÖRTER UND MONOIDE 1

Diese Vorlesung befaßt sich mit endlichen Automaten in Ergänzung der Grundvorlesung„Einführung in die theoretische Informatik“. Insbesondere werden wir auch Automaten mitAusgabe sowie Automaten für unendliche Wörter behandeln. Um die Nützlichkeit endlicherAutomaten in verschiedenen Bereichen aufzuzeigen, werden kurz Verbindungen zur Logik her-gestellt, wofür die Kenntnis der Prädikatenlogik erster Stufe (Syntax und Semantik) vorausge-setzt wird; Kenntnisse der temporalen Logik, speziell der Propositional Linear-Time TemporalLogic PLTL, wären günstig. Für einige algorithmische Fragestellungen werden entsprechendeKenntnisse aus Informatik III vorausgesetzt; insbesondere sollten Tiefen- und Breitensuche,aber auch NP-Vollständigkeit bekannt sein.

Literatur:Brauer: Automatentheorie. 1984Hopcroft, (Motwani,) Ullman: Introduction to Automata Theory, Languages and Computa-tion.dtsch.: Einführung in die Automatentheorie, Formale Sprachen und KomplexitätstheorieSchöning: Theoretische Informatik kurz gefaßt. 5. AuflageThomas: Automata on Infinite Objects. Chapter 4 in Handbook of Theoretical ComputerScience, Hrsg. van LeeuwenThomas: Languages, Automata, and Logic. In: Handbook of Formal Languages, Vol. 3, Hrsg.Rozenberg, Salomaa

1 Wörter und Monoide

Wort: Sequenz von Zeichen aus einem gegebenen Zeichenvorrat (z.B. C-Programm, voneinem System ausgeführte Aktionsfolgen)formale Sprache: Menge von Wörtern (z.B. der syntaktisch korrekten C-Programme, allerAktionsfolgen eines Systems)

Definition 1.1. Ein Alphabet (Zeichenvorrat) Σ ist eine endliche Menge; ihre Elemente heißenBuchstaben (Zeichen); oft ist zusätzlich eine totale Ordnung auf Σ gegeben.

Eine Folge von Buchstabenw = a1 · · · an mit ai ∈ Σ heißt Wort oder Zeichenkette überΣ. |w| ist die Länge des Wortes. Das Wort mit Länge 0 ist das leere Wort und wird mit λbezeichnet. Ist A ⊆ Σ, so ist |w|A die Anzahl der Zeichen von w, die in A liegen.

Σn bezeichnet die Menge der Wörter mit Länge n. Wörter der Länge 1 sind einfach Buch-staben; also Σ1 = Σ und Σ0 = {λ}.

Σ+ =⋃

n≥1

Σn Menge der nichtleeren Wörter

Σ∗ =⋃

n≥0

Σn = Σ+∪̇{λ} Menge aller Wörter

Eine formale Sprache über Σ ist eine Teilmenge L ⊆ Σ∗. 2

Definition 1.2. Die Konkatenation der Wörter v = a1 · · · an ∈ Σn und w = b1 · · · bm ∈ Σm

ist v · w = a1 · · · anb1 · · · bm ∈ Σn+m; wir schreiben oft vw . 2

Beispiele 1.3. • Wörter mit gleich vielen a und b: |w|a = |w|b

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 4: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

1 WÖRTER UND MONOIDE 2

• Wörter gerader Länge: |w| mod 2 = 0

• Kommunikation eines Pufferspeichers: Hier soll e für eine Eingabe in den Puffer, abzw. b für eine Ausgabe auf Kanal A bzw. B stehen. w ∈ {a, b, e}∗ ist ein korrektesPufferverhalten, wenn für jedes Anfangsstück (Präfix) v von w gilt |v|{a,b} ≤ |v|e.

Die Konkatenation ist assoziativ und λ ist ein Einselement (neutrales Element), d.h. w ·λ =

w = λ · w. Strukturen mit einer assoziativen Operation mit 1 gibt es häufiger.

Definition 1.4. Ein Monoid ist ein Tripel (M, ·, 1M ), wobei · eine assoziative Operation aufder Menge M und 1M ∈ M neutrales Element ist (also: ∀m ∈ M : m · 1M = m = 1M ·m).

2

Beispiele 1.5. für Monoide(Σ∗, ·, λ) für |Σ| ≥ 2 nicht kommutativ: ab 6= ba

(B,∧, true) (N,+, 0)(B,∨, false) (Z,+, 0)

In Monoiden kann man natürlichzahlige Potenzen definieren: xn ist das Produkt von n x’en;formal:

x0 = 1; xn+1 = x · xn

Speziell für Σ∗ ist also wn die Konkatenation von n w’s und w0 = λ. Weiter ist z.B.(ab)3 = ababab und ab3 = abbb – Potenzieren geht als „Rechenart höherer Stufe“ also vor.

Es gelten in allen Monoiden die üblichen Rechenregeln für Potenzen:

x1 = x; xn+m = xn · xm; ) (xn)m = xnm

Weiter verhält sich die Länge wie ein Logarithmus:

|λ| = 0; |vw| = |v| + |w| ; |wn| = n · |w|

Auch der folgende Typ von Monoiden interessiert in dieser Vorlesung.

Definition 1.6. Für eine Menge M sei P(M) die Potenzmenge von M , d.h. die Menge allerTeilmengen von M . Die Operation · eines Monoids M wird auf P(M) (punktweise) erweitert:für K,L ⊆M ist K · L = {k · l | k ∈ K, l ∈ L}. 2

Proposition 1.7. Für ein Monoid M ist auch (P(M), ·, {1M }) ein Monoid.∀K ⊆M : K · ∅ = ∅ = ∅ ·K

Beispiele 1.8. • Für B: {true} ∨ {true, false} =

• In {a, b, c}∗: {ab, ac} · {c, cb} =

{a, ab}2 =

• In {0, 1, . . . , 9}∗: {1, . . . , 9} · {0, 5} ist die Menge aller zweistelligen, durch 5 teilbarenDezimalzahlen.

Das Monoid P(Σ∗) enthält gerade alle formalen Sprachen über Σ. Die n-te Potenz vonΣ ∈ P(Σ∗) besteht aus allen Produkten von n Elementen von Σ, also allen Wörtern derLänge n – genau wie wir Σn oben bereits definiert haben.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 5: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

1 WÖRTER UND MONOIDE 3

Wenn wir die Elemente von Σ als Aktionen eines Systems oder eines Programms auffassen,sind die Wörter Aktionsfolgen, d.h. Abläufe des Systems (vgl. Beispiel Kommunikation einesPufferspeichers). Die möglichen Abläufe des Systems (die von den Eingangsdaten oder z.B.vom Benutzer beeinflußt werden können und daher nicht von vornherein eindeutig festliegen)bilden eine Sprache L. Ln ist dann die n-fache Iteration des Programms (for-Schleife); u.a.für beliebige (endliche) Iteration (terminierende while-Schleife) führen wir ein:

L+ =⋃

n≥1

Ln

L∗ =⋃

n≥0

Ln = L+∪̇{λ}

Für L = Σ entsprechen L+ und L∗ unseren obigen Festlegungen.

Eine prominente Operation auf Wörtern ist die Spiegelung bzw. Revertierung; wichtig beiKellerautomaten – wieso?

Definition 1.9. Sei w = a1 · · · an ∈ Σ∗, n ≥ 0, ai ∈ Σ. Dann ist das Spiegelbild

wR = an . . . a1 (w reverse).

Für L ⊆ Σ∗ ist LR = {wR | w ∈ L}. 2

Neben der Multiplikation im Monoid der Sprachen haben wir auch eine Art Inversenbildung:

Definition 1.10. Seien L,K ⊆ Σ∗. Dann ist

• der Rechtsquotient LK−1(= L/K) := {u ∈ Σ∗ | ∃v ∈ K : uv ∈ L}

• der Linksquotient K−1L(= K\L) := {u ∈ Σ∗ | ∃v ∈ K : vu ∈ L} 2

K−1L besteht also aus den Endstücken von Wörtern aus L, die mit einem Wort aus Kbeginnen; z.B. {an | n ≥ 1}−1{anbn | n ≥ 0} =

Für ein Wort u schreiben wir oft u statt {u} (vgl. reguläre Ausdrücke). Demnach ist uL =

{uv | v ∈ L} und u−1L =

Gilt damit u−1(uL) = L = u(u−1L)?

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 6: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

1 WÖRTER UND MONOIDE 4

Übung: Sei PALΣ die Menge aller Palindrome über Σ, also Worte w mit w = wR. Fernersei PAL die Sprache PALΣ für ein beliebiges, aber festes Σ mit mindestens zwei Buchstaben.Zeigen Sie, dass PAL · PAL−1 = PAL · PAL, aber nicht PAL = PAL · PAL · PAL (wasgelten müsste, wenn PAL−1 ein richtiges Inverses wäre).

Noch einige Begriffe für Graphen G = (V,E) (gerichtet oder ungerichtet): Die Entfernungdist(v,w) von v ∈ V nach w ∈ V ist die Länge (= #Kanten) eines kürzesten Weges vonv nach w; ∞, wenn kein solcher Weg existiert. Der Durchmesser diam(G) ist die maximaleEntfernung zwischen zwei Ecken, der Radius rad(G) ist minv∈V maxw∈V dist(v,w); vgl. diePunkte einer Kreisfläche – wird das letzte Minimum bei v angenommen, ist v im Zentrumvon G.

In ungerichteten Graphen ist der Grad einer Ecke die Anzahl der inzidenten Kanten. G istzusammenhängend (zh), wenn für je zwei Ecken ein Weg von der einen zur anderen existiert.

Gibt es für jeden ungerichteten zh. (endlichen) Graphen mindestens eine Ecke im Zentrum?Höchstens eine? Ist diam(G) = 2 rad(G) oder welche Beziehung gilt sonst?

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 7: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

2 ENDLICHE AUTOMATEN 5

2 Endliche Automaten

(Chomsky-)Grammatiken erzeugen Sprachen. Um zu prüfen, ob ein Wort in einer Spracheliegt, sind abstrakte Maschinen nützlich – vor allem, wenn sie sich auch effizient implemen-tieren lassen.

Die einfachsten solchen Maschinen sind endliche Automaten. Sie spielen (in leicht abgewan-delter Form) auch eine wichtige Rolle im Software- und Systementwurf (Zustandsübergangs-systeme (UML), Transitionssysteme).

Definition 2.1. Ein (nichtdeterministischer) endlicher Automat (EA) über Σ ist ein TupelA = (Q,Σ, δ, q0, F ), wobei:

• Q —

• q0 ∈ Q —

• F

• δ

Ein (nichtdeterministischer) erweiterter endlicher Automat (EEA) ist genauso definiert,nur dass hier die Übergangsrelation ein endliches δ ⊆ Q × Σ∗ × Q ist. Der Automat heißtbuchstabierend, wenn δ ⊆ Q× Σ ×Q.

Graphische Darstellung :

Zustand q ∈ Q bzw. q (p,w, q) ∈ δw

p q

Startzustand q0 bzw. Endzustand q ∈ F bzw.

2

Beispiel 2.2. EEA – alle Wörter über a,b,c die das Teilwort aab enthalten

Ein endlicher Automat ist also ein Kanten-beschrifteter gerichteter Graph mit ausgezeich-neten Ecken; die Kanten / Pfeile werden als Tripel angegeben mit der Beschriftung in derMitte (s.o.). Es kann zwischen zwei Ecken mehrere („parallele“) Kanten mit verschiedenenBeschriftungen geben – meist malt man nur eine Kante und trennt die Beschriftungen durchein Komma. Erweiterte endliche Automaten entsprechen direkt rechtslinearen Grammatiken,deren Regeln ja die Form A → uB bzw. A → u mit u ∈ Σ∗ (!) und Nonterminalen A und B

haben; mit ihnen kann man Zustände sparen, s.o.

Definition 2.3. Zum erweiterten endlichen Automaten A sei δ∗ ⊆ Q × Σ∗ × Q die kleinsteRelation mit

i) ∀p ∈ Q: (p, λ, p) ∈ δ∗

ii) ∀p, q, q′ ∈ Q, v,w ∈ Σ∗ : (p, v, q′) ∈ δ∗, (q′, w, q) ∈ δ =⇒ (p, vw, q) ∈ δ∗

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 8: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

2 ENDLICHE AUTOMATEN 6

Also: (p, v, q) ∈ δ∗ =̂ A kann v von p nach q lesen.Die akzeptierte (erkannte) Sprache von A ist:

L(A) = {w ∈ Σ∗ | ∃q ∈ F mit (q0, w, q) ∈ δ∗}

= {w1 · · ·wn ∈ Σ∗ | n ≥ 0;∀i = 1, . . . , n : wi ∈ Σ∗ und

∃ (pi−1, wi, pi) ∈ δ mit p0 = q0 und pn ∈ F}

Erweiterte endliche Automaten A1, A2 heißen äquivalent, wenn L(A1) = L(A2). 2

Die Sprache L(A) ist die Menge der Beschriftungen w von Pfaden von q0 zu einem Endzu-stand; intuitive Notation: q0

w1−→ q1w2−→ . . .

wn−→ qn mit w = w1 . . . wn und qn ∈ F . Ist speziellq0 ∈ F , so kann man n = 0 wählen und erhält λ ∈ L(A). In Beispiel 2.2 gibt es . . . mit aabaabbeschriftete Pfade von q0 aus, von denen . . . in F enden. Nach 2.3 akzeptiert der Automataab, d.h. er „rät“ richtig – im Gegensatz zu real existierenden Maschinen, die im Zweifel allesfalsch machen; angelischer vs. dämonischer Nichtdeterminismus.

Bisweilen noch nichtdeterministischer: Menge I ⊆ Q von Startzuständen; gleiche Klasse dervon endlichen Automaten erkannten Sprachen.

ba

b

b

b

0 321

Abbildung 1

Beispiel 2.4. Für A aus Abb. 1 ist L(A) =

Dies ist gewissermaßen die Leistung von q0.Zustand q1 als Startzustand leistetZustand q3 als Startzustand leistet

Satz 2.5. Eine Sprache L ⊆ Σ∗ ist genau dann regulär (d.h. sie wird von einer rechtslinearenGrammatik erkannt), wenn L von einem endlichen Automaten akzeptiert wird.

Als erste Schritte zu einem „realistischeren“ Automatentyp zeigen wir, daß endliche Auto-maten ohne spontane Übergänge nicht weniger können als erweiterte endliche Automaten.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 9: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

2 ENDLICHE AUTOMATEN 7

Proposition 2.6. Zu jedem erweiterten endlichen Automaten existiert effektiv – was heißtdas?? – ein äquivalenter endlicher Automat.

Beweis. 2

Beispiel 2.7. (Fortsetzung von 2.2)

Satz 2.8. Zu jedem endlichen Automaten A existiert effektiv ein äquivalenter buchstabieren-der endlicher Automat A′.

Beweis. Wir müssen lediglich die λ–Kanten eliminieren.Wir setzen R(p) = {q ∈ Q | (p, λ, q) ∈ δ∗}. Diese Mengen lassen sich mit Floyd/Warshall inZeit . . . bestimmen. Dann sei Q′ = Q, q′0 = q0,

δ′ = {(p, a, q) ∈ Q× Σ ×Q | ∃q′ ∈ R(p) : (q′, a, q) ∈ δ} undF ′ = {p ∈ Q | R(p) ∩ F 6= ∅}.

λ aλa

aa

λ λ

2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 10: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

2 ENDLICHE AUTOMATEN 8

Satz 2.9. Es ist entscheidbar, ob für einen gegebenen endlichen Automaten A L(A) leer bzw.unendlich ist.

Beweis. O.E. A buchstabierend (Satz 2.8 ist effektiv!). Entfernen wir aus A alle Zustände,die nicht von q0 aus über Kanten erreichbar sind, so gilt für den resultierenden endlichen Au-tomaten A′: L(A′) = L(A) (warum?) und L(A′) 6= ∅, wenn A′ mindestens einen Endzustandhat (warum?).

Wie funktioniert das Entfernen? Dauer?

Entfernen wir jetzt noch alle Zustände, von denen aus kein Endzustand erreichbar ist (; A′′

falls o.E. . . . ), so ist L(A) = L(A′′) (warum?) und L(A′′) ist genau dann unendlich, wenn esin A′′ einen Kreis gibt (warum?).

Wie funktioniert das Entfernen? 2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 11: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

2 ENDLICHE AUTOMATEN 9

Deterministische Automaten

Realistische Maschinen/Programme raten nicht einfach richtig; wir geben jetzt eine reali-stische Automatenvariante, die man direkt in ein Programm übertragen kann.

Definition 2.10. Ein buchstabierender endlicher Automat heißt deterministisch (ein DEA),wenn δ eine partielle Funktion Q × Σ 99K Q ist, d.h. wenn ∀q ∈ Q, a ∈ Σ höchstens einFolgezustand q′ ∈ Q mit (q, a, q′) ∈ δ existiert. Ein DEA heißt vollständig, wenn δ eine (totaldefinierte) Funktion ist. 2

Charakteristisch: ∀p ∈ Q, w ∈ Σ∗ ∃≤1q : (p,w, q) ∈ δ∗

Ein deterministischer endlicher Automat läßt sich leicht in ein Programm zur Worterken-nung umwandeln; dies benötigt die Tabelle δ, den jeweils aktuellen Zustand, das gerade ge-lesene Zeichen und F , also konstanten Platzbedarf; d.h.. . . Jedes Zeichen wird in konstanterZeit verarbeitet, das Wort also in linearer Zeit gelesen (gemessen an der Wortlänge).

Satz 2.11 (Hauptsatz über endliche Automaten). Zu jeder regulären Sprache L gibt es effektiveinen vollständigen (und daher deterministischen) endlichen Automaten A mit L(A) = L.

Der Beweis besteht in der Potenzautomatenkonstruktion von Myhill ausgehend von einemEA A′ für L; Idee: A merkt sich in jedem seiner Zustände alle Zustände von A′, in die A′ beimLesen einer gegebenen Eingabe geraten kann. Die Zustandsmenge von A ist also im Prinzipdie Potenzmenge Q := P(Q′). Da wir natürlich einen kleinen Automaten suchen, wollen wiruns immer auf den von Startzustand erreichbaren Teil des Potenzautomaten beschränken.Da die Konstruktion aus „Einführung in die Theor. Inf.“ bekannt ist, behandeln wir nur einBeispiel.

Beispiel 2.12. Fortsetzung von Beispiel 2.7

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 12: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

2 ENDLICHE AUTOMATEN 10

Hierbei repräsentiert z.B. q03 die Menge {q0, q3}. Die leere Zustandsmenge ∅ dient oft alsFangzustand: sie hat nur einlaufende Kanten und auf jeden Fall eine Schlinge für jedes Zeichen.Sie wird oft benötigt, um den Automaten vollständig zu machen, ist aber in unserem Beispielnicht erreichbar.

Korollar 2.13. i) Reguläre Sprachen sind effektiv unter Komplement abgeschlossen (washeißt das?).

ii) Es ist entscheidbar, ob für einen gegebenen endlichen Automaten A über Σ L(A) = Σ∗

ist.

Beweis. i)

ii) Wende diese Konstruktion auf A an – aufwendig! – und entscheide mit Satz 2.9, ob derresultierende Automat ∅ akzeptiert. 2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 13: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

3 ANWENDUNG: DIOPHANTISCHE GLEICHUNGEN 11

3 Anwendung: Diophantische Gleichungen

Lit. z.B.: A. Boudet, H. Comon: Diophantine Equations, Presburger Arithmetic and FiniteAutomata. In CAAP ’96, Springer 1996, LNCS 1059, 30–43

Diophantische Gleichungen sind lineare Gleichungen mit (mehreren Unbekannten und)ganzzahligen Koeffizienten, die in den natürlichen Zahlen gelöst werden sollen. Es könnteeinen z.B. interessieren, ob es natürliche Zahlen x und y gibt, so dass 3x − 4y = 5. Wirkönnten für solche Paare z.B. x − 2y maximieren wollen oder allgemein ganzzahlige lineareOptimierung für natürlichzahlige Lösungen betreiben. Solche Probleme lassen sich mit endli-chen Automaten lösen!

Wir behandeln hier allgemeiner Formeln in der sogenannten Presburger Arithmetik; derVorteil dabei ist, dass wir so die gesuchten EAen leichter konstruieren können.

Die Presburger Arithmetik ist eine eingeschränkte Prädikatenlogik, die in offensichtlicherWeise über (N,+) (inkl. 0) interpretiert wird. Die Terme t der Presburger Arithmetik sind:

• 0,1 (Konstanten)

• x, y, . . . , x1, x2, . . . (stehen also für natürliche Zahlen)

• t1 + t2

Die Formeln ϕ der Presburger Arithmetik sind:

α) t1 = t2 β) ¬ ϕ γ) ϕ1 ∨ ϕ2 δ) ∃x ϕ

Damit können wir die üblichen Abkürzungen ϕ1 → ϕ2 für . . . . . . , ϕ1 ∧ϕ2 für . . . . . . , ∀x ϕfür . . . . . . und t1 6= t2 für ¬ (t1 = t2) verwenden sowie

• 4 für . . . etc.; nur Zahlen aus N

• 3t für . . . etc. ; nur Koeffizienten aus N

• t1 ≤ t2 für . . .

• t1 < t2 für . . .

Beispiel 3.1. ϕ ≡ ∃x3 x1 + 2 = x3 ∧ ∃x4 x2 + x4 = x3

freie Variablen von ϕ sind

Die Schreibweise ϕ(x1, . . . , xn) impliziert, dass alle freien Variablen von ϕ in {x1, . . . , xn}

sind. Wir schreiben dann k1, . . . , kn |= ϕ für k1, . . . , kn ∈ N, wenn ϕ[k1/x1, . . . , kn/xn

] wahrist. (Bem.: Die Variablen müssen nicht lückenlos durchnumeriert sein, im Prinzip betrachtenwir auch ϕ(x2, x4, x7), ϕ(x, y) etc.)

Im Beispiel gilt 5, 1 |= ϕ(x1, x2) wg. x3 = 7, x4 = 6. Gelten 6, 7 |= ϕ(x1, x2) und 8, 11 |=

ϕ(x1, x2)? . Es gilt auch 5, 1, 42 |= ϕ(x1, x2, x6) und 5, 1, 42 |= ϕ(x1, x2, x3) (!)

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 14: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

3 ANWENDUNG: DIOPHANTISCHE GLEICHUNGEN 12

Mit der Presburger Arithmetik erfassen wir die oben genannten Probleme, wie folgendeBeispiele zeigen:

Für ϕ ≡ 3x1 + x2 + 2 = 2x3 ist {(k1, k2, k3) ∈ N3 | k1, k2, k3 |= ϕ} die Menge der natürlich-zahligen Lösungen der diophantischen Gleichung 3x1 + x2 − 2x3 = −2; Zahlen/Koeffizientenaus Z können wir also auch behandeln. Wenn die Gleichungen eines Gleichungssystems denFormeln ϕ1, ϕ2 und ϕ3 entsprechen, so beschreibt man die Lösungen des Gleichungssystemsanalog unter Verwendung von ϕ1 ∧ ϕ2 ∧ ϕ3; so kann man z.B. auch die nichtnegativen S-Invarianten eines Petrinetzes beschreiben.

Um die ganzzahlige lineare Optimierungsaufgabe „maximiere x1+x2 mit x1−2x2+3x3 ≤ 4“zu lösen, muss man Werte für x1, x2 und x3 finden, die folgende Formel erfüllen:

Um nun allgemein die Lösungsmenge für ein ϕ(x1, . . . , xn) als Sprache eines EA darzustel-len, müssen wir n-Tupel natürlicher Zahlen als Wörter über einem Alphabet darstellen. AlsAlphabet verwenden wir

{0, 1}n =

0...0

0

,

0...0

1

, . . . ,

1...1

0

,

1...1

1

und benutzen folgende Codierung: (k1, . . . , kn) ∈ Nn entspricht w ∈ ({0, 1}n)∗, wenn es ein l

und für jedes ki, i = 1, . . . , n, eine Binärdarstellung kilki(l−1) . . . ki0 gibt mit

w =

k10...kn0

. . .

k1l...knl

Die Binärdarstellungen müssen also gleichlang sein und werden dazu ggf. mit führendenNullen aufgefüllt; in w stehen niederwertige Bits vorn.

Die Codierungen von 0 sind also λ, 0, 00, . . ., eine Codierung von (10, 7) ist . λ codiert auchalle Tupel von Nullen.

Ziel: Konstruktion eines EA A(ϕ) über {0, 1}n zu jeder Formel ϕ(x1, . . . , xn) mit

L(A(ϕ)) = {w ∈ ({0, 1}n)∗ | für (k1, . . . , kn) =̂w : k1, . . . , kn |= ϕ}

So ein Automat berechnet (bzw. beschreibt) also z.B. die Lösungen diophantischer Opti-mierungsaufgaben. Man beachte, dass bei Bedarf auch überflüssige xi auftreten können, diealso nicht (freie) Variablen von ϕ sind. Mit Hilfe der gesuchten Konstruktion und Satz 2.9können wir also entscheiden, ob es überhaupt Lösungen gibt.

Als Extremfall können wir geschlossene Formeln ϕ() betrachten. Hier hat der Automatallenfalls λ-Kanten, und es gilt |= ϕ gdw. L(A(ϕ)) 6= ∅ (d.h. = {λ}). Zur Erinnerung: hier isteine geschlossene Formel ϕ() gültig, wenn sie in der festen Interpretation in den natürlichenZahlen stimmt. Mit Satz 2.9 erhalten wir mit der gesuchten Konstruktion:

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 15: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

3 ANWENDUNG: DIOPHANTISCHE GLEICHUNGEN 13

Ergebnis: Die Gültigkeit von Formeln der Presburger Arithmetik ist entscheidbar.

Unsere Konstruktion ist nicht besonders effizient, aber leicht zu verstehen. Es gibt optimier-te Versionen, die konkurrenzfähig sind. Man beachte: Wenn wir die Presburger Arithmetikum ∗ für Multiplikation erweitern, so ist das analoge Problem unentscheidbar!

Konstruktion des gesuchten EA mit struktureller Ind.

α) Da t1 = t2 gdw. ∃x t1 = x ∧ x = t2, genügt es, Formeln der Form x = t zubetrachten. Da weiter z.B. x = t1 + t2 + t3 gdw. ∃ y x = t1 + y ∧ y = t2 + t3 für ein frischesy, können wir annehmen, dass t höchstens zwei Summanden hat. Wir behandeln beispielhaftdie möglichen Fälle.

i) ϕ ≡ x1 = 2; da wir auch überflüssige Variablen behandeln müssen, betrachten wir hierϕ(x1, x2):

A0

ii) ϕ(x1, x2, x3) ≡ x1 = x2

A1

iii) ϕ(x1, x2, x3) ≡ x2 = x1 + x3

A2

β) effektiver Abschluss der regulären Sprachen unter Komplement, d.h. wir könnenA(¬ϕ)

Beachte: L(A(ϕ)) = {w | w codiert Lösung von ϕ} undL(A(¬ϕ)) = {w | w codiert keine Lösung von ϕ} = L(A(ϕ)). Würde A(ϕ) zu jeder Lösungnur mindestens eine, nicht aber immer alle Codierungen akzeptieren, so würde L(A(ϕ)) auchCodierungen von Lösungen von ϕ enthalten.

γ) effektiver Abschluss der regulären Sprachen unter VereinigungUm dies wirklich auf ϕ1 ∨ ϕ2 anwenden zu können, müssen die Automaten zu ϕ1 und ϕ2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 16: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

3 ANWENDUNG: DIOPHANTISCHE GLEICHUNGEN 14

δ) ϕ(x1, . . . , xn−1) ≡ ∃xn ϕ′(x1, . . . , xn)

Im Prinzip müssen wir die Ziffern von xn in A(ϕ′) löschen, z.B. die Ziffern von x3 in A2

für ϕ1(x1, x2) ≡ ∃x3 x2 = x1 + x3, d.h. x1 ≤ x2:

A3

A3 kann man direkt als richtig erkennen. Ein Ablauf von A3 entspricht einem Ablauf von A2;dazu muss x3 ergänzt werden, was aufgrund der Konstruktion natürlich möglich ist. Akzeptiertalso A3 eine Darstellung von (k1, k2), so akzeptiert A2 diese Darstellung mit jeweils einemdritten Bit; diese erweiterte Darstellung erfüllt ϕ′, also erfüllt (k1, k2) ϕ. In anderen Worten,A3 akzeptiert nur korrekte Wörter.

Erfüllt (k1, k2) umgekehrt ϕ, so gibt es ein k3, so dass (k1, k2, k3) ϕ′ erfüllt. A2 akzeptiert

also eine Codierung von (k1, k2, k3) und A3 die entsprechend gekürzte Codierung von (k1, k2).

Das reicht aber nicht, denn

Um einzusehen, dass dies wirklich ein Problem ist, konstruieren wir etwas abgekürzt denAutomaten zu ϕ(x1) ≡ ∃x2 x1 ≤ x2 ∧ even(x2). Automat A4 zu ϕ2(x1, x2) ≡ even(x2) ≡

∃x3 x2 = 2x3:

A4

Automat A3 ×A4 zu ϕ1 ∧ ϕ2 (direkte Konstruktion):

A3 ×A4

Durch Ausblenden von x2 gewinnenwir nun den Automaten zu ϕ:

A5

Dieser Automat erkennt

Allgemein gilt: erkennt ein Automat eine Codierung eines Tupels, so auch alle längeren.Das hier aufgetretene Problem ist also das einzige; um es zu beheben, muss die Konstruktionzu δ) noch abgeschlossen werden durch (wobei 00 = λ):

Wenn

so

Dies beendet die Konstruktion zu Formel der Form δ), also die ganze Konstruktion.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 17: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 15

4 Minimierung endlicher Automaten

In unserem Beispiel 2.12 hat die Konstruktion nicht auf ein optimales Ergebnis geführt.

Die Minimierung endlicher Automaten ist das folgende Problem:

Problem: Finde zu einer regulären Sprache einen vollständigen deterministischen endlichenAutomaten mit möglichst wenigen Zuständen.

Kurzschreibweise: Für vollst. DEA in diesem Abschnitt statt δ∗(q, w) einfach q · w (oderqw). Es gilt dann:

∀q ∈ Q : q · λ = q und ∀q ∈ Q, v,w ∈ Σ∗ : (q · v) · w = q · (v · w).

Bemerkung: Das Monoid Σ∗ operiert auf Q, d.h. das Einselement von Σ∗ hat einen neutralenEffekt und es gilt eine Art Assoziativgesetz.

Auf diese Weise läßt sich allgemein definieren: Ein (endlicher) Automat für ein Monoid Mist (Q,M, ·, q0, F ), wobei Q eine (endliche) Menge ist, M mittels · auf Q operiert, q0 ∈ Q,F ⊆ Q.

Damit läßt sich allgemein für ein Monoid M definieren, welche L ⊆ M durch endlicheAutomaten erkennbar sind. Von Interesse in der theoretischen Informatik (zur Beschreibungnebenläufiger Systeme) sind z.B. die sogenanten freien partiell–kommutativen Monoide, derenElemente auch Mazurkiewicz–Traces genannt werden. 2

4.1 Der Minimalautomat und der Satz von Nerode

Definition 4.1. Der Index einer Äquivalenzrelation (was ist das?) ist die Anzahl der Äqui-valenzklassen. Eine Relation R auf Σ∗ heißt rechtsinvariant, falls ∀u, v,w ∈ Σ∗ : uRv =⇒

uwRvw. (Wenn man an u, v aus derselben Äquivalenzklasse dasselbe w anhängt, . . .

Für eine Sprache L ⊆ Σ∗ ist L(u) = u−1L = {v ∈ Σ∗ | uv ∈ L} die Leistung von u ∈ Σ∗ – dieMenge der Wörter, die man nach u lesen muss, um in L zu landen. Die Relation RL ⊆ Σ∗×Σ∗

ist definiert durch uRLv ⇐⇒ L(u) = L(v). (Wenn man an u, v dasselbe w anhängt, . . .Idee: Wörter zum selben Zustand haben die selbe Leistung. 2

Offenbar ist RL eine Äquivalenzrelation, die sogenannte Nerode-Äquivalenz, deren Klassenwir mit [u] bezeichnen wollen. Es gilt:

(⋆) Falls u ∈ L, so [u] ⊆ L.Ist nämlich v ∈ [u], so λ ∈ L(u) = L(v), also v ∈ L. (⋆) bedeutet, dass L Vereinigung ist vonÄquivalenzklassen von RL.

(⋆⋆) RL ist rechtsinvariant.Ist nämlich uRLv, so folgt:

L(uw) = {x ∈ Σ∗ | uwx ∈ L} = {x ∈ Σ∗ | wx ∈ L(u) = L(v)}

= {x ∈ Σ∗ | vwx ∈ L} = L(vw).

Auf Grundlage von RL definieren wir nun einen evtl. nicht-endlichen Automaten, den soge-nannten minimalen Automaten zu L; diese Bezeichnung werden wir in Satz 4.8 rechtfertigen.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 18: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 16

Definition 4.2. Zur Sprache L ⊆ Σ∗ definieren wir den minimalen Automaten AL von L

durch: QL = {[v] | v ∈ Σ∗} – evtl. unendlich!

qL0 = [λ]; FL = {[v] | v ∈ L};

δL([v], a) = [va] 2

Besonders die Definition von δL ist problematisch: wir benutzen den Vertreter v, um dasBild von δL zu bestimmen – könnte nicht ein anderer Vertreter u ∈ [v] zu einem anderenErgebnis führen? Dies ist nicht der Fall (man sagt, δL sei wohldefiniert) denn nach (⋆⋆) giltfür u ∈ [v] . . .

Die Definition von FL bedeutet übrigens, dass eine Äquivalenzklasse ein Endzustand ist,wenn zumindest ein Vertreter in L ist. Es wäre mathematisch kein Problem (aber etwasverwirrend), wenn v ∈ L und zugleich u 6∈ L für ein u ∈ [v]; dies ist aber glücklicherweisenicht der Fall wegen

Beispiel 4.3. L = a(ba)∗ + b = (ab)∗a+ b

Leistung Äquivalenzklasse Bemerkungen

λ

a

b

ab

ba

L(λ)=L

L(a)= (ba)∗

L(b)= {λ}

L(ab)= (ab)∗a

L(ba)= ∅

[λ] = {λ}

[a] = a(ba)∗

[b] = {b}

[ab] = (ab)+

[ba] = Rest

vb ∈ L =⇒ v = λ (nur λ hat Leistung b)vba ∈ L =⇒ v ∈ a(ba)∗

maximal in L: nur bva ∈ L =⇒ v ∈ (ab)∗, vb 6∈ L =⇒ v 6= λ

Bemerkung: Die L(v) charakterisieren die [v]!

Satz 4.4. Für jede Sprache L ⊆ Σ∗ ist L(AL) = L.

Beweis. Es ist w ∈ L(AL) ⇐⇒ δ∗L([λ], w] = [w] ∈ FL ⇐⇒ w ∈ L

Für das letzte ⇐⇒ gilt die umgekehrte Implikation nach Definition von FL, die Implikation. . . 2

Lemma 4.5. Ist A ein vollst. DEA zu L, dann ist der Index von RL nicht größer als |Q|.

Beweis. Wir ordnen jeder Klasse von RL die Zustände q0u zu mit u aus der Klasse. JederKlasse wird also mindestens ein Zustand zugeordnet (wg. Vollständigkeit), evtl. auch mehrere.Wir sind fertig, wenn wir zeigen können, dass jeder Zustand höchstens einer Klasse zugeordnetwird. Wir zeigen also: Wenn q0u = q0v, dann [u] = [v]; sei also q0u = q0v. (Zu zeigen ist. . .

Dann gilt für beliebiges w offenbar q0uw = q0vw, d.h. w ∈ L(u) ⇐⇒ uw ∈ L⇐⇒

⇐⇒ w ∈ L(v) und demnach uRLv.

Bem.: Gilt auch: wenn [u] = [v], dann q0u = q0v? 2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 19: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 17

Satz 4.6 (Nerode, Myhill). Für L ⊆ Σ∗ sind äquivalent:

i) L ist regulär.

ii) L ist Vereinigung von Äquivalenzklassen einer rechtsinvarianten Äquivalenzrelation R

von endlichem Index.

iii) RL hat endlichen Index. (Damit ist AL ein vollst. DEA.)

Beispiel 4.7. Bevor wir diesen Satz beweisen, wollen wir als Anwendung mit Hilfe der Nerode-Äquivalenz nachweisen, dass L = {wwR | w ∈ {a, b}∗} nicht regulär ist. Dazu betrachten wirdie Wörter anb, n ∈ N; zur Leistung eines solchen Wortes gehört offenbar ban aber kein bam

mit n 6= m. Daher sind alle anb nicht-äquivalent, RL hat demnach unendlichen Index, und L

ist nicht regulär.

Beweis. i) =⇒ ii) Nach unseren obigen Überlegungen und Lemma 4.5 erfüllt RL die ge-forderten Bedingungen.

ii) =⇒ iii) Sei uRv, w ∈ Σ∗. Dann ist uwRvw, also nach Voraussetzung uw ∈ L ⇐⇒

vw ∈ L. Also folgt w ∈ L(u) ⇐⇒ w ∈ L(v) und damit L(u) = L(v), d.h. uRLv. Rverfeinert also RL bzw. R ⊆ RL bzw. jede Äquivalenzklasse von RL ist Vereinigung vonÄquivalenzklassen von R. Daher Index(RL) ≤ Index(R) <∞.

iii) =⇒ i) Dies ergibt sich direkt aus Satz 4.4.

2

Bsp. für eine Relation R gemäß ii), die nicht RL ist: Wörter sind äquivalent, wenn sie zumselben Zustand führen, z.B. in Abb. 2.

Rechtfertigung der Bezeichnung minimaler Automat:

Satz 4.8. Sei L ⊆ Σ∗ und A ein vollständiger endlicher Automat mit L(A) = L. Dann gilt:|QL| ≤ |Q|. Bei Gleichheit sind A und AL isomorph, d.h. gleich bis auf die Bezeichnung derZustände.

Beweis. Der erste Satz folgt aus Lemma 4.5, da |QL| = Index(RL). Den zweiten Satz wollenwir hier nicht beweisen.

2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 20: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 18

4.2 Ein Verfahren zur Minimierung

Wir haben also AL zurecht den minimalen Automaten von L genannt. Um aus einem gege-benen vollständigen Automaten den minimalen Automaten von L(A) zu konstruieren, wollenwir in geeigneter Weise Zustände von A zusammenfassen. Für den Rest des Abschnittes seiA gegeben und o.E. initial zusammenhängend, d.h. daß

∀q ∈ Q : ∃u ∈ Σ∗ : q = q0u.

Definition 4.9. Die Leistung L(p) eines Zustandes p ∈ Q ist

L(p) = L((Q,Σ, δ, p, F )) (p als Startzustand).

Zwei Zustände p, q sind äquivalent, p ≡ q, falls L(p) = L(q). Wir schreiben „p 6≡ q wg. u“,wenn u in der Leistung von genau einem von p und q liegt, d.h.: pu ∈ F ⇐⇒ qu 6∈ F . 2

Bemerkung 4.10. i) p ≡ q =⇒ [p ∈ F ⇐⇒ λ ∈ L(p) = L(q) ⇐⇒ q ∈ F ]

ii) Ist p = q0u, so L(p) = L(u).

Die Idee für unsere Konstruktion ist, dass Zustände mit gleicher Leistung zusammengefasstwerden können; dass dies das richtige Vorgehen ist, zeigt folgendes Lemma.

Lemma 4.11. AL ist isomorph zu A mit

Q = {[q]≡ | q ∈ Q} , Σ = Σ, q0 = [q0]≡, F = {[p]≡ | p ∈ F} und

δ : Q× Σ −→ Q, ([q]≡, a) 7−→ [qa]≡

Beweis. Beachte: p ≡ q =⇒ L(pa) = a−1(L(p)) = a−1(L(q)) = L(qa) =⇒ pa ≡ qa, d.h. δ istwohldefiniert.

Ferner ist [p]≡ ∈ F ⇐⇒ p ∈ F (nach 4.10 i)).

f : QL −→ Q̄, [v] 7−→ [q0v]≡

ist eine Bijektion, denn:

i) wohldefiniert: uRLv ⇐⇒ L(u) = L(v) ⇐⇒ L(q0u) = L(q0v) (4.10 ii)) ⇐⇒ q0u ≡ q0v.

ii) injektiv: ⇐= in i).

iii) surjektiv: A initial zusammenhängend, also gilt:

∀q ∈ Q : ∃u ∈ Σ∗ : q = q0u, d.h. f([u]) = [q]≡.

Weiter ist f(qL0) = f([λ]) = [q0]≡ und

[v] ∈ FL ⇐⇒ v ∈ L⇐⇒ λ ∈ L(v) = L(q0v) ⇐⇒ q0v ∈ Fs.o.⇐⇒ [q0v]≡ ∈ F .

Schließlich: δ(f([v]), a) =Def. f und δ

[q0va]≡ = f([va]) (und δL([v], a) = [va]). 2

Der folgende Algorithmus bestimmt den minimalen Automaten, indem er sukzessive allePaare (p, q) mit p 6≡ q markiert.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 21: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 19

Algorithmus 4.12. Gegeben sei ein vollständiger endlicher Automat, der initial zusammen-hängt.

1) Markiere alle {p, q} mit p ∈ Q− F, q ∈ F .

2) Solange es ein unmarkiertes {p, q} gibt und ein a ∈ Σ, so daß {pa, qa} schon markiert ist,markiere auch ein solches {p, q}. (Ist pa = qa, so gilt Äquivalenz, d.h. {pa, qa} gilt alsunmarkiert.)

3) Am Ende sind alle nichtäquivalenten Zustände markiert.

Beweis. Korrektheit

i) Offenbar terminiert der Algorithmus 4.12.

ii) Alle Markierungen sind korrekt, Beweis durch Induktion über die „laufende Nummer“der Markierung: Wird {p, q} in Schritt 1) markiert, gilt p 6≡ q wg. λ. Wird {p, q} inSchritt 2) markiert, gibt es nach Induktion ein a ∈ Σ und ein Wort u, so daß pa 6≡ qa

wg. u. Damit ist p 6≡ q wg. au.

iii) Alle unmarkierten {p, q} sind äquivalent. Angenommen: {p, q} ist unmarkiert, aber nichtäquivalent, d.h. p 6≡ q wg. einem Wort u. Wähle {p, q} mit möglichst kurzem u. Wegen1) ist u 6= λ; also ist u = au′ mit a ∈ Σ und pa 6≡ qa wg. u′. Nach Wahl von {p, q} istaber {pa, qa} markiert. Widerspruch zu: 2) wurde beendet.

2

a

a

1

76

b

aa

2

4

a

a3

a5

b

b

bb

b

b

Abbildung 2

Beispiel 4.13. Minimierung eines endlichen Automaten

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 22: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 20

1 2 3 4 5 6

2 ×

3 × ×

4 × × ×

5 × × ×

6 × × × ×

7 × × × × ×

1 2 a1 3 a1 5 a

...2 7 a ×

...3 5 a ×

...6 7 a ; 27 ×

1 3 a × !

Äquivalenzklassen sind: {1, 6}, {2, 5}, {3, 7}, {4}.

Der minimale Automat ist daher:

Bei geeigneter Implementierung ergibt sich eine Laufzeit von O(n2), wobei Σ fest vorgegebenund n = |Q| ist. (Bem.: Q ist ein Graph, in der Größe müßte eigentlich auch die Kantenzahlberücksichtigt werden; aber die ist

Idee: Zu jedem Feld {p, q} gibt es eine Liste; ist {p, q} unmarkiert, {pa, qa} aber auch, sowird

Die Arbeit, die für ein {p, q} geleistet wird, ist also angeblich konstant; dazu genügt es, dassdie Arbeit für ein a ∈ Σ konstant ist. Wird aber {p, q} markiert, müssen wir die anhängendeListe abarbeiten, und die kann sehr lang sein.

??

4.3 Minimierungsverfahren von Hopcroft

Eine bessere Laufzeit von O(n log n) für festes Σ ergibt sich durch folgenden Algorithmus vonHopcroft :

Eine Partition von Q ist eine Menge {B0, . . . , Bk} von Blöcken mit⋃k

i=0Bi = Q undBi ∩Bj = ∅ für alle i 6= j, Bi 6= ∅ für i = 0, . . . , k. Sie heißt zulässig, wenn:

∀p, q ∈ Q : p ≡ q =⇒ ∃i : p, q ∈ Bi.

Für B ⊆ Q setze

δ−1(B, a) = {q ∈ Q | δ(q, a) ∈ B}

(gehe von B aus rückwärts über a–Kanten).

Die Idee des Algorithmus ist es, mit der Partition {F,Q− F} zu beginnen (wie bisher); dannwählt man einen Block B und zerlegt jeden Block B′ in B′∩δ−1(B, a) und B′−δ−1(B, a). Dieswird wiederholt, bis keine weitere Zerlegung mehr möglich ist. Man beachte, dass Zerlegenmit B und a dasselbe ergibt wie Zerlegen mit Q−B und a.

Eine Partition {B0, . . . , Bk} von Q heißt stabil bzgl. B ⊆ Q und a ∈ Σ, wenn für i = 0, . . . , k

gilt:

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 23: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 21

Bi ⊆ δ−1(B, a) oder Bi ∩ δ−1(B, a) = ∅.

(Also: Rückwärts gehen von B über a Kanten spaltet keinen Block). Die Partition heißtstabil, wenn sie stabil ist bzgl. aller (Bi, a), i = 0, . . . , k, a ∈ Σ.

Bemerkung: δ−1(B, a) macht Arbeit =⇒ klein halten.

Lemma 4.14. Ist eine Partition stabil und eine Verfeinerung von {F,Q− F}, so gilt:

p, q ∈ Bi =⇒ p ≡ q.

Beweis. Indirekt: Wähle p, q ∈ Bi, so daß p 6≡ q wg. u mit u minimal. Nach Voraussetzunggilt: u 6= λ, d.h. u = au′ mit a ∈ Σ und pa 6≡ qa wg. u′. Nach Wahl von p, q und u gibt es alsol 6= m mit pa ∈ Bl und qa ∈ Bm. Demnach ist die Partition (speziell Bi) nicht stabil bzgl.(Bl, a). Widerspruch. 2

Algorithmus 4.15 (Hopcroft).begin B0 := Q− F ; B1 = F ;

for all a ∈ Σ do

Liste(a) :=

{{0} falls

∣∣δ−1(B0, a)∣∣ ≤

∣∣δ−1(B1, a)∣∣

{1} sonst

od; \\ B ∈ Liste(a): bzgl. (B, a) muß gespalten werden, s.o.)k:=1 \\B0, . . . , Bk sind die Blöckerepeat l := k; wähle a ∈ Σ und i ∈ Liste(a);

lösche i aus Liste(a); △ := δ−1(Bi, a);for j := 0 to k mit (∅ 6= Bj ∩△ 6= Bj) do

l := l + 1; Bl = Bj ∩△; Bj := Bj −Bl;

forall b ∈ Σ doif j ∈ Liste(b) then Liste(b) := Liste(b) ∪ {l}

elsif∣∣δ−1(Bj , b)

∣∣ ≤∣∣δ−1(Bl, b)

∣∣then Liste(b) := Liste(b) ∪ {j}

else Liste(b) := Liste(b) ∪ {l}

fi;od;

od;k := l;

until alle Listen leer;return {B0, . . . , Bk}

end

Korrektheit. Höchstens (n− 2)–mal spalten, danach alle Listen löschen =⇒ Terminierung.

Wir zeigen als nächstes, daß die Partitionen im Verlauf des Algorithmus stets zulässig sind.Zunächst ist {B0, B1} zulässig. Annahme: Bj wird in B′

j und B′l gespalten und es gibt p, q ∈ Bj

mit p ≡ q, p ∈ B′j und q ∈ B′

l. Dann ist pa /∈ Bi, qa ∈ Bi. Da pa ≡ qa (wegen p ≡ q), ist diesein Widerspruch zur Zulässigkeit der Partition vor der Aufspaltung von Bj.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 24: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 22

Da alle Partitionen Verfeinerungen von {Q− F,F} sind, müssen wir wegen Lemma 4.14 nurnoch zeigen, daß die Partition am Ende stabil ist. Während der Berechnung ist die Partitionevtl. nicht stabil bzgl. (B, a); dies ist kein Problem, wenn B ∈ Liste(a), da wir durch Spaltenbzgl. (B, a) Stabilität erzwingen werden. Die Partition ist aber auch evtl. nicht stabil bzgl.(B, a), obwohl B /∈ Liste(a); z.B. ist am Anfang nur F oder Q − F in Liste(a), da Spaltenbzgl. F bzw. Q − F denselben Effekt hat. Allgemeiner (s.o.): Ist die Partition stabil bzgl.(B, a) und wir spalten B in B′ und B′′, so hat Spalten bzgl. (B′, a) bzw. (B′′, a) denselbenEffekt, denn:

Ist Bi ∩ δ−1(B, a) = ∅, so gilt dies analog für B′ und B′′. Ist Bi ⊆ δ−1(B, a), so giltBi ∩ δ

−1(B′, a) = Bi − δ−1(B′′, a).

Wir speichern also nur das günstigere von B′ und B′′ ab — der Aufwand in der repeat–Schleife hängt wesentlich von δ−1(Bi, a) ab.

Wir zeigen daher die Schleifeninvariante:

Vor/Nach jedem Durchgang der repeat–Schleife gilt für m /∈ Liste(c), m ≤ k: es gibt{m1, . . . ,mn} =: L ⊆ Liste(c), n ≥ 0, so daß die aktuelle Partition stabil ist bzgl. (Bm ∪

Bm1∪ · · · ∪Bmn

, c).

Zu Beginn ist dies stets erfüllt wegen Stabilität bzgl. B0 ∪ B1 = Q und allen c. Am Endesind dann alle Listen leer, es gilt also Stabilität bzgl. aller (Bm, c).

Sei also m /∈ Liste(c) am Ende eines Schleifendurchlaufs:

I) m ∈ Liste(c) zu Beginn des Durchlaufs. Dann ist m = i und a = c. Durch das Aufspaltenist die Partition stabil bzgl. (Bi, a), also L = ∅. Ausnahme: Bi selbst wird in B′

i undB′

l gespalten und Stabilität gilt für Balt

i ; in diesem Fall ist am Ende (i /∈ Liste(c), also)l ∈ Liste(c); wähle L = {l}, da Balt

i = B′i ∪B

′l.

II) Andernfalls gibt es L gemäß Behauptung am Beginn des Durchlaufs, die Partition iststabil bzgl. B := Bm ∪ Bm1

∪ · · · ∪ Bmnund c zu Beginn und bzgl. B und c auch am

Ende des Durchlaufs:

a) i /∈ L ∨ a 6= c. Da nur Bi aus Liste(a) entfernt wird, bleibt in diesem Fall jedes Bmr

auf Liste(c).

Wird ein Balt

mrgespalten in B′

mrund B′

l, so sind am Ende mr, l ∈ Liste(c) (auch füri = mr), und wir fügen l zu L hinzu. Wird Balt

m selbst gespalten in B′m und B′

l, so istam Ende (m /∈ Liste(c), also) l ∈ Liste(c), und wir fügen l zu L hinzu. Am Ende istdie Partition also stabil bzgl. (B, c) mit B = Bm ∪

⋃r∈Lneu Br (wobei hier die neuen

Blöcke gemeint sind).

b) i ∈ L ∧ a = c, o.E. i = m1 6= m (m /∈ Liste(a)). Spalten von Bmr, mr 6= m1,

und von Bm wird wie in IIa) behandelt und m1 aus L entfernt (am Ende evtl.m1 /∈ Liste(a)). Zum Schluß ist die Partition stabil bzgl. (Balt

m1, a) und (B, a) mit

B = Bm∪Balt

m1∪

⋃r∈Lneu Br, also auch bzgl. (Bm∪

⋃r∈Lneu

Br, a) (wobei hier wiederdie neuen Blöcke gemeint sind):

2

Beispiel 4.16. (Forts.) Hopcroft-Algorithmus:

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 25: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 23

i� Bi δ−1(Bi, a) δ−1(Bi, b)

0 123567 13467 1256

1 4 25 347

Liste(a) = {1}

Liste(b) = {1}

k = 1: Wähle 1 ∈ Liste(a). δ−1(B1, a) = {2, 5}

j = 0:

i� Bi δ−1(Bi, a) δ−1(Bi, b)

0 1367 146 25

1 4 25 347

2 25 37 16

Liste(a) = {2}

Liste(b) = {0, 1}

j = 1: B1 ∩ δ−1(B1, a) = ∅

k = 2: Wähle 0 ∈ Liste(b). δ−1(B0, b) = {2, 5} stabil =⇒ Liste(a) = {2} , Liste(b) = {1}

k = 2: Wähle 1 ∈ Liste(b). δ−1(B1, b) = {3, 4, 7}

j = 0:

i� Bi δ−1(Bi, a) δ−1(Bi, b)

0 16 4 25

1 4 25 347

2 25 37 16

3 37 16 ∅

Liste(a) = {0, 2}

Liste(b) = {3}

Stabilität =⇒ Listen löschen

Weitere Details finden sich in: Norbert Blum: Theoretische Informatik, Kapitel 6.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 26: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 24

4.4 Gleicheit regulärer Sprachen und Größe minimaler Automaten

In vielen Fällen führt die Minimierung auf ein gutes Ergebnis. Es gibt aber Fälle (für jedesn), in dem zu einem EA A mit n Zuständen jeder vollständige DEA mindestens 2n Zuständehat, d.h. jedes Deterministisch-Machen kann auf ein exponentiell großes Ergebnis führen undkostet auch exponentielle Zeit.

Wir wollen hier ein Familie von Automaten behandeln, die auf 2n−1 Zustände führen, wojeder DEA also größenordnungsmäßig exponentiell ist im Vergleich zu einem guten EA.

Wir haben bereits einen EA mit n + 1 ≥ 2 Zuständen kennengelernt, der die SpracheL = {w ∈ {0, 1}∗ | |w| ≥ n und das n-letzte Zeichen von w ist 0} akzeptiert. Angenommen,der DEA A hat < 2n Zustände und akzeptiert L.

Zu A gibt es zwei Wörter v,w ∈ {0, 1}n mit q0v = q0w =: q. Sei i eine Position, in dersich v und w unterscheiden, d.h. o.E. v = v′0v′′ und w = w′1w′′ mit |v′′| = |w′′| = n − i,i ≥ 1. Sei nun u ∈ {0, 1}i−1. Dann ist 0 das n-letzte Zeichen von vu, aber nicht von wu, alsovu ∈ L ∧ wu 6∈ L.

Andererseits ist q0vu = qu = q0wu, d.h. vu und wu sind beide in L oder beide nicht in L;Widerspruch.

Betrachten Sie den Potenzautomaten für den EA zu L in den Fällen n = 2 und n = 3;wieviele Zustände haben diese? Wie kann man die Zustände interpretieren?

Satz 4.17. Es ist entscheidbar, ob für zwei gegebene endliche Automaten A1, A2 mit demsel-ben Alphabet Σ gilt: L(A1) ⊆ L(A2), bzw. A1 und A2 sind äquivalent.

Beweis. Sind A1, A2 gegeben, so können wir nach unseren bisherigen Ergebnissen einen endli-chen Automaten A3 konstruieren, mit L(A3) = L(A1)∩ (Σ∗−L(A2)). Es ist L(A3) = ∅ genaudann, wenn L(A1) ⊆ L(A2); mit Satz 2.9 ist dies entscheidbar und damit auch L(A1) = L(A2)

entscheidbar. 2

Wie aufwendig ist dies Entscheidungsverfahren? Um einen EA für Σ∗ − L(A2) zu konstru-ieren, machen wir zunächst A2 deterministisch und komplementieren dann die Endzustände.Den so erhaltenen DEA können wir noch minimieren, aber das Resultat kann immer nochexponentiell in der Größe des gegebenen EA A2 sein. Dass wir wohl nicht hoffen können, aufbessere als exponentielle Laufzeit zu kommen, zeigt der folgende Satz:

Satz 4.18. Das Problem IneqEA, die Inäquivalenz buchstabierender endlicher Automaten zuentscheiden, ist NP-hart; dies gilt dann erst recht für allgemeine EA.

Beweis. Was heißt NP-hart?

Ein Entscheidungsproblem D besteht aus einer Menge von Fällen (instances) instD (hier:Paare von buchstabierenden EAen) und einer Funktion D : instD → {T, F}; für einen Fall Xgilt D(X) gdw. die Antwort auf die Frage „Gilt D für X?“ ja ist. Gesucht ist ein Verfahren,dass bei Eingabe von X ∈ instD gerade D(X) ausgibt.

IneqEA ist NP-hart, wenn

Gegeben sei ein Fall ϕ = K1∧. . .∧Km von 3-SAT (was ist das?) mit Variablen {x1, . . . , xn}.Belegungen dieser Variablen können als w ∈ {0, 1}n beschrieben werden. Wir betrachten nundie Sprache L1 aller solcher w, die ϕ nicht erfüllen.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 27: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 25

Sei z.B. K1 = x1 ∨ ¬x3 ∨ x4; dann erfüllt w = w1w2w3w4 diese Klausel, wenn w1 = 1 oderw3 = 0 oder w4 = 1. Die w, die K1 nicht erfüllen, können wir also mit r1 = 0(0 + 1)10 oderdurch den azyklischen EA

beschreiben. Im allgemeinen ist der Ausdruck ri zu Ki definiert durch ri = ri1 . . . rin, wobeirij 0 bzw. 1 ist, wenn xj bzw. ¬xj in Ki auftritt, und (0 + 1) sonst. Damit ist L1 = r1 +

. . . rm und dieser Ausdruck bzw. ein zugehöriger buchstabierender Automat A1 lassen sichin polynomieller Zeit bestimmen, genauso wie (0 + 1)n und ein zugehöriger deterministischerAutomat A2.

Nun gilt L(A1) 6= L(A2) gdw. ϕ erfüllbar ist. Also lässt sich 3-SAT in polynomieller Zeitauf unser Problem IneqEA reduzieren, und wir sind fertig. 2

Übung: Dieser Beweis lässt sich leicht so modifizieren, dass er zeigt: „L(A1) 6= Σ∗ “ ist NP-hart – wie? (Hinweis: Durch welche w unterscheiden sich L(A2) und Σ∗? Sind diese relevantfür unser Problem?)

Das Problem in Korollar 2.13 ii) ist also schwierig, während das so ähnliche Leerheits-Problem in Satz 2.9 in kubischer Zeit gelöst werden kann.

Wir wollen noch eine Methode behandeln, mit der man die Frage angehen kann, ob L(A1) ⊆

L(A2). Diese Methode ist vor allem auch für Transitionssysteme geeignet; ein Transitionssy-stem entspricht weitgehend einem endlichen Automaten, es kann aber auch unendlich sein;dann sind die Verfahren aus obigem Beweis natürlich nicht anwendbar. Außerdem hat es nurEndzustände. (Deswegen muß man einfach kein F angeben.)

Sind Transitionssysteme systematisch gegeben, kann man evtl. auch im unendlichen Falleine Simulation (s.u.) finden und damit die Sprachinklusion nachweisen. Das läßt sich sointerpretieren, daß System A1 nur Verhalten zeigt, daß auch bei A2 erlaubt ist, so daß wir A1

als Implementierung der Spezifikation A2 ansehen können.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 28: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 26

Definition 4.19. Eine Simulation für endliche Automaten A1 und A2 mit demselben Alpha-bet Σ ist eine Relation S ⊆ Q1 ×Q2 mit folgenden Eigenschaften:

i) (q01, q02) ∈ S

ii) Ist (q1, q2) ∈ S und (q1, α, p1) ∈ δ1 (also α ∈ Σ∪{λ}), so gibt es p2 ∈ Q2 mit (q2, α, p2) ∈

δ∗2(!) und (p1, p2) ∈ S.

iii) Ist (q1, q2) ∈ S und q1 ∈ F1, so auch q2 ∈ F2.

2

Satz 4.20. Ist S eine Simulation für endliche Automaten A1 und A2, so gilt L(A1) ⊆ L(A2).

Beweis. Ist w ∈ L(A1), so gibt es (q01, α1, q11), (q11, α2, q21), . . . , (qm−1 1, αm, qm1) ∈ δ1( mitαi ∈ Σ∪{λ}, w = α1 · · ·αm und qm1 ∈ F1. Nach Definition 4.19 i) ist (q01, q02) ∈ S; also gibtes mit wiederholter Anwendung von ii) (q02, α1, q12), (q12, α2, q22), . . . , (qm−1 2, αm, qm2) ∈ δ∗2– also (q02, w, qm2) ∈ δ∗2 – mit (qm1, qm2) ∈ S; nach iii) ist also auch qm2 ein Endzustand, unddamit w ∈ L(A2). 2

b

a1

a

c

2

4

A

3

5

1 b

1

a

c

23

4

A

5

2

Abbildung 3

Abbildung 3 zeigt zwei sprachäquivalente Automaten; eine Simulation für endliche Auto-maten A1 und A2 ist S = {(1, 1), 2, 23), (3, 23), (4, 4), (5, 5)}. Für A2 und A1 gibt es aber keineSimulation, denn 23 hat eine b- und eine c-Kante, für einen simulierenden Zustand müßte dasauch gelten – aber einen solchen Zustand hat A1 nicht.

Die Methode ist also korrekt, aber nicht vollständig. Das wesentliche Problem dabei ist derNichtdeterminismus. Weiter beschränken wir A1 auf den Fall, daß von jedem Zustand ein Wegzu einem Endzustand führt; das ist keine wesentliche Einschränkung, da andere Zustände fürdie Sprache von A1 irrelevant sind.

Satz 4.21. Sind A1 und A2 endliche Automaten mit demselben Alphabet Σ; in A1 gebe esvon jedem Zustand einen Weg zu einem Endzustand, und A2 sei deterministisch. Ist L(A1) ⊆

L(A2), so gibt es eine Simulation S für A1 und A2.

Beweis. Wir setzen S = {(q1, q2) | ∃w ∈ Σ∗ : (q01, w, q1) ∈ δ∗1 ∧ (q02, w, q2) ∈ δ∗2}. Beachte,daß q2 durch w eindeutig bestimmt ist, da A2 deterministisch ist.

Für den Fall w = λ ergibt sich (q01, q02) ∈ S.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 29: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

4 MINIMIERUNG ENDLICHER AUTOMATEN 27

Ist (q1, q2) ∈ S und q1 ∈ F1, so ist w ∈ L(A1), also auch w ∈ L(A2), und wegen derEindeutigkeit von q2 muß q2 ∈ F2 sein.

Sei nun (q1, q2) ∈ S wegen w und (q1, α, p1) ∈ δ1; nach Voraussetzung gibt es v mit(p1, v, p) ∈ δ∗1 und p ∈ F1, d.h. wαv ∈ L(A1). Da nun auch wαv ∈ L(A2), gibt es einenwαv-beschrifteten Weg von q02 zu einem Endzustand, der wegen der Eindeutigkeit über q2und ein p2 führen muß mit (q2, α, p2) ∈ δ∗2 . (Entweder ist α ∈ Σ und (q2, α, p2) ∈ δ2 oderα = λ und q2 = p2.) Jetzt ist (q01, wα, p1) ∈ δ∗1 ∧ (q02, wα, p2) ∈ δ∗2 , also (p1, p2) ∈ S. 2

Bemerkung: Eine Bisimulation ist eine Relation S, die „in beide Richtungen“ eine Simu-lation ist, d.h. S und S−1 sind Simulationen; wird gern bei Transitionssystemen angewandt(z.B. in Zusammenhang mit der Prozessalgebra CCS). A1 und A2 sind also nicht bisimular;sie fällen die Entscheidung zwischen b und c während a bzw. nach a.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 30: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

5 PUMPING–LEMMA 28

5 Pumping–Lemma für reguläre Sprachen oder:

Das uvw–Theorem

Um zu zeigen, daß eine Sprache regulär ist, muß man lediglich einen entsprechenden EA (odereine Grammatik) angeben. Wie aber zeigt man, daß eine Sprache nicht regulär ist?

Sie kennen das folgende wichtige Hilfsmittel und seine klassische Anwendung:

Satz 5.1. Sei L regulär. Dann existiert ein n > 0, so daß es für alle z ∈ L mit |z| ≥ n eineZerlegung z = uvw gibt, für die gilt:

|uv| ≤ n, |v| ≥ 1 und ∀i ≥ 0 : uviw ∈ L

Beweis. Sei A ein buchstabierender endlicher Automat mit L = L(A). Wähle n = |Q|. Seiz = a1 · · · am ∈ L; m ≥ n, ai ∈ Σ. Dann in A: (q0, a1, q1), (q1, a2, q2), . . . , (qm−1, am, qm) ∈ δ

und qm ∈ F . Nach Wahl von n tritt ein Zustand in der Folge q0, . . . , qm mehrfach auf, undzwar bereits in q0, . . . , qn; d.h. ∃0 ≤ j < k ≤ n mit qj = qk.

Wir setzen u = a1 · · · aj , v = aj+1 . . . ak, w = ak+1 . . . am. Dann gilt |uv| = k ≤ n; |v| = k −

j ≥ 1. Wir können von q0 aus u lesen und qj erreichen, dann beliebig oft v und qj = qk erreichen(auch 0–mal!), schließlich w und einen Endzustand erreichen; also gilt: ∀i ≥ 0 : uviw ∈ L. 2

Der Satz gibt nur eine Folgerung, aber keine Charakterisierung für reguläre Sprachen an.

Anwendung : Zeigen, daß L die Folgerung verletzt und daher nicht regulär sein kann.

Beispiel 5.2. Das klassische Beispiel: L = {bmcm | m ≥ 0} ist nicht regulär.

Beweis. Annahme: L ist regulär. Dann gibt es ein n wie in 5.1. (Wir kennen n nicht, eventuellist n sehr groß, abhängig von n dürfen wir jetzt aber ein beliebiges z ∈ L wählen.)

Sei z = bncn; dann gibt es uvw wie in 5.1. (Wir kennen uvw nicht, wir müssen in jedemFall zum Widerspruch kommen.)

Da |uv| ≤ n gilt uv = bj , j ≤ n, ferner ist v = bk, k ≥ 1. Für i = 0 ergibt 5.1: bj−kbn−jcn =

bn−kcn ∈ L mit n− k 6= n. Widerspruch! 2

Leider gibt es auch Sprachen, die die Folgerung erfüllen und trotzdem nicht regulär sind; füreine solche Sprache kann man also nicht mit dem uvw-Theorem zeigen, dass sie nicht regulärist.

Beispiele 5.3.

L1 ={akblcm | k = 0 ∨ l = m

}

L2 = {(ab)m(cd)m | m ≥ 0} ∪ (ab)∗(cd)∗

L1 erfüllt obige Folgerung für n = 1: Sei akblcm ∈ L1 mit mindestens einem Zeichen. Wirbetrachten die folgenden Fälle:

i) Für k > 0 wähle uv = a.

ii) Für k = 0 ∧ l > 0 wähle uv = b.

iii) Für k = 0 ∧ l = 0 ∧m > 0 wähle uv = c.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 31: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

5 PUMPING–LEMMA 29

Intuitiv ist L1 aber nicht regulär, da man zum Erkennen offenbar zählen muss.

Für L2 wähle n gemäß 5.1 für die reguläre Sprache (ab)∗(cd)∗. Dann erfüllt L2 die Folgerungvon 5.1 für dieses n: Ist z aus der zweiten Teilmenge, ist dies klar nach Wahl von n; andernfallsführt Pumpen des ersten Buchstabens in die zweite Teilmenge.

Hier ist nicht mehr so offenbar, warum L2 nicht regulär ist. Zeigen Sie dies mit Hilfe vonSatz 4.6!

Betrachten wir noch einmal die Situation: kleine DEAen sind ein sehr effizientes Mittel zurBeschreibung von Sprachen, aber nicht immer anwendbar.

Der Praktiker sucht also (je nach Naturell) lange vergeblich nach einem EA, obwohl eskeinen gibt, oder bricht die Suche schnell ab, obwohl es einen gibt.

Der Theoretiker möchte hier Klarheit schaffen: Das uvw-Theorem kann einem die Sicherheitgeben, dass eine Suche sinnlos ist. Die Einsicht, die zu seinem Beweis führt, ergibt auch eineHeuristik für den Praktiker: EAen können nicht zählen.

Allerdings versuchen wir jetzt, parallel einen EA zu finden und das uvw-Theorem anzuwen-den. Wenn eine Bemühung erfolgreich ist, haben wir Klarheit; wenn nicht, kann es an unsererDummheit liegen oder daran, dass beide Vorgehen scheitern müssen.

Der Theoretiker möchte wieder Klarheit schaffen: Kann letzterer Fall eintreten? (Ja, s. 5.3;es gibt in unserer Methode also eine inhaltliche Lücke.) Wenn ja, können wir unser Werkzeuguvw-Theorem schärfen?

Letzteres gelingt in der Tat, wenn wir z.B. L1 betrachten. Wir würden gern abncn verwen-den, dabei das a ignorieren und uns auf bncn konzentrieren. Dazu wollen wir bncn in abncn

markieren:

Ein Wort mit Markierungen ist ein Wort z = a1 · · · am zusammen mit einer Menge P ⊆

{1, . . . ,m}. Wir sagen, dass die Buchstaben ai, i ∈ P , in z markiert sind; um die Markierungenanzugeben, unterstreichen wir oft die entsprechenden Buchstaben. In abcba sind also das erstea, das zweite b und das c markiert, das Wort hat 3 Markierungen.

Beachten Sie die starke Analogie des folgenden Satz, Beweis und Beispiel zum Obigen.

Satz 5.4 (Ogdens Lemma). Sei L regulär. Dann existiert ein n > 0, so daß es für alle z ∈ L

mit m ≥ n Markierungen (also auch |z| ≥ n) eine Zerlegung z = uvw gibt, für die gilt:

• uv hat ≤ n Markierungen und u ist leer oder endet mit einer Markierung;

• v endet mit einer Markierung, d.h. es hat mindestens eine und |v| ≥ 1;

• ∀i ≥ 0 : uviw ∈ L

Beweis. Sei A ein buchstabierender endlicher Automat mit L = L(A). Wähle n = |Q|. Seiz = a1 · · · al ∈ L, ai ∈ Σ,mit m ≥ n Markierungen. Wir lesen das Wort in A stückweise, wobeidie Stücke jeweils mit dem nächsten markierten Buchstaben enden: (q0, z1, q1), (q1, z2, q2), . . . ,

(qm−1, zm, qm), (qm, zm+1, qm+1) ∈ δ∗ und qm+1 ∈ F , wobei in jedem zi ∈ Σ∗ mit i ≤ m genauder letzte Buchstabe markiert ist und z = z1 · · · zm+1. Nach Wahl von n tritt ein Zustand inder Folge q0, . . . , qm mehrfach auf, und zwar bereits in q0, . . . , qn; d.h. ∃0 ≤ j < k ≤ n mitqj = qk.

Wir setzen u = z1 · · · zj, v = zj+1 . . . zk, w = zk+1 . . . zm+1. Dann enden u und v (ggf.) miteinem markierten Buchstaben, uv hat k ≤ n und v k − j ≥ 1 Markierungen. Wir können

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 32: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

5 PUMPING–LEMMA 30

von q0 aus u lesen und qj erreichen, dann beliebig oft v und qj = qk erreichen (auch 0–mal!),schließlich w und einen Endzustand erreichen; also gilt: ∀i ≥ 0 : uviw ∈ L. 2

Der Satz gibt wieder nur eine Folgerung, aber keine Charakterisierung für reguläre Sprachenan.

Anwendung : Zeigen, daß L die Folgerung verletzt und daher nicht regulär sein kann.

Wir betrachten hier ein Beispiel, dass sich auch mit dem uvw-Theorem behandeln läßt, beidem Ogdens Lemma aber übersichtlicher ist.

Beispiel 5.5. L = {((ab)m(ac)m | m ≥ 0} ist nicht regulär.

Beweis. Annahme: L ist regulär. Dann gibt es ein n gemäß Ogdens Lemma. (Wir kennen n

nicht, eventuell ist n sehr groß, abhängig von n dürfen wir jetzt aber ein beliebiges z ∈ L

wählen und markieren.)

Sei z = (ab)n(ac)n; dann gibt es uvw wie in 5.4. (Wir kennen uvw nicht, wir müssen injedem Fall zum Widerspruch kommen.)

Da uv ≤ n Markierungen hat und mit einer endet, gilt uv = (ab)j , j ≤ n; da ferner u miteiner Markierung endet und v k ≥ 1 Markierungen hat, ist v = (ab)k. Für i = 0 ergibt 5.4:(ab)j−k(ab)n−j(ac)n = (ab)n−k(ac)n ∈ L mit n− k 6= n. Widerspruch! 2

Zeigen Sie mit Ogdens Lemma, dass L1 nicht regulär ist in Analogie zum obigen klassischenBeispiel mit der Idee von oben.

Das Optimum wäre natürlich ein Kriterium, dass von jeder nicht-regulären Sprache verletztwird; dann gäbe es keine Lücke. Wir haben aber leider nur die Lücke verkleinert.

Bemerkung: Reguläre Sprachen sind so weitgehend untersucht, dass Ogdens Lemma hiertatsächlich keine große Rolle spielt; vgl. Kapitel 8. Es gibt aber auch ein Ogdens Lemmafür kontextfreie Sprachen, die analoge Verschärfung des uvwxy-Theorems. Dieses Lemma istwesentlich nützlicher.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 33: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

6 MEALY-AUTOMATEN 31

6 Mealy-Automaten

Endliche Automaten lesen und untersuchen Zeichenfolgen. Eine andere Sichtweise ist, dasssie Zeichenfolgen erzeugen, wobei die Zeichen als Aktionen oder Signale verstanden werdenkönnen; in Endzuständen kann der Automat terminieren, muss aber nicht unbedingt. Werdendie Zeichen als Aktionen gesehen, lässt man die Endzustände oft weg und spricht von Transiti-onssystemen, die auch unendlich sein dürfen; ein solches System kommt zum Stillstand, wennes einen Zustand ohne ausgehende Kanten erreicht, den man oft als Verklemmung versteht.

Mealy-Automaten kombinieren beide Sichtweisen: Deterministisch lesen sie Eingabezeichenund beantworten sie jeweils mit einem Ausgabezeichen. Welche Eingaben kommen, wird vonder Umgebung bestimmt; der Automat kümmert sich daher nicht um Akzeptieren oder Ter-minierung und hat keine Endzustände.

Mealy-Automaten eignen sich u.a. zur Modellierung von Schaltkreisen; da Schaltkreise imAllgemeinen mehrere Eingaben und Ausgaben haben, ist hier ein Eingabezeichen ein Tupel,das für jedes Eingabesignal einen Wert festlegt (1 oder 0, + oder −); Ausgabezeichen werdenggf. analog behandelt.

Der folgende Mealy-Automat führt eine serielle (auch: sequentielle) Addition durch. DieEingabe besteht aus zwei Binärzahlen, wobei jeweils die beiden Ziffern einer Stelligkeit vonrechts nach links eingegeben werden und die Ziffer derselben Stelligkeit ausgegeben wird (vgl.Kapitel 3). Der Automat muss sich im Zustand merken, ob ein Übertrag aufgelaufen ist.

11 / 0

00 / 1

0 1 00 / 001 / 110 / 1

01 / 010 / 011 / 1

Abbildung 4

Definition 6.1. Ein Mealy-Automat (MlA) über dem Eingabealphabet Σ und dem Ausgabe-alphabet ∆ ist ein Tupel A = (Q,Σ,∆, δ, γ, q0), wobei:

• Q —

• q0 ∈ Q —

• δ — Übergangsfunktion δ

• γ — Ausgabefunktion γ

Wie bei endlichen Automaten erweitern wir δ zu δ∗ : Q× Σ∗ → Q und wie folgt analog γzu γ∗ : Q× Σ∗ → ∆∗:

• γ∗(q, λ) =

• γ∗(q, wa) = für a ∈ Σ, w ∈ Σ∗

Die Leistung von A ist dann γA : Σ∗ → ∆∗ mit γA(w) = γ∗(q0, w). 2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 34: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

6 MEALY-AUTOMATEN 32

r s

yx

Abbildung 5

Mit dieser Definition ist die Leistung des obigen MlA tatsächlich Serienaddition im folgen-den Sinn: Entspricht w ∈ ({0, 1}2)∗ dem Paar (k1, k2) ∈ N2 wie in Kapitel 3, wobei beideBinärdarstellungen mit mindestens einer 0 beginnen, so entspricht γA(w) k1 + k2.

Als nächstes wollen wir den Schaltkreis in Abbildung 5 als MlA modellieren. Dieser Schalt-kreis hat Eingänge r und s, den Ausgang x und ein internes Signal y; neben den üblichenGattern (hier „oder“ und (dicker) Negationspunkt, die jeweils zusammen ein NOR ergeben)hat dieser Schaltkreis zwei Verzögerungsglieder bzw. Register.

Ohne diese kann man den Schaltkreis als asynchronen Schaltkreis mit folgendem Verhaltenverstehen. Der Schaltkreis befindet sich in einem stabilen Zustand, z.B. rsxy = 1001; wenndann die Eingabe auf 01 gesetzt wird, liefert das linke NOR immer noch 0, aber y ändertsich auf 0; erst jetzt ändert sich x auf 1, und der Zustand ist wieder stabil. Um Probleme zuvermeiden, muss hierbei die Umgebung die Eingaben auf 01 halten, bis Stabilisierung eintritt– der Schaltkreis muss im sog. Fundamentalmodus betrieben werden. (Dann realisiert er einRS-Flip-Flop, s.u.) Solche mehrstufigen Übergänge sind konzeptionell offenbar schwierig.

Einfacher sind getaktete Schaltkreise, die in der Praxis vorherrschend sind. Hier pufferndie Verzögerungsglieder die Werte von x und y, wobei wir gepufferte und Ausgabe-Signale alslokale Signale bezeichnen. Die Verzögerungsglieder liefern an ihren Ausgängen die alten Werte,auch wenn sich im aktuellen Takt neue Werte für x und y ergeben – die wir mit x′ und y′

bezeichnen wollen. Da nach „Durchschneiden“ der Verzögerungsglieder ein kombinatorischerSchaltkreis (also ohne Kreise) entsteht – das müssen und wollen wir fordern –, kann mangemäß „Pfeilrichtung“ (d.h. von den Eingaben und den gepufferten Signalen aus) die neuenWerte für alle Drähte in einem Durchgang bestimmen. Dieser Sichtweise wollen wir hier folgen.

Der Zustand des Schaltkreises entspricht den Werten der gepufferten Signale x und y. Istdieser Zustand 01 wie oben und die nächste Eingabe ist wieder 01, so ist x′y′ = 00. Ist diedarauffolgende Eingabe wieder 01, geht der Schaltkreis nach 10, bei 11 aber bleibt er in 00.Insgesamt bekommen wir folgende Übergangstabelle, wenn wir als Startzustand 00 wählenund die Eingabe 00 verbieten; daraus ergibt sich dann der MlA in Abbildung 6.

xy\rs 01 10 11

00 10 0001 0010 00

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 35: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

6 MEALY-AUTOMATEN 33

Abbildung 6

Jetzt wollen wir an mehreren Beispielen den Entwurf eines Schaltkreises mit Mealy-Auto-maten untersuchen. Das erste Beispiel ist ein T-Flip-Flop; es hat Zustände 0 und 1, mitdenen es ein Bit (zunächst 0) speichert – die Ausgabe ist gleich dem neuen Zustand; offenbarentspricht der Zustand hier einem lokalen Signal q, das ein Ausgabesignal ist. Bei Eingabea = 0 bleibt das Flip-Flop in seinem Zustand, bei Eingabe 1 wechselt es seinen Zustand.Abbildung 7 zeigt den MlA, aus dem wir wieder eine Tabelle gewinnen.

Zum Entwurf eines Schaltkreises empfiehlt es sich, die Tupel, die den möglichen Zuständenund Eingaben entsprechen, wie auf der linken Seite einer Wahrheitstafel aufzulisten; dazumuss man die Zustände binär codieren. Die Codierung ist hier schon gegeben; i.A. kann mansie geschickt und weniger geschickt wählen. Auf der rechten Seite stehen die gestrichenenZustandssignale und die Ausgaben.

1 / 1

1 / 0

0 1 0 / 00 / 1 qa q′

00011011

Abbildung 7

Wir erkennen, dass es sich hier einfach um ein . . . handelt. Zur Realisierung mit Standard-Gattern (hier: AND, OR, NOT) kann man im Zweifel auf die disjunktive Normalform (wasist das?) zurückgreifen und erhält die Gleichung q′ = . . . .

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 36: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

6 MEALY-AUTOMATEN 34

Es gibt also ein OR-Gatter mit Ausgabe q; diese Ausgabe führen wir über ein Verzöge-rungsglied zurück zu den Gattern, die q als Eingabe haben, und in diesem Fall auch alsAusgabesignal nach draußen. Dies ergibt folgende Schaltung:

Abbildung 8

Im Allgemeinen hat die Tabelle links die Eingaben und die Zustandssignale (die gepuffertwerden), rechts die Ausgaben und die (gestrichenen) Zustandssignale – die evtl. mit Ausgabenzusammenfallen können.

Analog wollen wir nun einen Schaltkreis entwickeln, der mittels Eingabesignal a eine 0-1-Folge erhält und sein Ausgabesignal x genau dann auf 1 setzt, wenn in der 0-1-Folge (inkl.aktuelle Eingabe) der Block von 1en seit der letzten 0 eine durch 4 teilbare Länge (evtl. 0)hat.

Das nächste Beispiel ist ein RS-Flip-Flop; Zustand und Ausgabe wie beim T-Flip-Flop.Diesmal gibt es zwei Eingabesignale r und s: bei 00 bleibt das RS-Flip-Flop in seinem Zustand,bei 01 wird der Zustand auf 1 (set), bei 10 auf 0 (reset) gesetzt; Eingabe 11 ist verboten.

Diesmal ist die Wahrheitstafel unvollständig; die freien Felder können wir nach Bedarffüllen. Z.B. können wir ausnutzen, dass q′ offenbar fast s ist. Dies führt auf q′ =

Eine andere Gleichung ist q′ =

Sind die beiden Booleschen Ausdrücke äquivalent?

Natürlich sind auch MlAen durch ihr endliches Gedächtnis beschränkt; dies wird z.B. durchfolgendes konkretes Ergebnis demonstriert.

Satz 6.2. Es gibt keinen MlA zur seriellen Multiplikation, der also wie der Serienaddierer zweiBinärzahlen als Eingabe bekommt und jeweils die entsprechende Stelle des Produkts ausgibt.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 37: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

6 MEALY-AUTOMATEN 35

Beweis. Angenommen, A sei so ein MlA und habe weniger als n Zustände. Ein „Lauf“ bei derEingabe von (2n, 2n) hätte also die Form

q000/0−→ . . .

11/0−→ q1

00/0−→ q2

00/0−→ . . .

00/0−→ qn

00/1−→

(Nach der Ausgabe von n+ 1 0en erreicht A q1 und nach 2n 0en qn.)

Offenbar gibt es 1 ≤ i < j ≤ n mit qi = qj. Da alle MlAen deterministisch sind, ist derAblauf nach qj bis qn derselbe wie nach qi, d.h. es gibt 1 ≤ k < n mit qk = qn. Dies führtzum Widerspruch, da qk anders auf 00 reagiert als qn. 2

Tatsächlich hängt die Ausgabe unserer bisherigen Beispiel-MlAen meist nur vom beim je-weiligen Übergang erreichten Zustand ab, was uns im nächsten Kapitel auf einen anderenAutomatentyp mit Ausgabe bringen wird.

Ein andersartiges Beispiel bekommt man, wenn man bei dem obigen 1er-Block-Automatenverlangt, dass die Länge des 1er-Blocks zudem positiv sein muss. Übung: Wie ändert sich dieSchaltkreiskonstruktion und der Schaltkreis? (Behalten Sie die Automatenzustände und ihreCodierung bei!)

Hier ein weiteres Beispiel: Abbildung 9 skizziert einen Spielautomaten. Bei A oder B kannman wiederholt eine Kugel einwerfen; die Kugel wird durch die passierten „Türen“ bei x1, x2

und x3 abgelenkt, die nach dem Ablenken in die jeweils andere Schrägstellung springen. Esgibt zwei Aufgaben:

1) Konstruiere einen Automaten, der gerade die Folgen über {A,B} akzeptiert, bei denendie letzte Kugel bei D austritt. Damit könnte man sich z.B. überlegen, wie man es erreicht,dass die 5. Kugel o.ä. bei D austritt.

2) Konstruiere einen Mealy-Automaten, der Folgen über {A,B} annimmt und jeweils aus-gibt, ob die letzte Kugel bei C oder D austritt.

Übung: Lösen Sie 2)! (Auf 1) kommen wir später.)

A B

C D

x1 x2

x3

Abbildung 9

Auf die Frage, welche Funktionen f sich als Leistung eines MlA beschreiben lassen, werdenwir jetzt eine Antwort geben. Offenbar muss gelten, dass die Ausgabe genauso lang ist wiedie Eingabe, und dass f(v) ein Präfix von f(vw) ist.

• Die Funktion f : Σ∗ → ∆∗ heißt längentreu, falls |f(w)| = |w| für alle w ∈ Σ∗.

• Die Funktion f heißt sequentiell, falls für alle v,w ∈ Σ∗ das Wort f(v) ein Präfix vonf(vw) ist, d.h. dass ein u ∈ ∆∗ existiert mit f(v)u = f(vw). Da dies u eindeutig

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 38: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

6 MEALY-AUTOMATEN 36

ist, können wir fv(w) = u definieren und erhalten damit eine Familie von Funktionenfv : Σ∗ → ∆∗.

Ist nun jede längentreue und sequentielle Funktion Leistung eines MlA? Man betrachte dieFunktion f , die beschreibt, dass eine Eingabe aus {a, b} mit 1 beantwortet wird, wenn diebisherige Folge von Eingaben die Form anbn hat, und mit 0 sonst. (Übung: Geben Sie eineformale Def. von f ! )

Diese Funktion ist längentreu und sequentiell, aber offenbar müsste ein entsprechender MlAdie anfänglichen a zählen können. Anders ausgedrückt: Erreicht man mit an Zustand q, mussq fan realisieren; alle fan sind verschieden (fan(bm) endet auf 1 gdw. n = m). Das kann nichtgehen.

• Das Gewicht von f ist die Anzahl der verschiedenen Funktionen fv.

Satz 6.3. Eine Funktion f : Σ∗ → ∆∗ ist genau dann die Leistung eines MlA, wenn sielängentreu und sequentiell mit endlichem Gewicht ist.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 39: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

7 MOORE-AUTOMATEN 37

7 Moore-Automaten

Bei den meisten Mealy-Automaten in Kapitel 6 hing die Ausgabe nur vom neuen Zustand,nicht aber vom alten Zustand oder vom Eingabezeichen ab. Dementsprechend führen wir einenweiteren Typ von endlichen Automaten mit Ausgabe ein.

Als Beispiel betrachten wir das T-Flip-Flop in Abbildung 7. Dieser Automat hat die geradegenannte spezielle Eigenschaft; formal bedeutet das: Es gibt eine Funktion β : Q → ∆ (vgl.γ : Q× Σ → ∆), so dass γ(q, a) = . . . für alle q ∈ Q und a ∈ Σ. Wir sagen, dass ein solcherMlA eine zustandsabhängige Ausgabe hat; beim Serienaddierer in Abbildung 4 ist dies z.B.nicht der Fall.

Dementsprechend löschen wir jetzt die Ausgabe an den Kanten und fügen die passende Aus-gabe an den Zuständen ein; wir erhalten den folgenden Moore-Automaten. (Welches Problemkönnte auftreten? Führen Sie dieselbe Konstruktion für Abbildung 6 durch.)

1

1

0/0 1/1 00

Abbildung 10

Definition 7.1. Ein Moore-Automat (MrA) über dem Eingabealphabet Σ und dem Ausgabe-alphabet ∆ ist ein Tupel A = (Q,Σ,∆, δ, β, q0), wobei:

• Q —

• q0 ∈ Q —

• δ — Übergangsfunktion δ

• β — Ausgabefunktion β

Wie bei endlichen Automaten erweitern wir δ zu δ∗ : Q × Σ∗ → Q und wie folgt β zuβ∗ : Q× Σ∗ → ∆∗:

• β∗(q, λ) =

• β∗(q, wa) = für a ∈ Σ, w ∈ Σ∗

Die Leistung von A ist dann βA : Σ∗ → ∆∗ mit βA(w) = β∗(q0, w). 2

Mit dieser Definition ist die Leistung des obigen MrA A im wesentlichen dieselbe wie diedes MlA in Abbildung 7, hier mit A′ bezeichnet. Es gibt aber einen Unterschied: Der MrA A

und A′ sind also äquivalent im folgenden Sinn: Für alle w ∈ {0, 1}∗ gilt γA′(w) =

Da man die obige Konstruktion rückwärts auf jeden MrA anwenden kann, kann man MrAenals spezielle MlAen auffassen. (Überzeugen Sie sich, dass Sie das verstanden haben!)

Einen weiteren MrA sehen Sie in Abbildung 11; was tut er?

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 40: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

7 MOORE-AUTOMATEN 38

0/0 11/3

2/2

1

0

0

01

1

1

1

1/1 12/0 10/2

2

2

2 2

2

2

00

1

0

Abbildung 11

Little lost robot

Ein Robot wird auf einen Knoten eines Netzwerkes, d.h. eines ungerichteten Graphen G

gesetzt; er soll – z.B. zu Wartungszwecken – alle Ecken dieses Graphen wiederholt ablaufen.

Dazu ist bekannt, dass diam(G) ≤ D und dass der Grad einer Ecke höchstens m ist fürbekannte Werte D und m. Die Kanten einer Ecke sind beliebig, aber fest von 1 bis d (Gradder Ecke) durchnumeriert; dabei kann die Kante vw aus Sicht von v eine Nummer, aus Sichtvon w eine völlig andere Nummer haben.

Weiter erhält der Robot beim Betreten einer Ecke die Information (i, d); dabei ist i dielokale Nummer der Kante, über die er gekommen ist, und d der Grad der Ecke. Aus dieserInformation kann man nicht schließen, ob und wann man schon einmal diese Ecke besuchthat; läuft man jetzt aber über die lokale Kante i zurück, erreicht man natürlich die Ecke, inder man unmittelbar vorher war.

Helfen Sie unserem kleinen Freund, indem Sie eine geeignete Steuerung als MrA entwerfen;der MrA soll jeweils die lokale Kante ausgeben, die der Robot als nächstes beschreiten soll.

Kommen wir zu der Beobachtung zurück, dass MrAen spezielle MlAen sind. Sind MlAenwirklich allgemeiner?

Dazu betrachten wir den Serienaddierer A in Abbildung 4. Ein entsprechender MrA wirdzunächst eine unerwünschte Ausgabe – z.B. 0 – machen, die wir ja ignorieren wollen; er wirdsich sicherlich den Übertrag merken müssen, aber zudem am Anfang bei 00 in einen anderenZustand (mit Ausgabe 0) gehen als bei 01 (Ausgabe 1). Wir brauchen also für Zustand q0(und analog für jeden Zustand von A) und jede Ausgabe beim Übergang nach q0 eine eigeneKopie von q0. Also ist ein Teil des MrA in Abbildung 12 zu sehen (links die beiden Kopienvon q0; ab/b: Kopie b des Zustands a mit Ausgabe b); vervollständigen Sie ihn.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 41: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

7 MOORE-AUTOMATEN 39

11 00/0 10/0 00

0110

01/1

00

Abbildung 12

Dies Verfahren lässt sich ganz allgemein durchführen:

Satz 7.2. Zu jedem MlA A = (Q,Σ,∆, δ, γ, q0) gibt es einen äquivalenten MrA A′ = (Q′,Σ,

∆, δ′, β, q′0) in dem Sinn, dass für alle w ∈ Σ∗ gilt: γA(w) = ∆−1βA′(w) – und umgekehrt.

Zum Beweis verwenden wir eine angepasste Version von Bisimulation (Idee von Mark Schä-fer):

Definition 7.3. Seien der Mealy-Automat A und der Moore-Automat A′ über Σ und ∆

gegeben. A und A′ heißen MM-bisimular, wenn eine MM-Bisimulation für A und A′ existiert,d.h. eine Relation R ⊆ Q×Q′ mit folgenden Eigenschaften:

(1) (q0, q′0) ∈ R

(2) Aus (q, q′) ∈ R, δ(q, a) = q1 und δ′(q′, a) = q′1 folgt (q1, q′1) ∈ R und β(q′1) = γ(q, a).

2

Eine MM-Bisimulation ist fast dasselbe wie eine normale Bisimulation. Hier hat jeder Zu-stand zu jeder Eingabe genau eine Kante; es wird also nur gefordert, dass die erreichtenZustände wieder in der Relation stehen und zudem die Ausgaben passen. Die Ausgabe wirdin A während des Übergangs, bei A′ nach dem Übergang erzeugt.

Der folgende Satz ist daher das Gegenstück zur Sprachäquivalenz bei gewöhnlichen bisi-mularen Automaten unter Berücksichtigung der ’überflüssigen’ ersten Ausgabe eines Moore-Automaten.

Satz 7.4. Seien der Mealy-Automat A und der Moore-Automat A′ MM-bisimular mit derMM-Bisimulation R. Dann gilt für alle w ∈ Σ∗:

(q, q′) ∈ R⇒ γ∗(q, w) = β(q′)−1β∗(q′, w)

Für Interessierte: Der formale Beweis dieses Satzes ist notationell erstaunlich aufwendig.Man zeigt zunächst mit Induktion ∀w ∈ Σ∗ : (q, q′) ∈ R⇒ (δ∗(q, w), δ′∗(q′, w)) ∈ R (∗).

Dann zeigt man den Satz wiederum durch Induktion über |w|:

w = λ: γ∗(q, λ) = λ = β(q′)−1β(q′) = β(q′)−1β∗(q′, λ) X

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 42: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

7 MOORE-AUTOMATEN 40

w = w′a: Die Behauptung gilt laut Induktionsvoraussetzung für w′, d.h. (q, q′) ∈ R ⇒

γ∗(q, w′) = β(q′)−1β∗(q′, w′).

γ∗(q, w′a)

(Definition von γ∗) = γ∗(q, w′) γ(δ∗(q, w′), a)

(Induktionsvoraussetzung) = β(q)−1β∗(q, w′) γ(δ∗(q, w′), a)

((∗) und Definition 7.3.(2,3)) = β(q)−1β∗(q, w′) β(δ′(δ′∗(q′, w′), a))

(Definition von δ′∗) = β(q)−1β∗(q, w′) β(δ′∗(q′, w′a))

(Definition von β∗) = β(q)−1β∗(q, w′a)

2

Beweis von 7.2: Nach obigen Überlegungen müssen wir nur die erste Aussage zeigen; seialso A gegeben. Wir definieren A′ wie folgt, wobei wir in Anwendungen Q′ auf die erreichbarenZustände beschränken wollen:

• Q′ =

• δ′

• β

• q′0 =

Anstatt die Aussage direkt zu zeigen, werden wir eine MM-Bisimulation angeben, worausdie Aussage dann nach Satz 7.4 – angewandt auf die Zustände q0 und q′0 – direkt folgt.

Wir definieren die Relation R ⊆ Q× (Q× ∆)) als R = {(q, (q, x)) | q ∈ Q,x ∈ ∆}. DiesesR ist eine MM-Bisimulation:

(1) (q0, (q0, y)) ∈ R

(2) Sei (q, (q, x)) ∈ R und δ(q, a) = q1 mit γ(q, a) = x′. Aus der Definition von δ′ folgtδ′((q, x), a) = (δ(q, a), γ(q, a)) = (q1, x

′). Offensichtlich gilt (q1, (q1, x′)) ∈ R und nach

Definition β((q1, x′)) = x′ = γ(q, a). 2

Natürlich sind auch die Fähigkeiten von MrAen begrenzt. Wir wollen uns kurz folgendesProblem überlegen: Gegeben sei eine Sprache L ⊆ Σ∗; gesucht ist ein MrA, der nach demLesen eines Wortes w eine 1 ausgibt, wenn w ∈ L, und 0 sonst. (Für alle Präfixe wurden dannbereits die entsprechenden Ausgaben gemacht.) Für welche Sprachen L existiert ein solcherMrA?

Ein solcher MrA ist nichts anderes als

Übung: Fügen Sie Satz 7.2 und den letzten Punkt zusammen, um die Frage 1) zu demSpielautomaten aus Kapitel 6 zu beantworten; beginnen Sie Ihre Überlegungen mit dem MlAzu Frage 2)!

Auch bei MrAen (und MlAen) möchte man mit möglichst wenig Zuständen auskommen, d.h.jeweils einen MrA mit gleicher Leistung und minimaler Zustandszahl finden. Wie wir geradegesehen haben, können wir im Fall |∆| = 2 einfach die Verfahren aus Kapitel 4 verwenden.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 43: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

7 MOORE-AUTOMATEN 41

Tatsächlich ist dies auch im allgemeinen möglich. Wir müssen nur beachten, dass wir un-mittelbar nicht die Endzustände von den übrigen unterscheiden können, sondern generell

Entsprechend müssen wir mit einer feineren Partition beim Algorithmus von Hopcroft be-ginnen bzw. zu Beginn mehr Kreuze im „Tabellenverfahren“ setzen. Machen Sie letzteres fürden MrA in Abbildung 11 und konstruieren Sie den entsprechenden reduzierten MrA!

0 1 2 10 11

1

2

10

11

12

Abbildung 13

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 44: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

8 ABSCHLUßEIGENSCHAFTEN 42

8 Abschlußeigenschaften

Abschlußeigenschaften können nützlich sein um zu begründen, warum eine Sprache regulärist (s. Beispiel 8.2), oder auch warum sie nicht regulär ist: Ist L1 regulär, L1 ∪L2 aber nicht,so kann nach dem folgenden Satz auch L2 nicht regulär sein.

Satz 8.1. Seien E ⊆ Σ∗ endlich und L1, L2 ⊆ Σ∗ regulär. Dann sind neben E (effektiv)regulär:

L1 ∪ L2, L1 · L2, L∗1, L1 ∩ L2, L1 := Σ∗ − L1

In Worten: Die regulären Sprachen sind effektiv abgeschlossen unter (endlicher) Vereini-gung, Konkatenation, Sternbildung, (endlichem) Durchschnitt und Komplementbildung.

Beispiel 8.2. i) Es läßt sich leicht ein EA (nicht so leicht aber ein DEA) finden zu L =

{w ∈ {a, b}∗ | w enthält das zusammenhängende Teilwort aaba}. Daher ist auch L

regulär; wie ein EA zu L aussieht, ist aber nicht so offensichtlich.

ii) Betrachte L1 aus Beispiel 5.3. Wäre L1 regulär, so auch L1 ∩ ab∗c∗ = {abmcm | m ≥ 0}.

Das dies nicht der Fall ist, kann man mit dem normalen Pumping Lemma sehen, womitgezeigt ist, dass L1 nicht regulär ist; s.a.u.

iii) Sei L = {anbm | n 6= m}. Man kann direkt mit dem normalen Pumping Lemma sehen,dass L nicht regulär ist; dies ist aber kompliziert.

Wegen der Negation scheint das Komplement nützlich: Wäre L regulär, so auch L . . .Dies ist aber bekanntermaßen nicht regulär, also auch nicht L.

Satz 8.3. Ist L regulär, so auch LR.

Beweis. Sei A ein buchstabierender Automat mit L(A) = A. Wir definieren

AR = (Q ∪̇ {qR

0 } ,Σ, δR ∪ {(qR

0 , λ, q) | q ∈ F} , qR

0 , {q0}),

wobei δR = {(p, a, q) | (q, a, p) ∈ δ}. (Das heißt, wir drehen alle Pfeile um und vertauschen imPrinzip Anfangs- und Endzustände.) Es gilt LR = L(AR). 2

Hat man reguläre Sprachen über rechtslineare Grammatiken definiert, so kann man mitdiesem Satz zeigen: L ⊆ Σ∗ ist genau dann regulär, wenn L durch eine linkslineare GrammatikG erzeugt wird.

Weitere Abschlusseigenschaften definieren sich durch Monoid–Homomorphismen; dies sindstrukturerhaltende Abbildungen; dabei ist die Struktur eines Monoids seine Operation undsein Einselement.

Definition 8.4. Eine Abbildung h zwischen zwei Monoiden M und N heißt Monoid-Homo-morphismus, falls:

i) ∀u, v ∈M : h(u ·M v) = h(u) ·N h(v)

ii) h(1M ) = 1N 2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 45: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

8 ABSCHLUßEIGENSCHAFTEN 43

Die Charakteristika des Monoids werden also durch einen Homomorphismus übertragen. DieÜbertragung wird vielleicht noch deutlicher mit folgender Sichtweise: charakteristisch für einMonoidM sind zwei Relationen, ·M = {(u, v, u·M v) | u, v ∈M} und {1M}; diese werden durchh in die entsprechenden Relationen von N abgebildet, also h(·M ) = {(h(u), h(v), h(u ·M v)) |

u, v ∈M} ⊆ ·N und h({1M}) ⊆ {1N}.

In der Theorie der formalen Sprachen behandeln wir in der Regel Homomorphismen h :

Σ∗ −→M (M ein Monoid); dabei ist nach Definition h(a1 · · · an) = h(a1) . . . h(an); da λ auf1M abgebildet werden muss, kennt man ganz h, wenn man seine Bilder für alle Buchstabenkennt. Ist z.B. h(a) = of und h(b) = do, so ist h(abb) = und h(ba) =

In anderen Worten: jede Abbildung h : Σ −→ M läßt sich eindeutig zu einem Monoid-Homomorphismus h : Σ∗ −→ M wie gerade angegeben fortsetzen; man sagt, Σ∗ ist das freieMonoid über Σ.

In der Theorie der formalen Sprachen ist ein Homomorphismus h (ohne nähere Bezeichnung)ein Monoid–Homomorphismus Σ∗ −→ Σ′∗ für Alphabete Σ, Σ′.

Definition 8.5. Eine Substitution f ist ein Monoid–Homomorphismus Σ∗ −→ P(Σ′∗); sie istregulär, wenn ∀a ∈ Σ : f(a) ist regulär. Wir erweitern f auf P(Σ∗) durch f(L) =

⋃w∈L f(w).

Wenn man von inverser Substitution spricht, fasst man f als Relation aller Paare (v,w)

mit w ∈ f(v) auf. Also ist f−1(L) = {v | ∃w ∈ L : w ∈ f(v)} = {v | f(v) ∩ L 6= ∅} – nichtetwa f−1(L) = {v | f(v) = L}.

Erinnerung: P(Σ′∗) ist ein Monoid (siehe 1.7).

Da Sprachen mit genau einem Wort immer regulär sind, ist also ein Homomorphismus einespezielle reguläre Substitution. f ist gegeben durch die f(a) ⊆ Σ′∗, a ∈ Σ.

Beispiele 8.6. i) Sei f(0) = a und f(1) = b∗; dann ist f(010) = ab∗a und f(0∗(0+1)1∗) =

a∗(a+ b∗)b∗ = a∗b∗

ii) Sei h(0) = aa, h(1) = aba; dann ist h(10) = abaaa oder h((01)∗) = (aaaba)∗. SeiL = (ab + ba)∗a. Wir wollen auf L den inversen Homomorphismus h−1 anwenden. Esgilt:

h(λ) = λ /∈ L

h(0w) = aah(w) /∈ L

h(1) = aba ∈ L

h(10w) = abaaah(w) /∈ L

h(11w) = abaabah(w) /∈ L

=⇒ h−1(L) = {1} .

Ferner h(h−1(L) = {aba} $ L. Ganz allgemein gilt: h(h−1(L)) ⊆ L und h−1(h(L)) ⊇ L.

Um eine Reihe weiterer Abschlusseigenschaften – u.a. bzgl. regulärer Substitution (alsospeziell bzgl. Homomorphismen) und inversen Homomorphismen – zu zeigen, führen wir eineVerallgemeinerung der Mealy-Automaten ein.

Definition 8.7. Ein (endlicher) Transduktor (ET) über den Ein- bzw. Ausgabe-AlphabetenΣ und ∆ ist ein Tupel T = (Q,Σ,∆, δ, q0, F ), wobei:

• Q — endliche Menge von Zuständen

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 46: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

8 ABSCHLUßEIGENSCHAFTEN 44

• q0 ∈ Q — Startzustand

• F ⊆ Q — Menge der (akzeptierenden oder) Endzustände

• δ ⊆ Q× Σ∗ × ∆∗ ×Q ist endlich — Übergangsrelation

Wir schreiben die Elemente von δ als (p, u/v, q); liest T im Zustand p die Eingabe u ∈ Σ∗,so gibt er v ∈ ∆∗ aus und geht in q über; die Ausgabe ist also in δ integriert.

Wir erweitern δ zu δ∗ durch:

i) ∀p ∈ Q: (p, λ/λ, p) ∈ δ∗

ii) ∀p, q, q′ ∈ Q, u, u′ ∈ Σ∗, v, v′ ∈ ∆∗ : (p, u/v, q′) ∈ δ∗, (q′, u′/v′, q) ∈ δ =⇒

Die Leistung von T ist die Relation T = {(u, v) | ∃ q ∈ F : (q0, u/v, q) ∈ δ∗} (Überladungvon T ), die als Transduktion bezeichnet wird. Wir schreiben auch T (u) = {v | (u, v) ∈ T}

und erweitern diese Funktion wie üblich auf Sprachen.

Zwei Transduktoren heißen äquivalent, wenn sie dieselbe Transduktion beschreiben. 2

Man beachte, dass T (u) = . . . , wenn T u nicht akzeptierend lesen kann. Wieder können wir

Abläufe von T intuitiv schreiben: q0u1/v1

−→ q1u2/v2

−→ . . .un/vn

−→ qn mit u = u1 . . . un, v = v1 . . . vn

und qn ∈ F beschreibt, dass (und wie) T u akzeptierend liest und dabei v ausgibt.

Ein Mealy-Automat A = (Q,Σ,∆, δ, γ, q0) ist im Prinzip ein spezieller Transduktor, näm-lich T = (Q,Σ,∆, δ′, q0, . . .) mit δ′ = {

T hat dieselbe Leistung wie A.

Transduktoren passen auch gut zuist im Prinzip ein spezieller Transduktor, nämlich T = (Q,Σ,

Es gilt w ∈ L(A) ⇐⇒ T (w) =

Eine andere Entsprechung ist der Transduktor T = (Q,

Es gilt L(A) = T (λ).

Definition 8.8. Ein Transduktor T ist fast-buchstabierend oder in Standardform, wenn δ

⊆ Q× (Σ ∪ {λ}) × (∆ ∪ {λ}) ×Q. 2

Satz 8.9. Jeder Transduktor T ist effektiv äquivalent zu einem Transduktor T ′ in Standard-form.

Beweis. Erstes Problem: Die Eingabe eines Übergangs hat mehr als ein Zeichen. Lösung:

Zweites Problem: Die Ausgabe eines Übergangs hat mehr als ein Zeichen. Lösung:

2

Transduktoren sind ein Werkzeug, um Abschlusseigenschaften zu zeigen; entscheidend dafürist:

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 47: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

8 ABSCHLUßEIGENSCHAFTEN 45

Satz 8.10. Die regulären Sprachen sind effektiv unter Transduktion abgeschlossen, d.h. wennL regulär, so auch

Beweis. Sei A = (QA,Σ, δA, qA0, FA) ein buchstabierender EA zu L und T o.E. in Standard-form. Die Idee ist es, A und T parallel laufen zu lassen und dabei die von A gelesenen Zeichenals Eingabe für T aufzufassen, aber danach zu verstecken. Wir benötigen also eine Variationder bekannten Konstruktion für

Wir konstruieren den EA B über ∆ zu T (L):

• QB =

• qB0 =

• FB =

Beachte: A muss ein Wort w akzeptierend lesen – sonst interessiert uns T (w) nicht;genauso muss T w akzeptierend lesen – sonst trägt T (w) nichts zu T (L) bei.

• δB =

Technischer Trick: Wir fügen jedem Zustand von A eine λ-Schlinge hinzu; dies ändert dieSprache nicht. Wenn wir unsere Konstruktion auf dieses modifizierte A anwenden, können wirdie zweite Menge in δB weglassen, falls wir in der ersten a = λ zulassen.

Ist v ∈ L(B), so gibt es einen akzeptierenden Ablauf (qA0, q0)v1−→ (p1, q1)

v2−→ . . . (pn, qn)

mit v = v1 . . . vn – vi ∈ –, pn ∈ FA und qn ∈ F . Diesem Ablauf liegen zwei akzeptierende

Abläufe qA0u1−→ p1

u2−→ . . .un−→ pn mit u = u1 . . . un ∈ L – ui ∈ – und q0

u1/v1

−→ q1u2/v2

−→

. . .un/vn

−→ qn zugrunde. Demnach ist v ∈ T (u) ⊆ T (L).

Ist umgekehrt v ∈ T (L), so gibt es u ∈ L mit v ∈ T (u). Es gibt also akzeptierende Abläufe

qA0u1−→ p1

u2−→ . . .un−→ pn mit u = u1 . . . un und pn ∈ F und q0

u1/v1

−→ q1u2/v2

−→ . . .un/vn

−→ qn mitv = v1 . . . vn und qn ∈ F . Da T evtl. λ-Übergänge machen muss, können wir eigentlich nichtannehmen, dass die beiden Abläufe so gut zusammenpassen – der zweite könnte

Aufgrund unserer Modifikation können wir aber annehmen, dass A immer genau dort einenλ-Übergang macht, wo T einen solchen zur Erzeugung von v benötigt. Die Abläufe lassen sichoffenbar zu einem Ablauf wie oben zusammenfügen, so dass v ∈ L(B). 2

Satz 8.11. Die regulären Mengen sind (effektiv) unter Präfix-, Suffix- und Infix-Bildung (Ope-rationen pref, suff und infix) sowie Homomorphismen und regulärer Substitution abgeschlos-sen, wobei pref(L) = {v | v ist Präfix eines w ∈ L}, suff(L) = {v | ∃u : uv ∈ L} undinfix(L) = {v | ∃u,w : uvw ∈ L}.

Beweis. Für die ersten drei Operationen benutzen wir die folgenden drei Transduktoren undSatz 8.10:

Homomorphismen sind nur spezielle reguläre Substitutionen, sei also f eine reguläre Sub-stitution und Aa für jedes a ∈ Σ ein EA zu f(a). Der Transduktor, der f ausrechnet (und

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 48: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

8 ABSCHLUßEIGENSCHAFTEN 46

zeigt, dass f eine Transduktion ist), muss also bei Eingabe von a ein Wort aus L(Aa) erzeugenund dazu Aa ansteuern; vgl. Bsp. 8.6 i). Sein Start- ist sein einziger Endzustand:

2

Für den Abschluss unter inversen Homomorphismen betrachten wir kurz inverse Transduk-tionen.

Satz 8.12. Ist T eine Transduktion, so auch T−1.

Beweis. Ersetze in dem Transduktor zu T jede Kante (p, u/v, q) ∈ δ durch (p, v/u, q). 2

Exkurs:

Man kann diesen Satz auch als Korollar zu einer Charakterisierung der Transduktionen ge-winnen. Zur Vorbereitung wollen wir zu einem festen gerichteten Graphen G mit EckenmengeV = {v0, . . . , vn} einen EA über (V V ) suchen (wobei (vivj) der Kante vivj ∈ E entspricht),der genau solche w akzeptiert, die einen Weg von v0 nach v1 oder nach vn in G beschreiben.Man beachte, dass wir (vivj) als ein Zeichen auffassen.

Bsp.:

Satz 8.13 (Nivat). Eine Relation R ⊆ Σ∗ × ∆∗ ist eine Transduktion genau dann, wenn eseine reguläre Sprache L über Σ′ und Homomorphismen g : Σ′∗ → Σ∗ und h : Σ′∗ → ∆∗ gibtmit R = {(g(w), h(w)) | w ∈ L}.

Beweis. Gibt es L, g und h, so wählen wir einen buchstabierenden EA A = (Q,Σ′, δA, q0, F ) zuL und konstruieren T = (Q,Σ,∆, δ, q0, F ), indem wir jede Kante (p, a, q) ∈ δA ersetzen durch(p, g(a)/h(a), q). Offenbar entspricht jeder akzeptierende Ablauf q0

w1−→ q1w2−→ . . .

wn−→ qn mit

w = w1 . . . wn von A dem Ablauf q0g(w1)/h(w1)

−→ q1g(w2)/h(w2)

−→ . . .g(wn)/h(wn)

−→ qn, in dem T g(w)

akzeptierend liest und dabei h(w) ausgibt.

Sei nun der Transduktor T = (Q,Σ,∆, δ, q0, F ) mit Leistung R gegeben. Wie in der Vor-bereitung werden wir einen Automaten A = (Q,Σ′, δA, q0, F ) konstruieren, wobei Σ′ ⊆

QΣ∗/∆∗Q. Dabei nehmen wir o.E. an, dass Q zu Σ und ∆ disjunkt ist (wir können nichtannehmen, dass diese beiden disjunkt sind!), und wir betrachten pu/vq als ein Zeichen; be-achte, dass wir nur die endlich vielen dieser Zeichen benötigen, die Kanten von T entsprechen,während QΣ∗/∆∗Q unendlich viele Zeichen enthält.

Wir erhalten δA, indem wir jede Kante (p, u/v, q) ∈ δ ersetzen durch (p, pu/vq, q). Die Wortew ∈ L(A) haben gerade die Form q0u1/v1q1 q1u2/v2q2 . . . qn−1un/vnqn; sie entsprechen genau

den Abläufen q0u1/v1

−→ q1u2/v2

−→ . . .un/vn

−→ qn von T , bei denen u = u1 . . . un akzeptierend gelesenund v = v1 . . . vn ausgegeben wird. Definieren wir nun g(pui/viq) = ui und h(pui/viq) = vi

sind wir fertig. 2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 49: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

8 ABSCHLUßEIGENSCHAFTEN 47

Ende Exkurs

Satz 8.14. Die regulären Mengen sind (effektiv) abgeschlossen unter inversen Homomorphis-men und inverser regulärer Substitution.

Beweis. Es genügt, eine reguläre Substitution f zu betrachten. Im Beweis zu Satz 8.11 habenwir gezeigt, dass f eine Transduktion ist und der Abschluss unter f daher aus Satz 8.10 folgt.Wegen Satz 8.12 ist aber auch f−1 eine Transduktion, und wir sind fertig. 2

Anwendung:

i) Jetzt können wir unsere Betrachtung von L1 aus Beispiel 5.3 beenden; dazu sei h derHomomorphismus mit h(a) = λ, h(b) = a, h(c) = b. Wäre nun L1 regulär, so auchh(L1 ∩ab

∗c∗) = {ambm | m ≥ 0}. Dies ist bekanntermaßen nicht der Fall, womit gezeigtist, dass L1 nicht regulär ist.

ii) L0 = {anbcn | n ≥ 0} ist nicht regulär. Andernfalls wäre

iii) L = {anban | n ≥ 0} ist nicht regulär. Sonst wäre mit h(a) = h(c) = a und h(b) = b die„geschnittene Urbildmenge“ h−1(L) ∩ a∗bc∗ = L0 regulär.

iv) L ={anbc2n+1 | n ≥ 0

}ist nicht regulär. Sonst wäre für h mit h(a) = a, h(b) = bc,

h(c) = c2 die Urbildmenge h−1(L) = L0 regulär.

Für eine Sprache L ist max(L) = {w ∈ L | wenn w echtes Präfix von v, so v 6∈ L}. Z.B. istmax({ambn | m ≥ n ≥ 0}) =

Satz 8.15. Die regulären Mengen sind (effektiv) abgeschlossen unter max-Bildung.

Beweis. Sei L regulär, A ein entsprechender DEA; man modifiziere A zu A′, indem man alleq aus F entfernt, falls v ∈ Σ+ existiert mit δ∗(q, v) ∈ F .

Üb.: Könnte man auch v ∈ Σ∗ schreiben?

Könnte man die Konstruktion genausogut bei einem allgemeinen EA A ausführen? 2

Anwendung: {ambn | m ≥ n ≥ 0} ist nicht regulär; s.o.

Beispiel 8.16. zur Erinnerung; vgl. Definition 1.10

L ={a2nb2m | n,m ≥ 0

}; K = {a, aab};

K−1L ={a2n−1b2m | n ≥ 1, m ≥ 0

}∪

{b2m−1 | m ≥ 1

}

Satz 8.17. L sei regulär und K ⊆ Σ∗ beliebig. Dann sind K−1L und LK−1 (nicht effektiv)regulär.

Beweis. Für K−1L: Sei A ein EA für L. Wir fügen einen neuen Anfangszustand q′0 und λ–Kanten zu allen q ein mit ∃v ∈ K : (q0, v, q) ∈ δ∗ . Der neue endliche Automat A′ akzeptiertu genau dann, wenn: ∃v ∈ K : vu ∈ L. 2

Beispiel 8.18. (Fortsetzung) Ein Automat für obiges L; die q im Beweis sind 1 und 2.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 50: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

8 ABSCHLUßEIGENSCHAFTEN 48

Bemerkung: Dies ist ein mathematischer, nichtkonstruktiver Existenzbeweis (wieso?). Miteiner Konstruktion könnten wir eine beliebige Menge K auf Leerheit testen: Es ist K−1Σ∗ =

∅ ⇐⇒ K = ∅. Wäre K−1Σ∗ effektiv regulär, könnten wir den resultierenden Automaten aufLeerheit testen. Bereits für kontextsensitive Sprachen K ist Leerheit aber nicht entscheidbar.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 51: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

9 BÜCHI-AUTOMATEN 49

9 Büchi-Automaten

Man kann endliche Automaten auch verwenden, um unendliche Wörter zu akzeptieren. Ur-sprünglich dienten Überlegungen in dieser Richtung dazu, Probleme der Logik zu lösen; vgl.Kapitel 3.

Fasst man die Buchstaben eines Alphabets Σ als Aktionen eines Systems auf, so sind un-endliche Wörter unendliche Aktionsfolgen, die Abläufe des Systems beschreiben. Solche un-endlichen Abläufe sind ganz natürlich bei sogenannten reaktiven Systemen, die immer wiederauf Anforderungen reagieren sollen (wie z.B. Betriebssysteme) und daher eigentlich nicht ter-minieren. Endliche Automaten für unendliche Wörter, wie z.B. Büchi-Automaten, könnenalso als Modelle reaktiver Systeme dienen.

Will man unendliche Abläufe logisch spezifizieren, kann man temporale Logik verwenden;speziell haben Sie in Logik für Informatiker LTL (bzw. PLTL) (linear-time temporal logic)kennengelernt. PLTL-Formeln beschreiben unendliche Zustandsfolgen, andere Versionen vonLTL beschreiben unendliche Aktionsfolgen. Model Checking ist i.A. das Problem zu entschei-den, ob eine Struktur eine logische Formel erfüllt. Im gegenwärtigen Kontext verstehen wirdarunter konkreter das Problem zu entscheiden, ob alle Abläufe eines Büchi-Automaten eineLTL-Formel erfüllen. Interessanterweise kann man LTL-Formeln in Büchi-Automaten über-setzen, so dass Model Checking rein automatentheoretisch gelöst werden kann.

Ein unendliches Wort über Σ ist eine unendliche Folge w = w1w2w3 . . . mit wi ∈ Σ;Σω ist die Menge dieser Wörter. Offenbar kann man ein endliches mit unendlichen Wortkonkatenieren oder auch unendlich viele endliche Wörter. Damit ist auch klar, was ein Präfixvon w ist, nämlich

Um unendliche Wörter notieren zu können, soll aω aaa . . . bezeichnen, vω die unendlicheKonkatenation vvv . . . für v ∈ Σ∗, und schließlich Lω = {w ∈ Σω | w = w1w2w3 . . . mitwi ∈ L}. Mit dieser Notation können wir die regulären Ausdrücke erweitern; dann bezeichnetz.B. b∗(ab∗)ω die Menge aller Wörter über {a, b}, die

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 52: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

9 BÜCHI-AUTOMATEN 50

9.1 Definition und Abschlusseigenschaften

Definition 9.1. Ein (nichtdeterministischer) Büchi-Automat (BA) über Σ ist ein Tupel B =

(Q,Σ, δ, q0, F ), wobei:

• Q — endliche Menge von Zuständen

• q0 ∈ Q — Startzustand

• F ⊆ Q — Menge der akzeptierenden oder Endzustände

• δ ⊆ Q× Σ ×Q — Übergangsrelation

B heißt deterministisch, wenn δ eine Funktion Q× Σ → Q ist.

Ein Ablauf α von B hat die Form q0a1−→ q1

a2−→ q3a3−→ . . . wobei (qi−1, ai, qi) ∈ δ für

alle i ≥ 1 (genau wie bei . . . . . . ). INF (α) := {q ∈ Q | q tritt unendlich oft in α auf}. GiltINF (α)∩F 6= ∅, so akzeptiert B das Wort a1a2a3 . . .; die Sprache L(B) (auch der Deutlichkeithalber Lω(B)) von B ist die Menge aller akzeptierten Wörter.

Eine Sprache L heißt ω-regulär, wenn es einen Büchi-Automaten B gibt mit L = L(B).Büchi-Automaten B1, B2 heißen äquivalent, wenn L(B1) = L(B2). 2

Ein akzeptierender Ablauf von B trifft also einen Zustand von F unendlich oft. Genausogut kann man sagen, dass er F unendlich oft trifft ; da

a

b

b,c

a,cB1

a

b

a,b,c

B 3

a

b

b

a

B 2

Abbildung 14

Der Büchi-Automat B1 beschreibt alle Wörter über {a, b, c}, bei denen jedem a ein b folgt– 2(a → 3b), in Worten: always wenn a, so eventually b. Welches sind die Sprachen von B2

und B3?

Ein Büchi-Automat B4, der alle w ∈ {a, b}ω akzeptiert, die auf bω enden – 32b, eventuallyalways b:

Abbildung 15

Beachten Sie, dass B4 das Komplement von L(B2) akzeptiert, im Gegensatz zu B2 abernicht deterministisch ist. Das ist kein Zufall:

Satz 9.2. Es gibt einen Büchi-Automaten (nämlich B4), der zu keinem deterministischenBüchi-Automaten äquivalent ist.

Beweis. Angenommen, B sei doch so ein deterministischer Büchi-Automat. Da B abω akzep-tiert, gibt es auf dem Ablauf dazu einen Endzustand q1 mit δ∗(q0, abn1) = q1. Da B abn1abω

akzeptiert, gibt es auf dem Ablauf dazu (der zunächst durch q1 führt) einen Endzustand q2mit δ∗(q0, abn1abn2) = q2. So fortfahrend finden wir ein Wort w = abn1abn2abn3 . . ., auf dessenAblauf von B die Endzustände q1, q2, q3, . . . liegen, d.h. w ∈ L(B), aber w /∈ L(B4). 2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 53: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

9 BÜCHI-AUTOMATEN 51

Dies Ergebnis ist zunächst unerfreulich: Deterministische EA kann man als realistische Pro-gramme sehen, nichtdeterministische nicht. Auch zeigt dieser Satz, dass die von deterministi-schen Büchi-Automaten akzeptierten Sprachen nicht unter Komplementbildung abgeschlossensind.

Hingegen sind ω-reguläre Sprachen unter Komplement abgeschlossen; die Konstruktion istaber schwer zu verstehen und auch sehr aufwendig. (Bei einem BA mit n Zuständen hat derKomplement-BA 2c n log n Zustände für eine Konstante c.) Man sollte sie also vermeiden!

Der Abschluss unter Vereinigung folgt mit derselben Konstruktion wie bei buchstabierendenEA. Der Abschluss unter Durchschnitt führt aber auf ein Problem mit den Endzuständen.

Übung: Erweitern Sie B2 zu B′2, so dass dieser alle Wörter aus {a, b, c}ω mit unendlich

vielen a akzeptiert. Beschreiben Sie L(B1) ∩ L(B′2).

Führen Sie die übliche Durchschnittskonstruktion durch und begründen Sie, warum manF nicht so wählen kann, dass der Automat gerade L(B1) ∩ L(B′

2) akzeptiert.

Wir erweitern zunächst unsere Klasse von Automaten:

Definition 9.3. Ein generalisierter Büchi-Automat (GBA) über Σ ist ein B = (Q,Σ, δ, q0,F),wobei Q, δ und q0 dieselbe Bedeutung haben wie in Definition 9.1, und F = {F1, . . . , Fk} mitFi ⊆ Q die Akzeptanzbedingung ist.

B akzeptiert das Wort a1a2a3 . . ., wenn es einen Ablauf α der Form q0a1−→ q1

a2−→ q3a3−→ . . .

gibt, so dass INF (α) ∩ Fi 6= ∅ für alle i = 1, . . . , k. Daraus ergibt sich wie üblich die SpracheL(B). 2

Wir werden zeigen, dass GBAen dieselben Sprachen akzeptieren wie BAen, dass es aber fürGBAen eine einfache Durchschnittskonstruktion gibt.

Satz 9.4. Zu GBAen B′ und B′′ über Σ gibt es effektiv einen GBA B mit L(B) = L(B′) ∩

L(B′′).

Beweis. Wir definieren wie üblich: Q := Q′×Q′′, q0 := (q′0, q′′0 ) und δ := {((p′, p′′), a, (q′, q′′)) |

(p′, a, q′) ∈ δ′ ∧ (p′′, a, q′′) ∈ δ′′}. F besteht aus den Mengen F ′×Q′′ mit F ′ ∈ F ′ und Q′×F ′′

mit F ′′ ∈ F ′′.

Zu jedem w ∈ L(B′) ∩ L(B′′) gibt es akzeptierende Abläufe α′ von B′ und α′′ von B′′, diesich zu einem Ablauf α von B zusammensetzen lassen. α trifft F ′ ×Q′′ (F ′ ∈ F ′) genau andenselben Stellen wie α′ F ′ trifft – also unendlich oft – and analog für α′′. Also akzeptiert Bw mittels α.

Umgekehrt gibt es zu jedem w ∈ L(B) einen akzeptierenden Ablauf α von B, der sich inAbläufe α′ von B′ und α′′ von B′′ zerlegen lässt. Wiederum trifft α′ F ′ (F ′ ∈ F ′) genauan denselben Stellen wie α F ′ × Q′′ – also unendlich oft – and analog für α′′. Also w ∈

L(B′) ∩ L(B′′). 2

Satz 9.5. Zu jedem GBA B gibt es effektiv einen äquivalenten BA B′ und umgekehrt.

Beweis. Es genügt die erste Aussage zu zeigen, da

Wir legen für jedes Fi ∈ F eine eigene Kopie von B an; in dieser Kopie sind die Zuständevon Fi Endzustände, und die Pfeile von diesen Endzuständen aus führen zur nächsten Schicht:

Q′ := Q × {1, . . . , k}, q′0 := (q0, 1) und δ′ := {((p, i), a, (q, i)) | (p, a, q) ∈ δ ∧ p /∈ Fi} ∪

{((p, i), a, (q, i + 1 mod k)) | (p, a, q) ∈ δ ∧ p ∈ Fi}.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 54: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

9 BÜCHI-AUTOMATEN 52

Schließlich ist F ′ := F1 × {1} ∪ . . . ∪ Fk × {k}.

Ein akzeptierender Ablauf α von B trifft jedes Fi unendlich oft, also F1 zum ersten mal inq1, danach zum ersten mal F2 in q2 etc. Nachdem er Fk in qk getroffen hat, trifft er danach F1

zum ersten mal in qk+1, danach zum ersten mal F2 in qk+2 etc. Der entsprechende Ablauf vonB′ durchläuft also (q1, 1), (q2, 2), . . . , (qk, k), (qk+1, 1), . . . ; er akzeptiert also dasselbe Wort.

Analog durchläuft ein akzeptierender Ablauf α′ von B′ Endzustände (q1, 1) (und verlässtdie erste Kopie), (q2, 2), . . . , (qk, k), (qk+1, 1), . . . ; projizieren wir α′ auf den Ablauf α von B,trifft dieser jedes Fi unendlich oft – z.B. F1 in q1, qk+1, q2k+1, . . . ; α akzeptiert also dasselbeWort.

Bei der Konstruktion kann man sich offensichtlich auf die von q′0 erreichbaren Zuständebeschränken – und das wollen wir auch immer tun. 2

Wir fassen die aufgeführten Ergebnisse zusammen:

Satz 9.6. Die ω-regulären Sprachen sind effektiv abgeschlossen unter Vereinigung, Durch-schnitt und Komplement.

Übung: Fassen Sie B1 und B′2 von eben als GBAen auf; übersetzen Sie den Durchschnitts-

GBA in einen BA gemäß Satz 9.5.

Übung: Um F klein zu halten, wird vorgeschlagen, in der Konstruktion zu Satz 9.5 F :=

F1 × {1} zu setzen; was halten Sie davon?

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 55: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

9 BÜCHI-AUTOMATEN 53

9.2 Model Checking

Wie oben schon beschrieben, wollen wir beim Model Checking prüfen, ob ein System (s)eineSpezifikation erfüllt. Dazu sei das System als BA B formalisiert, die Spezifikation durch eineLTL-Formel ϕ. Jeder Systemablauf soll diese Formel erfüllen.

Die Grundidee ist, ϕ in einen BA Bϕ zu übersetzen, der gerade alle ϕ erfüllenden un-endlichen Wörter akzeptiert, und dann L(B) ⊆ L(Bϕ) zu prüfen. Letzteres ist ja äquivalentzu L(B) ∩ L(Bϕ) = ∅, wobei das Komplement in Σω gebildet wird. Man müsste also dieKomplement-Konstruktion auf Bϕ anwenden, dann die Durchschnitts-Konstruktion mit Bund schließlich für den erhaltenen BA die Leerheit der Sprache prüfen.

Wie oben erwähnt ist die Komplement-Konstruktion aber sehr kompliziert und ineffizient.Es bewährt sich in der Praxis sehr oft, stattdessen einen BA B¬ϕ für ¬ϕ zu konstruieren. Dadie Negation ein Problem ist, drückt man sie nach innen; statt der Formel (oder Teilformel)¬(ϕ ∧ ψ) betrachtet man ¬ϕ ∨ ¬ψ, statt ¬2ϕ . . . . . . etc. Um negierte Until-Formeln zubehandeln, führt man den Release-Operator ein: ϕ R ψ gilt, falls ψ immer gilt oder zumindest(ggf.) bis zum ersten Zeitpunkt (inkl.), zu dem ϕ gilt.

Model Checking: System erfüllt ϕ gdw. L(B) ∩ L(B¬ϕ) = L(B ×B¬ϕ) = ∅

Beispiel 9.7. Das System sei ein Scheduler (Mutex-Lösung, Arbiter), dem mit a bzw. xAnforderungen (requests r1, r2) einer Ressource (=critical section) zugehen, die er dann mitb bzw. y (grant g1, g2) zuteilt; Ressource wird mit c bzw. z (leave l1, l2) wieder freigegeben.Abbildung 16 zeigt das Systemmodell B.

dec

a

bc

x

y z

1 2

Abbildung 16 parallele Kanten haben dieselbe Beschriftung

1. Spezifikation: 2(a→ 3b), d.h. jede Anforderung des ersten Nutzers wird erfüllt

Negation: . . . . . . ; der BA B¬ϕ steht links in Abbildung 17.

Abbildung 18 zeigt B×B¬ϕ als GBA; ein Ablauf, der F2 (Doppelkreise) trifft, bleibt in F2,trifft also nie wieder F1. Damit ist L(B ×B¬ϕ) = ∅, d.h. B erfüllt diese Spezifikation.

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 56: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

9 BÜCHI-AUTOMATEN 54

a

Σ

- {b}Σ

x

Σ

- {y}Σ

b

Σ

- {c}Σ

Σ

y

Abbildung 17

dec

a

bc

x

y z

1 2

dec

2

a

Abbildung 18 parallele Kanten haben dieselbe Beschriftung

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 57: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

9 BÜCHI-AUTOMATEN 55

2. Spezifikation: 2(x→ 3y), d.h. jede Anforderung des zweiten Nutzers wird erfüllt.

Negation: 3(x ∧ 2¬y); der BA B¬ϕ steht in der Mitte in Abbildung 17. Bestimmen SieB ×B¬ϕ als GBA. Erfüllt B diese Spezifikation?

Abbildung 19 parallele Kanten haben dieselbe Beschriftung

3. Spezifikation: gleich die Negation: 3(b ∧ (¬cUy)), d.h. Ressource wird zugeteilt undschließlich nochmals zugeteilt, bevor sie freigegeben wurde. Der BA B¬ϕ steht rechts in Ab-bildung 17. Bestimmen Sie B ×B¬ϕ als GBA. Erfüllt B diese Spezifikation?

Wichtig ist jetzt noch die Frage, ob man immer entscheiden kann, ob die Sprache eines BAleer ist. Oben wurde die Antwort für einen GBA schon angedeutet; für BAen ist die Sachenoch einfacher: Offenbar ist die Sprache nicht-leer, wenn man ein q ∈ F von q0 erreichen kann,das auf einem geschlossenen Kantenzug liegt – oder auch auf einem Kreis (ohne Wiederholungvon Ecken oder Kanten); das ist dasselbe.

Man könnte also zunächst mit DFS (für gerichtete Graphen) die von q0 erreichbaren Zu-stände bestimmen und dann jeden erreichbaren Endzustand auf einen Kreis hin untersuchen;auch letzteres geht mit einer Variation von DFS in linearer Zeit O(n+m), wenn B n Zuständeund m Kanten hat. Insgesamt ergibt sich ein Aufwand von O(n(n+m)).

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 58: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

9 BÜCHI-AUTOMATEN 56

Das Problem lässt sich aber effizienter lösen. Dazu benötigen wir den Begriff der starkenZusammenhangskomponente. Eine Menge C von Ecken eines gerichteten Graphen G ist starkzusammenhängend in G, wenn es für alle u, v ∈ C immer einen Weg von u nach v gibt. Einestarke Zusammenhangskomponente ist dann eine maximale solche Menge C; C heißt trivial,wenn sie nur aus einer Ecke ohne Schlinge besteht.

Starke Zusammenhangskomponenten sind disjunkt: Hätten stark zh. Mengen C und C ′ eineEcke v gemeinsam,

Ein Zustand q liegt in einer nicht-trivialen starken Zhkomponente gdw. q auf einem ge-schlossenen Kantenzug liegt.

Starke Zhkomponenten lassen sich mit einer Variation von DFS in linearer Zeit bestimmen.Um die Sprach-Leerheit zu entscheiden, bestimmen wir also mit DFS die von q0 erreichba-ren starken Zhkomponenten und prüfen, ob eine nicht-triviale von diesen einen Endzustandenthält. Damit haben wir:

Satz 9.8. Die Frage, ob die Sprache eines BA leer ist, lässt sich in linearer Zeit O(n +m)

entscheiden.

Tatsächlich will man diese Frage für sehr große BAen entscheiden. Daher gibt es spezia-lisierte Algorithmen, die vor allem ggf. in kurzer Zeit und mit geringem Speicherbedarf (≤RAM!) ein w ∈ L(B) finden.

9.3 Variationen von Büchi-Automaten

Wenn wir in dem BA in Abbildung 16 alle Zustände zu Endzuständen machen, akzeptiert die-ser BA alle „sinnvollen“ unendlichen Wörter, die die dritte sowie die dazu duale Spezifikationerfüllen. (Sinnvoll heißt, dass a, b, c und x, y, z immer in dieser Reihenfolge auftreten müssen.)Das graphische Grundgerüst stellt also sicher, dass die Sicherheitseigenschaft des wechselsei-tigen Ausschluss (etwas Schlechtes geschieht nie) gewährleistet ist; tatsächlich genügen zurUntersuchung von Sicherheitseigenschaften normale EAen.

Die Endzustände in Abbildung 16 wurden dann so „trickreich“ gewählt, dass der Schedulertatsächlich alle „sinnvollen“ unendlichen Wörter akzeptiert, die zudem die erste Spezifikationerfüllen. (Lebendigkeitseigenschaft – etwas Gutes geschieht schließlich) Es gibt andere Typenvon endlichen Automaten für unendliche Wörter, die hier eine intuitivere Modellierung erlau-ben. Hier wollen wir z.B. die Fairnessanforderung modellieren: Wenn der BA unendlich oftin dec ist, also unendlich oft zwischen der Anforderung des ersten und des zweiten Nutzersentscheidet, so soll er auch unendlich oft für den ersten Nutzer entscheiden, also unendlichoft q1 besuchen. Dies läßt sich direkt in die Akzeptanzbedingung eines sogenannten Streett-Automaten schreiben.

Um Streett- und sog. Muller-Automaten mit Büchi-Automaten vergleichen zu können, wol-len wir aber zunächst zeigen, wie man ω-reguläre Sprachen mit den wie zu Beginn diesesKapitels erweiterten regulären Ausdrücken beschreiben kann.

Definition 9.9. Ist B ein BA (bzw. ein EA) mit Zuständen p, q ∈ Q, dann bezeichnet B(p, q)

den endlichen Automaten, der aus B entsteht, wenn man p als Startzustand und q als einzigenEndzustand wählt. 2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 59: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

9 BÜCHI-AUTOMATEN 57

Satz 9.10. Eine Sprache in Σωist genau dann ω-regulär, wenn sie eine endliche Vereinigungvon Mengen der Form U V ω ist, wobei U und V reguläre Sprachen über Σ sind.

Beweis. „genau dann“: Sei L = L(B) für einen BA B; aufgrund der Büchi-Akzeptanzbedin-gung ist dann L die endliche Vereinigung der Mengen L(B(q0, q))L(B(q, q))ω mit q ∈ F .Offenbar sind die Mengen L(B(q0, q)) und L(B(q, q)) regulär.

„wenn“: Seien reguläre Sprachen U und V über Σ mit zugehörigen buchstabierenden EAenA und A′ gegeben. Zunächst fügen wir A′ einen neuen Startzustand q′′0 und Kanten {(q′′0 , a, q) |

(q′0, a, q) ∈ δ′} hinzu; der sich ergebende EA A′′ hat offenbar auch die Sprache V – außer dassggf.

Nun konstruieren wir aus A′′ einen BA B, indem wir q′′0 zum einzigen Endzustand machenund Kanten {(p, a, q′′0 ) | ∃q ∈ F ′ : (p, a, q) ∈ δ′} hinzufügen. Statt in A′′ ein Wort zuakzeptieren und wieder bei q′′0 zu beginnen, kann man jetzt die neuen Kanten benutzen – undgenau damit FB treffen. B akzeptiert also V ω.

Jetzt bilden wir die disjunkte Vereinigung von A und B, wählen q0 als Startzustand und{q′′0} als Büchi-Akzeptanzbedingung und fügen Kanten {(p, a, q) | p ∈ F ∧ (q′′0 , a, q) ∈ δB}

hinzu. Dieser BA akzeptiert U V ω. Die Behauptung folgt mit Satz 9.6.

2

Also lassen sich ω-reguläre Sprachen genau durch erweiterte reguläre Ausdrücke beschrei-ben, die endliche Summen mit Summanden der Form r sω sind, wobei r und s reguläre Aus-drücke über Σ sind.

Definition 9.11. Ein Muller-Automat (MA) über Σ ist ein B = (Q,Σ, δ, q0,F), wobei Q, δund q0 dieselbe Bedeutung haben wie in Definition 9.1, und F = {F1, . . . , Fk} mit Fi ⊆ Q die(Muller-)Akzeptanzbedingung ist.

B akzeptiert das Wort a1a2a3 . . ., wenn es einen Ablauf α der Form q0a1−→ q1

a2−→ q3a3−→ . . .

gibt, so dass INF (α) ∈ F . Daraus ergibt sich wie üblich die Sprache L(B).

Ein Streett-Automat (StA) über Σ ist ein B = (Q,Σ, δ, q0,F), wobei Q, δ und q0 dieselbeBedeutung haben wie in Definition 9.1, und F = {(E1, F1), . . . , (Ek, Fk)} mit Ei, Fi ⊆ Q die(Streett-)Akzeptanzbedingung ist.

B akzeptiert das Wort a1a2a3 . . ., wenn es einen Ablauf α der Form q0a1−→ q1

a2−→ q3a3−→ . . .

gibt, so dass für i = 1, . . . , k gilt: wenn INF (α) ∩ Ei 6= ∅, dann INF (α) ∩ Fi 6= ∅. Darausergibt sich wie üblich die Sprache L(B). 2

Muller-Automaten eignen sich gut, um die Ausdruckskraft von Automaten für unendlicheWörter zu vergleichen. Für Muller-Automaten wurde das sehr wichtige Ergebnis erzielt, dasses zu jedem Muller-Automaten einen äquivalenten deterministischen gibt.

Streett-Automaten können ω-reguläre Sprachen sehr viel kompakter beschreiben als Büchi-Automaten, und sie eignen sich gut zur Modellierung von Fairness-Bedingungen. Betrachtenwir den Automaten in Abbildung 16 (wobei wir die Markierung der Endzustände ignorieren),so können wir leicht spezifizieren, dass der Automat unendlich oft für den ersten Nutzerentscheidet, falls er unendlich oft in dec ist: wir wählen die Streett-Akzeptanzbedingung

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten

Page 60: Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4 Minimierung endlicher Automaten 15 ... Strukturen mit einer assoziativen Operation mit 1 gibt

9 BÜCHI-AUTOMATEN 58

Um zu spezifizieren, dass der Automat ggf. unendlich oft für den ersten Nutzer und unend-lich oft für den zweiten Nutzer entscheidet (also jede Möglichkeit, die sich hier unendlich oftbietet, auch unendlich oft wählt), verwendet man die Streett-Akzeptanzbedingung

Auch diese beiden neuen Typen von Automaten für unendliche Wörter akzeptieren genaudie ω-regulären Sprachen:

Satz 9.12. Zu jedem Streett-Automaten gibt es effektiv einen äquivalenten Muller-Automatenund umgekehrt. Zu jedem Muller-Automaten gibt es effektiv einen äquivalenten Büchi-Auto-maten und umgekehrt.

Beweis. Ein BA ist ein spezieller StA: wähle die Streett-Akzeptanzbedingung

Ein StA kann als MA gesehen werden: wähle als Muller-Akzeptanzbedingung alle MengenF , die die Streett-Akzeptanzbedingung erfüllen, d.h. für die für i = 1, . . . , k gilt: wenn F∩Ei 6=

∅, dann F ∩ Fi 6= ∅.

Sei nun B ein MA. Um zu zeigen, dass L(B) ω-regulär ist, verwenden wir Satz 9.10, dessenBeweis ja konstruktiv war. Also zeigen wir, dass die wegen Fi ∈ F akzeptierten Wörter eineSprache der Form U V ω bilden. Dazu wählen wir eine Numerierung der Zustände in Fi, d.h.Fi = {q1, . . . , ql}; C sei der EA, der entsteht, wenn man B auf die Zustände in Fi einschränktund z.B. q1 als Start- und einzigen Endzustand wählt.

Jeder wegen Fi akzeptierende Ablauf von B hat folgende Form: er hat ein Suffix, in demer nur Zustände von Fi besucht; in diesem Suffix erreicht er q1, dann q2 etc. und schließlichql, von wo er wieder q1, dann q2 erreicht usw. Die auf diese Weise akzeptierten Wörter bildenalso gerade die Sprache L(B(q0, q1))

(L(C(q1, q2)) . . . L(C(ql−1, ql))L(C(ql, q1))

)ω. 2

Prof. Dr. W. Vogler Universität Augsburg Endliche Automaten


Top Related