Grundbegri�e der InformatikKapitel 18: Endliche Automaten
Thomas Worsch
KIT, Institut für Theoretische Informatik
Wintersemester 2015/2016
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 1 / 41
Überblick
Erstes Beispiel: ein Getränkeautomat
Mealy-Automaten
Moore-Automaten
Spezialfall: endliche Akzeptoren
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 2 / 41
Wo sind wir?
Erstes Beispiel: ein Getränkeautomat
Mealy-Automaten
Moore-Automaten
Spezialfall: endliche Akzeptoren
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 3 / 41
Ein primitiver Getränkeautomat
Geld-Einwurf
Geld-Rückgabe Ware
Sprudel
rein zitro
OK C
Geldnur 1-Euro-Stückeerster Euro gespeichertweitere Münzen sofort zurück
vier Tastenrein Mineralwasser (1 Euro)zitro Zitronensprudel (1 Euro)
letzter Wunsch gemerkt
C ggf. Geld zurück, ggf.Getränkewunsch gelöscht
OK Geld und Getränkewunsch ;Getränk
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 4 / 41
Getränkeautomat: Zuständezwischen den Eingaben müssenNachrichten gespeichert werden
und zwarschon Geld eingeworfen?schon Getränk ausgewählt?wenn ja: welches?
Formalisierung: Paare (x ,y)x ∈ {0, 1}: schon eingeworfener Geldbetragy ∈ {-,R,Z}: GetränkewahlZustandsmenge Z = {0, 1} × {-,R,Z}
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 5 / 41
Getränkeautomat: EingabenEingaben führen zu Zustandsänderungen.
Eingaben hier:Einwurf eines EurosDrücken einer der vier Tasten
Modellierung der Eingaben: Symbole 1, R, Z, C und O
Eingabealphabet X = {1,R,Z,C,O}
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 6 / 41
Getränkeautomat: Zustandsübergänge (1)Zustandsübergang hängt ab von
aktuellem Zustand z ∈ Z undaktuellem Eingabesymbol x ∈ Xz und x legen eindeutig den neuen Zustand fest
also immer und eindeutigjedenfalls im ersten Semester
Zustandsüberführungsfunktion f : Z × X → Zo� graphisch spezifiziert
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 7 / 41
Getränkeautomat: Zustandsübergänge (2a)
(0,-) (0,R) (0,Z)
(1,-) (1,R) (1,Z)
1 1 1
R
ZZ
R
R
Z Z
R
1 1 1
R
R
Z
Z
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 8 / 41
Getränkeautomat: Zustandsübergänge (2b)
(0,-) (0,R) (0,Z)
(1,-) (1,R) (1,Z)
O,C O,C
O,C O O
O
CC
C
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 9 / 41
Getränkeautomat: Zustandsübergänge (2c)
(0,-) (0,R) (0,Z)
(1,-) (1,R) (1,Z)
O,C
R,O
Z,O
1,O
1,R
1,Z
1 1 1
C
R
C
Z
RZ
C
R
O,C
Z
R
Z
O,C
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 10 / 41
Getränkeautomat: Ausgaben (1)zweiter wesentlicher Aspekt jedes Automaten: Ausgaben
hier: Rückgeld, gewählte Flasche
Ausgabealphabet Y = {1,R,Z}Formalisierung der Ausgaben
abhängig von aktuellem Zustand z ∈ Z und aktuellemEingabesymbol x ∈ Xz und x legen eindeutig die Ausgabe fest.
also immer und eindeutigjedenfalls im ersten Semesterim allgemeinen Wörter über Y
Formalisierung: Ausgabefunktion д : Z × X → Y ∗Funktionswert ε : „keine Ausgabe“
д im Zustandsübergangsdiagramm: x |д(z,x )
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 11 / 41
Getränkeautomat: Ausgaben (2)
(0,-) (0,R) (0,Z)
(1,-) (1,R) (1,Z)
O|ε ,C|ε
R|ε ,O|ε
Z|ε ,O|ε
1|1,O|ε1|1,R|ε
1|1,Z|ε
1|ε 1|ε 1|ε
C|1
R|ε
C|ε
Z|ε
R|εZ|ε
C|ε
R|ε
O|R,C|1
Z|ε
R|ε
Z|ε
O|Z,C|1
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 12 / 41
Was ist wichtigDas sollten Sie mitnehmen:
alles endlichalles endlich beschreibbarim Beispiel Getränkeautomat:
aktueller Zustand und aktuelle Eingabelegen eindeutig fest:nächsten ZustandAusgabe
Das sollten Sie üben:Zustandsdiagramm lesen
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 13 / 41
Wo sind wir?
Erstes Beispiel: ein Getränkeautomat
Mealy-Automaten
Moore-Automaten
Spezialfall: endliche Akzeptoren
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 14 / 41
Mealy-Automatenformal
eine endliche Zustandsmenge Z ,einen Anfangszustand z0 ∈ Z ,ein Eingabealphabet X ,eine Zustandsüberführungsfunktion f : Z × X → Z ,ein Ausgabealphabet Y ,eine Ausgabefunktion д : Z × X → Y ∗
Darstellung als Graph:Knoten: Zustände
Kanten: z f (z,x )x |д(z,x )
Anfangszustand: kleiner Pfeil z
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 15 / 41
Verallgemeinerte Zustandsübergangsfunktionen (1)nach Eingabe eines ganzen Wortes w ∈ X ∗:
erreichter Zustand?alle durchlaufenen Zustände?
definiere passende Funktionen f∗ und f∗∗
f∗ : Z × X ∗ → Z : f∗ (z, ε ) = z∀w ∈ X ∗ : ∀x ∈ X : f∗ (z,wx ) = f ( f∗ (z,w ),x )
alternativ f̄∗ (z, ε ) = z
∀w ∈ X ∗ : ∀x ∈ X : f̄∗ (z,xw ) = f̄∗ ( f (z,x ),w )
Definitionen äquivalent: f∗ = f̄∗
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 16 / 41
Verallgemeinerte Zustandsübergangsfunktionen (1)nach Eingabe eines ganzen Wortes w ∈ X ∗:
erreichter Zustand?alle durchlaufenen Zustände?
definiere passende Funktionen f∗ und f∗∗
f∗ : Z × X ∗ → Z : f∗ (z, ε ) = z∀w ∈ X ∗ : ∀x ∈ X : f∗ (z,wx ) = f ( f∗ (z,w ),x )
alternativ f̄∗ (z, ε ) = z
∀w ∈ X ∗ : ∀x ∈ X : f̄∗ (z,xw ) = f̄∗ ( f (z,x ),w )
Definitionen äquivalent: f∗ = f̄∗
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 16 / 41
Verallgemeinerte Zustandsübergangsfunktionen (1)nach Eingabe eines ganzen Wortes w ∈ X ∗:
erreichter Zustand?alle durchlaufenen Zustände?
definiere passende Funktionen f∗ und f∗∗
f∗ : Z × X ∗ → Z : f∗ (z, ε ) = z∀w ∈ X ∗ : ∀x ∈ X : f∗ (z,wx ) = f ( f∗ (z,w ),x )
alternativ f̄∗ (z, ε ) = z
∀w ∈ X ∗ : ∀x ∈ X : f̄∗ (z,xw ) = f̄∗ ( f (z,x ),w )
Definitionen äquivalent: f∗ = f̄∗
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 16 / 41
Verallgemeinerte Zustandsübergangsfunktionen (2)alle durchlaufenen Zustände:
f∗∗ : Z × X ∗ → Z ∗
f∗∗ (z, ε ) = z
∀w ∈ X ∗ : ∀x ∈ X : f∗∗ (z,wx ) = f∗∗ (z,w ) · f ( f∗ (z,w ),x )
auch hier wieder eine alternative Definitionsmöglichkeit
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 17 / 41
Bespiel Getränkeautomat
(0,-) (0,R) (0,Z)
(1,-) (1,R) (1,Z)
O|ε ,C|ε
R|ε ,O|ε
Z|ε ,O|ε
1|1,O|ε1|1,R|ε
1|1,Z|ε
1|ε 1|ε 1|ε
C|1
R|ε
C|ε
Z|ε
R|εZ|ε
C|ε
R|ε
O|R,C|1
Z|ε
R|ε
Z|ε
O|Z,C|1
f∗∗ ( (0,-),R1RZO) = (0,-) (0,R) (1,R) (1,R) (1,Z) (0,-)GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 18 / 41
Verallgemeinerte Ausgabefunktionen
für „die letzte“ Ausgabe: д∗ : Z × X ∗ → Y ∗
д∗ (z, ε ) = ε
д∗ (z,wx ) = д( f∗ (z,w ),x )
Für „alle Ausgaben konkateniert“: д∗∗ : Z × X ∗ → Y ∗:
д∗∗ (z, ε ) = ε
д∗∗ (z,wx ) = д∗∗ (z,w ) · д∗ (z,wx )
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 19 / 41
Bespiel Getränkeautomaten
(0,-) (0,R) (0,Z)
(1,-) (1,R) (1,Z)
O|ε ,C|ε
R|ε ,O|ε
Z|ε ,O|ε
1|1,O|ε1|1,R|ε
1|1,Z|ε
1|ε 1|ε 1|ε
C|1
R|ε
C|ε
Z|ε
R|εZ|ε
C|ε
R|ε
O|R,C|1
Z|ε
R|ε
Z|ε
O|Z,C|1
д∗∗ ( (0,-),R1RZO) = εεεεZ = ZGBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 20 / 41
Was ist wichtigDas sollten Sie mitnehmen:
„o�izielle“ Definition von Mealy-Automat:Zz0 ∈ ZXf : Z × X → ZYд : Z × X → Y ∗ Ausgabe hängt von der Eingabe ab
Das sollten Sie üben:zu vorgegebenem „Verhalten“ Beispielautomaten konstruierenvon vorgebenenen Automaten ihr Verhalten verstehen
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 21 / 41
Wo sind wir?
Erstes Beispiel: ein Getränkeautomat
Mealy-Automaten
Moore-Automaten
Spezialfall: endliche Akzeptoren
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 22 / 41
Moore-AutomatAusgabe «im Zustand» sta� beim Zustandsübergang
genauer beim «Erreichen des Zustandes»
Definitionendliche Zustandsmenge Z ,Anfangszustand z0 ∈ Z ,Eingabealphabet X ,Zustandsüberführungsfunktion f : Z × X → Z ,Ausgabealphabet Y ,Ausgabefunktion h : Z → Y ∗
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 23 / 41
Moore-Automat: Beispiel aus tikz-Dokumentationgraphische Darstellung analog zu Mealy-Automaten,nur die Ausgaben in den Zuständen:
qε |0
qa |0
qb |0
qf |1 qr |0
a
b
b
a
a
b
a,b a,b
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 24 / 41
Verallgemeinerte Zustandsübergangsfunktionen
qε |0
qa |0
qb |0
qf |1 qr |0
a
b
b
a
a
b
a,b a,b
Definition von f∗, f∗∗wie bei Mealy-Automaten
Beispiele:f∗ (qε ,aaaba) = qrf∗∗ (qε ,aaaba) =qεqaqaqaqf qr
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 25 / 41
Verallgemeinerte Ausgabefunktionen д∗ und д∗∗„letzte Ausgabe“ д∗ = h ◦ f∗:
∀(z,w ) ∈ Z × X ∗ : д∗ (z,w ) = h( f∗ (z,w ))
„alle Ausgaben“: д∗∗ = h∗∗ ◦ f∗∗∀(z,w ) ∈ Z × X ∗ : д∗∗ (z,w ) = h∗∗ ( f∗∗ (z,w ))
Erinnerung: h∗∗ der durch h induzierte Homomorphismus
Beispielf∗∗ (qε ,aaaba) = qεqaqaqaqf qr
alsoд∗ (qε ,aaaba) = h( f∗ (qε ,aaaba)) = h(qr ) = 0
д∗∗ (qε ,aaaba) = h∗∗ ( f∗∗ (qε ,aaaba)) = h∗∗ (qεqaqaqaqf qr )= h(qε )h(qa)h(qa)h(qa)h(qf )h(qr ) = 000010
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 26 / 41
Was ist wichtigDas sollten Sie mitnehmen:
„o�izielle“ Definition von Moore-Automat:Zz0 ∈ ZXf : Z × X → ZYh : Z → Y ∗ Ausgabe hängt nicht von der Eingabe ab
Das sollten Sie üben:vorgegebenes Verhalten mit Moore-Automat realisierenvorgebenenen Moore-Automaten analysieren
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 27 / 41
Wo sind wir?
Erstes Beispiel: ein Getränkeautomat
Mealy-Automaten
Moore-Automaten
Spezialfall: endliche Akzeptoren
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 28 / 41
Endliche Akzeptoren —ein wichtiger Sonderfall von Moore-Automaten
immer genau ein Bit AusgabeY = {0,1} und∀z : h(z) ∈ Y
Interpretation der Ausgabe:Eingabe war „gut“ oder „schlecht“ bzw.„syntaktisch korrekt“ oder „syntaktisch falsch“(für eine gerade interessierende Syntax)
bequemere Formalisierung:Spezifikation der Menge F : akzeptierende ZuständeF = {z | h(z) = 1}die anderen heißen ablehnende Zustände
in graphischen Darstellungen
akzeptierende Zustände mit Doppelkringel: z
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 29 / 41
Endlicher Akzeptor: Beispiel
qε |0
qa |0
qb |0
qf |1 qr |0
a
b
b
a
a
b
a,b a,b
der Moore-Automatvon eben
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 30 / 41
Endlicher Akzeptor: Beispiel
qε
qa
qb
qf qr
a
b
b
a
a
b
a,b a,b
der Moore-Automatvon eben
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 30 / 41
Akzeptierte und abgelehnte WörterWort w ∈ X ∗ wird akzeptiert, falls f∗ (z0,w ) ∈ F .
Wort w ∈ X ∗ wird abgelehnt, falls f∗ (z0,w ) < F .
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 31 / 41
Beispiel
qε
qa
qb
qf qr
a
b
b
a
a
b
a,b a,b
aaaba abgelehnt:f∗ (z0,aaaba) = qr < F
aaab akzeptiert:f∗ (z0,aaab) = qf ∈ F .
allgemein akzeptiert:Wörter der Form akbWörter der Form bkanicht anderes
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 32 / 41
Beispiel
qε
qa
qb
qf qr
a
b
b
a
a
b
a,b a,b
aaaba abgelehnt:f∗ (z0,aaaba) = qr < F
aaab akzeptiert:f∗ (z0,aaab) = qf ∈ F .
allgemein akzeptiert:Wörter der Form akbWörter der Form bkanicht anderes
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 32 / 41
Erkannte formale SpracheDie von einem Akzeptor A = (Z , z0,X , f , F ) akzeptierte odererkannte formale Sprache ist
L(A) = {w ∈ X ∗ | f∗ (z0,w ) ∈ F }
Das ist ganz einfache „Syntaxanalyse“.
in unserem Beispiel:
L(A) = {a}+{b} ∪ {b}+{a}
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 33 / 41
Beispiel 2 einer erkennbaren Spracheformale Sprache L aller Wörter w ∈ {a,b}∗ mit:
in w kommt mindestens ein b vor undvor dem letzten b steht ein a
Behauptung: Es gibt EA, der L erkennt.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 41
Beispiel 2 einer erkennbaren Spracheformale Sprache L aller Wörter w ∈ {a,b}∗ mit:
in w kommt mindestens ein b vor undvor dem letzten b steht ein a
Behauptung: Es gibt EA, der L erkennt.
z0 z1
z
a
b
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 41
Beispiel 2 einer erkennbaren Spracheformale Sprache L aller Wörter w ∈ {a,b}∗ mit:
in w kommt mindestens ein b vor undvor dem letzten b steht ein a
Behauptung: Es gibt EA, der L erkennt.
z0 z1
z
a
b
a
b
b
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 41
Beispiel 2 einer erkennbaren Spracheformale Sprache L aller Wörter w ∈ {a,b}∗ mit:
in w kommt mindestens ein b vor undvor dem letzten b steht ein a
Behauptung: Es gibt EA, der L erkennt.
z0 z1
z
a
b
a
b
b
a
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 41
Beispiel 2 einer erkennbaren Spracheformale Sprache L aller Wörter w ∈ {a,b}∗ mit:
in w kommt mindestens ein b vor undvor dem letzten b steht ein a
Behauptung: Es gibt EA, der L erkennt.
z0 z1a a
b
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 41
Beispiel 2 einer erkennbaren Spracheformale Sprache L aller Wörter w ∈ {a,b}∗ mit:
in w kommt mindestens ein b vor undvor dem letzten b steht ein a
Behauptung: Es gibt EA, der L erkennt.
z0 z1
z2
a a
b
b
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 41
Beispiel 2 einer erkennbaren Spracheformale Sprache L aller Wörter w ∈ {a,b}∗ mit:
in w kommt mindestens ein b vor undvor dem letzten b steht ein a
Behauptung: Es gibt EA, der L erkennt.
z0 z1
z2
a a
b
bb
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 41
Beispiel 2 einer erkennbaren Spracheformale Sprache L aller Wörter w ∈ {a,b}∗ mit:
in w kommt mindestens ein b vor undvor dem letzten b steht ein a
Behauptung: Es gibt EA, der L erkennt.
z0 z1
z2 z3
a a
b
bb
a
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 41
Beispiel 2 einer erkennbaren Spracheformale Sprache L aller Wörter w ∈ {a,b}∗ mit:
in w kommt mindestens ein b vor undvor dem letzten b steht ein a
Behauptung: Es gibt EA, der L erkennt.
z0 z1
z2 z3
a a
b
bb
a
ab
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 41
Beispiel 3 einer erkennbaren SpracheAufgabe aus dem Informatiker-Alltag
gegeben: Textdatei mit vielen Zeilengesucht: die Zeilen, in denen ein gewisses Wortm vorkommt
mit anderen Wortengegeben: Zeichenke�e w und Textmustermgesucht: Algorithmus, der feststellt, obm in w vorkommtdas geht mit einem endlichen Akzeptor
Beispiel:Eingabealphabet X = {a,b}Textmusterm = ababbZiel: endlicher Akzeptor A mitL(A) = {w1ababbw2 | w1,w2 ∈ {a,b}∗}
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 35 / 41
Beispiel 3 einer erkennbaren SpracheAufgabe aus dem Informatiker-Alltag
gegeben: Textdatei mit vielen Zeilengesucht: die Zeilen, in denen ein gewisses Wortm vorkommt
mit anderen Wortengegeben: Zeichenke�e w und Textmustermgesucht: Algorithmus, der feststellt, obm in w vorkommtdas geht mit einem endlichen Akzeptor
Beispiel:Eingabealphabet X = {a,b}Textmusterm = ababbZiel: endlicher Akzeptor A mitL(A) = {w1ababbw2 | w1,w2 ∈ {a,b}∗}
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 35 / 41
Beispiel 3 einer erkennbaren SpracheAufgabe aus dem Informatiker-Alltag
gegeben: Textdatei mit vielen Zeilengesucht: die Zeilen, in denen ein gewisses Wortm vorkommt
mit anderen Wortengegeben: Zeichenke�e w und Textmustermgesucht: Algorithmus, der feststellt, obm in w vorkommtdas geht mit einem endlichen Akzeptor
Beispiel:Eingabealphabet X = {a,b}Textmusterm = ababbZiel: endlicher Akzeptor A mitL(A) = {w1ababbw2 | w1,w2 ∈ {a,b}∗}
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 35 / 41
Beispiel 3 — Entwicklung einer Lösung
z0 z1 z2 z3 z4 z5a b a b b
a,b
es fehlen noch diverse Übergängewas ist z. B. mit:
bbbababbaaaababbabbababbabaababbabababb
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 36 / 41
Beispiel 3 — Entwicklung einer Lösung
z0 z1 z2 z3 z4 z5a
b
b a b b
a,b
es fehlen noch diverse Übergängewas ist z. B. mit:
bbbababbaaaababbabbababbabaababbabababb
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 36 / 41
Beispiel 3 — Entwicklung einer Lösung
z0 z1 z2 z3 z4 z5a
b
b
a
a b b
a,b
es fehlen noch diverse Übergängewas ist z. B. mit:
bbbababbaaaababbabbababbabaababbabababb
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 36 / 41
Beispiel 3 — Entwicklung einer Lösung
z0 z1 z2 z3 z4 z5a
b
b
a
a
b
b b
a,b
es fehlen noch diverse Übergängewas ist z. B. mit:
bbbababbaaaababbabbababbabaababbabababb
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 36 / 41
Beispiel 3 — Entwicklung einer Lösung
z0 z1 z2 z3 z4 z5a
b
b
a
a
b
b
a
b
a,b
es fehlen noch diverse Übergängewas ist z. B. mit:
bbbababbaaaababbabbababbabaababbabababb
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 36 / 41
Beispiel 3 — Entwicklung einer Lösung
z0 z1 z2 z3 z4 z5a
b
b
a
a
b
b
a
b
a
a,b
es fehlen noch diverse Übergängewas ist z. B. mit:
bbbababbaaaababbabbababbabaababbabababb
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 36 / 41
Beispiel 3 — Entwicklung einer Lösung
z0 z1 z2 z3 z4 z5a
b
b
a
a
b
b
a
b
a
a,b
es fehlen noch diverse Übergängewas ist z. B. mit:
bbbababbaaaababbabbababbabaababbabababb
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 36 / 41
Beispiel einer nicht erkennbaren SpracheBehauptung: Die formale Sprache
L = {akbk | k ∈ N0}
kann von keinem endlichen Akzeptor erkannt werden.
Beweis„schwieriger“ als einen Akzeptor hinzumalen:
betrachte „beliebigen“ Akzeptor A und zeige L(A) , LWas bedeutet L(A) , L?
L * L(A) oder L(A) * L«zielführende» Fallunterscheidung:
1. Fall: L * L(A)o�ensichtlich L(A) , L
2. Fall: L ⊆ L(A)zeige L(A) * L, d. h. ein „falsches“ Wort wird akzeptiert
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 37 / 41
Beispiel einer nicht erkennbaren SpracheBehauptung: Die formale Sprache
L = {akbk | k ∈ N0}
kann von keinem endlichen Akzeptor erkannt werden.
Beweis„schwieriger“ als einen Akzeptor hinzumalen:
betrachte „beliebigen“ Akzeptor A und zeige L(A) , LWas bedeutet L(A) , L?
L * L(A) oder L(A) * L«zielführende» Fallunterscheidung:
1. Fall: L * L(A)o�ensichtlich L(A) , L
2. Fall: L ⊆ L(A)zeige L(A) * L, d. h. ein „falsches“ Wort wird akzeptiert
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 37 / 41
Beispiel einer nicht erkennbaren Sprache (2)
L = {akbk | k ∈ N0}
A = (Z , . . . ) beliebig mitm = |Z |
zeige: wenn L ⊆ L(A), dann L(A) * L
betrachte w = ambm
f∗∗ (z0,am ) besteht ausm + 1 Zuständen:z0z1 = f (z0,a)z2 = f (z1,a)...zm = f (zm−1,a)
ein Zustand muss doppelt vorkommen:A läu� in einer Schleife
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 38 / 41
Beispiel einer nicht erkennbaren Sprache (2)
L = {akbk | k ∈ N0}
A = (Z , . . . ) beliebig mitm = |Z |
zeige: wenn L ⊆ L(A), dann L(A) * L
betrachte w = ambm
f∗∗ (z0,am ) besteht ausm + 1 Zuständen:z0z1 = f (z0,a)z2 = f (z1,a)...zm = f (zm−1,a)
ein Zustand muss doppelt vorkommen:A läu� in einer Schleife
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 38 / 41
Beispiel einer nicht erkennbaren Sprache (2)
L = {akbk | k ∈ N0}
A = (Z , . . . ) beliebig mitm = |Z |
zeige: wenn L ⊆ L(A), dann L(A) * L
betrachte w = ambm
f∗∗ (z0,am ) besteht ausm + 1 Zuständen:z0z1 = f (z0,a)z2 = f (z1,a)...zm = f (zm−1,a)
ein Zustand muss doppelt vorkommen:A läu� in einer Schleife
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 38 / 41
Beispiel einer nicht erkennbaren Sprache (3)seien i ≥ 0 und ` ≥ 1 Zahlen mitzi = zi+` , also f∗ (z0,ai ) = f∗ (z0,ai+` )
A «kann irgendwann nicht mehr unterscheiden»,ob ` a mehr oder weniger in der Eingabe
betrachte: w ′ = am−`bm < L
f∗ (z0,w′) = f∗ (z0,am−`bm )= f∗ ( f∗ (z0,ai ),am−`−ibm )= f∗ ( f∗ (z0,ai+` ),am−`−ibm )= f∗ (z0,ambm ) ∈ F
w ′ ∈ L(A) aber w ′ < L
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 39 / 41
Beispiel einer nicht erkennbaren Sprache (3)seien i ≥ 0 und ` ≥ 1 Zahlen mitzi = zi+` , also f∗ (z0,ai ) = f∗ (z0,ai+` )
A «kann irgendwann nicht mehr unterscheiden»,ob ` a mehr oder weniger in der Eingabe
betrachte: w ′ = am−`bm < L
f∗ (z0,w′) = f∗ (z0,am−`bm )= f∗ ( f∗ (z0,ai ),am−`−ibm )= f∗ ( f∗ (z0,ai+` ),am−`−ibm )= f∗ (z0,ambm ) ∈ F
w ′ ∈ L(A) aber w ′ < LGBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 39 / 41
Was ist wichtigDas sollten Sie mitnehmen:
„o�izielle“ Definition endlicher Akzeptoren:Zz0 ∈ ZXf : Z × X → ZF ⊆ Z
Wenn ein «sehr langes» «uniformes» Wort akzeptiert wird,dann läu� der Automat in einer Schleife,die beliebig o� durchlaufen werden kann ohne Akzeptanz zuändern
Das sollten Sie üben:gegeben L: konstruiere A mit L(A) = Lgegeben A: bestimme L(A)
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 40 / 41
ZusammenfassungMealy-Automaten
Moore-Automatentaucht im Zusammenhang mit diversen Protokollen z. B. inBetriebssystemen und bei Kommunikationssystemen auf
insbesonderen Akzeptorenprimitive Syntaxanalyseo� nützlich, z. B.
bei Compilerbau-WerkzeugenSuche nach Text-Vorkommen, etc.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 41 / 41
Erstes Beispiel: ein GetränkeautomatMealy-AutomatenMoore-AutomatenSpezialfall: endliche Akzeptoren
