Home > Documents > Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4...

Endliche Automaten · 2 Endliche Automaten 5 3 Anwendung: Diophantische Gleichungen 11 4...

Date post: 20-May-2020
Category:
Author: others
View: 1 times
Download: 0 times
Share this document with a friend
Embed Size (px)
of 60 /60
Endliche Automaten Prof. Dr. W. Vogler Sommersemester 2011 1
Transcript
  • Endliche Automaten

    Prof. Dr. W. Vogler

    Sommersemester 2011

    1

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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 Bhaben; 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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 lund 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

  • 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

  • 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 A2fü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 akzeptiertalso 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

  • 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

  • 4 MINIMIERUNG ENDLICHER AUTOMATEN 16

    Definition 4.2. Zur Sprache L ⊆ Σ∗ definieren wir den minimalen Automaten AL von Ldurch: 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

  • 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 Rvon 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 List 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)

  • 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

  • 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≡ qawg. 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

  • 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, . . . , kgilt:

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

  • 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 dies

    ein Widerspruch zur Zulässigkeit der Partition vor der Aufspaltung von Bj.

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

  • 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 B

    alt

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

    ′i ∪B

    ′l.

    II) Andernfalls gibt es L gemäß Behauptung am Beginn des Durchlaufs, die Partition iststabil bzgl. B := Bm ∪ Bm1 ∪ · · · ∪ Bmn und c zu Beginn und bzgl. B und c auch amEnde des Durchlaufs:

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

    Wird ein Baltmr gespalten in B′mr und B

    ′l, so sind am Ende mr, l ∈ Liste(c) (auch für

    i = mr), und wir fügen l zu L hinzu. Wird Baltm selbst gespalten in B′m und B

    ′l, so ist

    am 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. (Baltm1 , a) und (B, a) mitB = Bm∪B

    alt

    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

  • 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

  • 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

  • 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 A1als Implementierung der Spezifikation A2 ansehen können.

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

  • 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

  • 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 einen

    wα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

  • 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

  • 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 ∈ Lmit 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

  • 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 nnicht, eventuell ist n sehr groß, abhängig von n dürfen wir jetzt aber ein beliebiges z ∈ Lwä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

  • 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

  • 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 1100 10 0001 0010 00

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

  • 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

  • 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

  • 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, x2und 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

  • 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

  • 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 Aund 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

  • 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 Ggesetzt; 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

  • 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

  • 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 nachDefinition β((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

  • 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

  • 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 Lregulä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 ∪̇ {qR0 } ,Σ, δR ∪ {(qR0 , λ, q) | q ∈ F} , q

    R

    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

  • 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

  • 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−→ q1

    u2/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 �


Recommended