close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Endliche Automaten

EinbettenHerunterladen
Endliche Automaten
Endliche Automaten
1 / 38
Endliche Automaten
Endliche Automaten erlauben eine Beschreibung von Handlungsabläufen:
Wie ändert sich ein Systemzustand in Abhängigkeit von
veränderten Umgebungsbedingungen?
Vielfältiges Einsatzgebiet, nämlich:
- in der Definition der regulären Sprachen
also der Menge aller Folgen von Ereignissen,
die von einem Startzustand in einen gewünschten Zustand führen,
- in der Entwicklung digitaler Schaltungen
- in der Softwaretechnik (z. B. in der Modellierung des
Applikationsverhaltens)
- in der Compilierung: Lexikalische Analyse
- im Algorithmenentwurf für String Probleme
- in der Abstraktion tatsächlicher Automaten (wie Bank- und
Getränkeautomaten, Fahrstühle etc.)
Endliche Automaten
2 / 38
Das Problem der Flußüberquerung
"Startzustand"
MWZ K
MZ
MZ
W K
M Z
M
M
MW K
Z
MW
K
MZ
MZ K
MK
MK
MW
MW Z
W
MZ
MZ
W
M WZ
MZ
K
MW
MK
MK
MW
Z
MW K
M
M
M
Z
W K
MZ
"akzeptierender Zustand"
M K Z
MZ
MWKZ
Dieser endliche Automat „akzeptiert“ genau diejenigen Folgen von einzelnen
Flussüberquerungen, die vom Startzustand in den akzeptierenden Zustand führen.
Endliche Automaten
Beispiele
3 / 38
Ein Kaffeeautomat
Der Automat erlaubt das Einwerfen von 1 oder 2 e-Münzen, sowie das Drücken
der Tasten „Geldrückgabe“ und „Kaffee kaufen“.
(Der Kaffee kostet 2 e.)
Und hier ist die Spezifikation des Automaten:
Einwerfen einer
1 e-Münze
Grundzustand
Zustand 1
Drücken der
„Geld Rückgabe“-Taste
Einwerfen einer
2 e-Münze
Einwerfen einer
1 e-Münze
Zustand 2
Drücken der
„Geld Rückgabe“-Taste
Drücken der Taste
„Kaffee kaufen“
Dieser Automat „akzeptiert“ genau diejenigen Folgen von Bedienoperationen, die vom Grundzustand aus wieder in den Grundzustand führen.
Endliche Automaten
Beispiele
4 / 38
Freischaltung eines Fernsehers
(1/2)
Um die Kindersicherung des Fernsehers über die Fernbedienung freizuschalten, muss
ein dreistelliger Code korrekt eingegeben werden. Dabei sind die folgenden Tasten
relevant:
- Die Tasten 0, . . . , 9,
- die Taste CODE sowie
- die Taste BACK.
Die Taste CODE muss vor Eingabe des Codes gedrückt werden.
Wird CODE während der Codeeingabe nochmals gedrückt, so wird die Eingabe neu
begonnen.
Wird BACK gedrückt, so wird die zuletzt eingegebene Zahl zurückgenommen.
Der Code zum Entsperren ist 999.
Endliche Automaten
Beispiele
5 / 38
Freischaltung eines Fernsehers
BACK
(2/2)
CODE
CODE
9
ready
9
BACK
CODE
CODE
0,...,8
9
BACK
0,...,8
BACK
CODE
CODE
99
9
ON
BACK
0,...,8
x
CODE
9x
0,...,9
0,...,9
BACK
xx
0,...,9
OFF
0,...,9
BACK
Der Automat „akzeptiert“ alle Folgen von Bedienoperationen,
die vom Zustand „ready“ in den Zustand „ON“ führen.
Endliche Automaten
Beispiele
6 / 38
Was ist ein endlicher Automat?
Ein deterministischer endlicher Automat (engl. deterministic finite automaton,
kurz DFA)
A = (Σ, Q, δ, q0 , F )
besteht aus:
einer endlichen Menge Σ, dem Eingabealphabet,
einer endlichen Menge Q, der Zustandsmenge (die Elemente aus Q werden
Zustände genannt),
einer partiellen Funktion δ von Q × Σ nach Q,
der Übergangsfunktion (oder Überführungsfunktion),
einem Zustand q0 ∈ Q, dem Startzustand,
sowie einer Menge F ⊆ Q von Endzuständen bzw. akzeptierenden
Zuständen. (Der Buchstabe F steht für „final states“, also „Endzustände“).
Endliche Automaten
DFAs: Die formale Definition
7 / 38
Der Kaffeautomat als DFA A = (Σ, Q, δ, q0 , F )
Σ = {Einwerfen einer 1 e-Münze, Einwerfen einer 2 e-Münze,
Drücken der „Geld Rückgabe“-Taste,
Drücken der Taste „Kaffee kaufen“}
Q = {Grundzustand, Zustand 1, Zustand 2}
q0 = Grundzustand
F = {Grundzustand}
die Funktion δ : Q × Σ → Q ist partiell und besitzt die „Automatentabelle“
δ(Grundzustand, Einwerfen einer 1 e-Münze)
= Zustand 1,
δ(Grundzustand, Einwerfen einer 2 e-Münze)
= Zustand 2,
δ(Zustand 1, Einwerfen einer 1 e-Münze)
= Zustand 2,
δ(Zustand 1, Drücken der „Geld Rückgabe“-Taste)
= Grundzustand,
δ(Zustand 2, Drücken der „Geld Rückgabe“-Taste)
= Grundzustand,
δ(Zustand 2, Drücken der Taste „Kaffee kaufen“)
= Grundzustand.
Endliche Automaten
DFAs: Die formale Definition
8 / 38
Der Automatengraph,
die grafische Darstellung eines DFA
Endliche Automaten
Der Automatengraph
9 / 38
Grafische Darstellung: Der Automatengraph
A = (Σ, Q, δ, q0 , F ) sei ein DFA.
Für jeden Zustand q ∈ Q gibt es einen durch
q
dargestellten Knoten.
Der Startzustand q0 wird durch einen in ihn hinein führenden Pfeil markiert,
d.h.:
q0
Jeder akzeptierende Zustand q ∈ F wird durch eine doppelte Umrandung
markiert, d.h.:
q
Seien p, q ∈ Q Zustände und a ∈ Σ ein Symbol des Alphabets mit
δ(q, a) = p. Dann füge einen mit dem Symbol a beschrifteten Pfeil von
Knoten
zu Knoten
ein, d.h.:
q
p
q
Endliche Automaten
a
Der Automatengraph
p
10 / 38
Wie arbeitet ein DFA?
Die erweiterte Übergangsfunktion
Endliche Automaten
Die erweiterte Übergangsfunktion
11 / 38
Wie arbeitet ein DFA A = (Σ, Q, δ, q0 , F )?
(1/2)
Ein DFA A = (Σ, Q, δ, q0 , F ) erhält als Eingabe ein Wort w ∈ Σ∗ ,
das eine Folge von „Aktionen“ oder „Bedienoperationen“ repräsentiert.
A wird im Startzustand q0 gestartet. Falls w das leere Wort ist, d.h. w = ε, dann
verbleibt A im Zustand q0 .
Also gelte w = a1 · · · an mit n ∈ N>0 und a1 , . . . , an ∈ Σ.
1. Der Automat liest den ersten Buchstaben a1 von w .
Wenn δ nicht für das Paar (q0 , a1 ) definiert ist, dann stürzt A ab
Ansonsten wechselt A in den Zustand q1 := δ(q0 , a1 ).
In der grafischen Darstellung von A wird der Zustand
q0
durch die mit a1 beschriftete Kante verlassen, und q1 ist der Endknoten dieser
Kante, d.h.
a1
q0
q1
Endliche Automaten
Die erweiterte Übergangsfunktion
12 / 38
Wie arbeitet ein DFA A = (Σ, Q, δ, q0 , F )?
(2/2)
2. Durch Lesen von a2 , dem zweiten Symbol von w , wechselt A in den Zustand
q2 := δ(q1 , a2 ), bzw. „stürzt ab“, falls δ nicht für (q1 , a2 ) definiert ist.
In der grafischen Darstellung von A wird
q1
durch die mit a2 beschriftete Kante verlassen (falls diese Kante existiert)
a2
q1
q2
und der Automat landet in Zustand q2 = δ(q1 , a2 ).
n. Auf diese Weise wird das gesamte Eingabewort w = a1 · · · an abgearbeitet.
Ausgehend vom Startzustand q0 erreicht A nacheinander Zustände q1 , . . . , qn .
In der grafischen Darstellung von A entspricht diese Zustandsfolge einem Weg
der Länge n, der im Knoten
q0
startet und dessen Kanten mit den Buchstaben a1 , . . . , an beschriftet sind.
Schreibe δ(q0 , w ) := qn , bzw. δ(q0 , w ) := ⊥, wenn A zwischenzeitlich abstürzt.
Endliche Automaten
Die erweiterte Übergangsfunktion
13 / 38
Was genau ist δ(q, w )?
(1/2)
Sei A := (Σ, Q, δ, q0 , F ) ein DFA. Sei ⊥ ein Symbol, das nicht in der
Zustandsmenge Q liegt, und sei Q⊥ := Q ∪ {⊥}. Die Funktion
δ : Q ⊥ × Σ∗ → Q ⊥
ist rekursiv wie folgt definiert:
F.a. w ∈ Σ∗ ist δ(⊥, w ) := ⊥. (Einmal abgestürzt, immer abgestürzt.)
Der Rekursionsanfang: f.a. q ∈ Q ist δ(q, ε) := q.
Und der Rekursionsschritt?
Endliche Automaten
Die erweiterte Übergangsfunktion
14 / 38
Was genau ist δ(q, w )?
(2/2)
Der Rekursionsschritt: F.a. q ∈ Q, w ∈ Σ∗ und a ∈ Σ gilt für q := δ(q, w ):
δ(q, wa) :=
⊥
falls δ nicht für (q , a) definiert ist,
δ(q , a) falls δ für (q , a) definiert ist.
Grafische Darstellung:
q
w
ˆ w)
δ(q,
a
ˆ w ), a)
δ(δ(q,
wa
Insgesamt gilt:
ˆ 0 , w ) der Zustand, der durch Verarbeiten des
- Falls δ(q0 , w ) = ⊥, so ist δ(q
Worts w erreicht wird.
- Falls δ(q0 , w ) = ⊥, so stürzt der Automat beim Verarbeiten des Worts w ab.
Endliche Automaten
Die erweiterte Übergangsfunktion
15 / 38
DFAs: Die Maschinensichtweise
a1 a2 a3
w=
···
an
Lesekopf
q0
aktueller
Zustand
Wir können uns einen DFA als eine Maschine vorstellen, die
∗ ihre Eingabe w = a1 a2 a3 · · · an
von links-nach-rechts mit Hilfe eines Lesekopfes durchläuft
∗ und dabei Zustandsübergänge durchführt.
Endliche Automaten
DFAs: Die Maschinensichtweise
16 / 38
Können wir heutige Rechner durch DFAs modellieren?
Endliche Automaten
DFAs: Die Maschinensichtweise
17 / 38
Die akzeptierte Sprache eines DFA
DFAs und ihre Sprachen
18 / 38
Wann akzeptiert A = (Σ, Q, δ, q0 , F ) ein Wort w ?
Das Eingabewort w wird vom DFA A akzeptiert, falls
δ(q0 , w ) ∈ F ,
d.h., A stürzt bei Eingabe von w nicht ab, und der nach Verarbeiten von w
erreichte Zustand gehört zur Menge F der akzeptierenden Zustände.
Wie „übersetzt“ sich
Akzeptanz von w = a1 · · · an
in der grafischen Darstellung von A? Es gibt einen in
q0
startenden Weg der Länge n,
- dessen Kanten mit den Symbolen a1 , . . . , an beschriftet sind,
- und der in einem akzeptierenden Zustand
DFAs und ihre Sprachen
endet.
19 / 38
Die akzeptierte Sprache L(A)
Die von einem DFA A = (Σ, Q, δ, q0 , F ) akzeptierte Sprache L(A) ist
L(A) := { w ∈ Σ∗ : δ(q0 , w ) ∈ F }.
Ein Wort w ∈ Σ∗ gehört also genau dann zur Sprache L(A),
wenn w vom DFA A akzeptiert wird.
DFAs und ihre Sprachen
20 / 38
Der Automat A1
Wir betrachten das Eingabealphabet Σ := {a, b}.
Sei A1 ein DFA mit folgender graphischer Darstellung:
b
a
b
A1 akzeptiert z.B. folgende Worte: ε, a, b, aaa, aaab, aaaabbbb, bbb, . . .
A1 „stürzt ab“ z.B. bei Eingabe von ba, aabbba.
Insgesamt gilt:
L(A1 ) = { an b m : n ∈ N, m ∈ N }.
an b m bezeichnet das Wort a · · · ab · · · b der Länge n + m,
das aus n a’s gefolgt von m b’s besteht, z.B. ist a3 b 4 das Wort aaabbbb.
DFAs und ihre Sprachen
Beispiele
21 / 38
Der Automat A2
Der DFA A2 hat den Automatengraphen
a
a
b
b
A2 akzeptiert die Sprache
L(A2 ) = {w ∈ {a, b}∗ : der letzte Buchstabe von w ist ein a }
DFAs und ihre Sprachen
Beispiele
22 / 38
Der Automat A3
Die graphische Darstellung eines DFA A3 mit
L(A3 ) = {w ∈ {a, b}∗ : der vorletzte Buchstabe von w ist ein a }
ist
qaa
b
a
a
qbb
a
b
qba
b
a
b
DFAs und ihre Sprachen
qab
Beispiele
23 / 38
Ein Paritätscheck
Bei der Speicherung von Daten auf einem Speichermedium eines Computers
werden Informationen durch binäre Worte über dem Alphabet {0, 1} kodiert.
Um Fehler bei der Datenübertragung zu erkennen, wird oft ein „Paritätsbit
angehängt, so dass die Summe der Einsen im resultierenden Wort w gerade ist.
Für ein beliebiges Wort w ∈ {0, 1}∗ sagen wir
w „besteht den Paritätscheck“,
falls die Anzahl der Einsen in w gerade ist.
Der folgende DFA A führt einen Paritätscheck durch:
0
0
1
q0
q1
1
Für A gilt: L(A) = {w ∈ {0, 1}∗ : w besteht den Paritätscheck }.
DFAs und ihre Sprachen
Beispiele
24 / 38
Das Murmelspiel
A
(R, L, C)
A
(L, L, −)
(L, L, C )
B
A
A
(L, R, D)
B
(L, L, D)
A
(R, R, D)
B
A
B
A
(R, R, C)
B
B
(R, L, D)
B
B
(L, R, C)
B
A
A
Wir interessieren uns für alle Folgen von Einwürfen von Murmeln in die Eingänge
A oder B, so dass die letzte Murmel am Ausgang D herausrollt:
Uns interessiert also die Sprache aller Worte w ∈ {A, B}∗ , so dass der
Automat vom Startzustand (L, L, −) aus einen Zustand (∗, ∗, D) erreicht!
DFAs und ihre Sprachen
Beispiele
25 / 38
Endliche Automaten in der technischen Informatik
Endliche Automaten in der technischen Informatik
26 / 38
Schaltnetze
Mit einem Schaltnetz wird ein Tupel boolescher Funktionen berechnet, also eine
Funktion der Form
f : {0, 1}n → {0, 1}m .
Schaltnetze können z.B. arithmetische Funktionen berechnen wie etwa die
Addition oder Multiplikation von Zahlen, deren Binärdarstellung n/2 Bits lang ist.
Endliche Automaten in der technischen Informatik
27 / 38
Boolesche Funktionen und endliche Automaten
Sei f : {0, 1}n → {0, 1} eine boolesche Funktion.
Wie berechnet man f mit einem endlichen Automaten Af = (Σ, Q, δ, q0 , F )?
1. Af besitzt das Eingabealphabet Σ = {0, 1}n ,
2. die Zustandsmenge Q = { ε , 0 , 1} mit Startzustand q0 = ε,
3. die partielle Übergangsfunktion δ : Q × Σ → Q mit
δ(ε, x ) = f (x )
4. und die Menge F = { 1 } akzeptierender Zustände.
Aber endliche Automaten können kein Tupel g boolescher Funktionen mit
g : {0, 1}n → {0, 1}m
für m > 1 berechnen!
Endliche Automaten in der technischen Informatik
28 / 38
Moore Automaten und Mealy Automaten:
DFAs mit Ausgaben
Endliche Automaten in der technischen Informatik
Moore Automaten und Mealy Automaten
29 / 38
Moore Automaten
Endliche Automaten können „nur“ akzeptieren oder verwerfen,
Moore Automaten können beliebige Ausgaben ausgeben.
Ein Moore Automat (Σ, Q, δ, q0 , λ, Ω, F ) ist wie ein DFA aufgebaut,
besitzt aber zusätzlich
- ein Ausgabealphabet Ω und
- eine Ausgabefunktion λ : Q → Ω.
Ein Moore Automat produziert für jeden Zustand eine Ausgabe.
Endliche Automaten in der technischen Informatik
Moore Automaten und Mealy Automaten
30 / 38
Moore Automaten und Tupel boolescher Funktionen
Das Tupel
f : {0, 1}n → {0, 1}m
boolescher Funktionen sei vorgegeben.
f wird von dem folgenden Moore Automaten (Σ, Q, δ, q0 , λ, Ω, F ) berechnet:
- Σ = {0, 1}n ist das Eingabealphabet,
- Q = { ε } ∪ {0, 1}m ist die Zustandsmenge und q0 = ε der Startzustand,
- δ : Q × Σ → Q mit
δ(ε, x ) = f (x )
ist die partielle Übergangsfunktion (δ ist nur für von ε ausgehende
Übergänge definiert),
- Ω = {0, 1}m ist das Ausgabealphabet und
- λ : Q → Ω mit λ(q) = q ist die Ausgabefunktion.
Endliche Automaten in der technischen Informatik
Moore Automaten und Mealy Automaten
31 / 38
Schaltwerke
In einem Schaltwerk wird Rückkopplung erlaubt: In „einem Schritt“ wird eine
Ausgabefunktion gA und eine Rückkopplungsfunktion gR berechnet mit
gA : {0, 1}n × {0, 1}r → {0, 1}m und gR : {0, 1}n × {0, 1}r → {0, 1}r
Erscheinen nacheinander die Eingaben x1 , . . . , xk ∈ {0, 1}n , dann werden
Ausgaben y1 , . . . , yk ∈ {0, 1}m und Rückkopplungen r0 = 0r , r1 , . . . , rk−1
berechnet, wobei
yi = gA (xi , ri−1 ) und ri = gR (xi , ri−1 ).
Beispielsweise kann ein Steuerwerk durch ein Schaltwerk berechnet werden.
1. Ein Steuerwerk lädt den nächsten Befehl und interpretiert ihn.
2. Operanden, auf die sich der Befehl bezieht, werden geladen und Steuersignale
an andere Funktionseinheiten (wie etwa das Rechenwerk) erstellt.
Endliche Automaten in der technischen Informatik
Moore Automaten und Mealy Automaten
32 / 38
Mealy Automaten
Auch Mealy Automaten sind wie DFAs aufgebaut, besitzen aber zusätzlich
- ein Ausgabealphabet Ω und
- eine Ausgabefunktion λ : Q × Σ → Ω.
Ein Mealy Automat produziert eine vom Zustand und
vom Eingabesymbol abhängige Ausgabe.
Warum können wir einen Moore Automaten mit Ausgabefunktion
λ:Q→Ω
auch als Mealy Automaten mit Ausgabefunktion
λ :Q×Σ→Ω
auffassen? Wie sollten wir λ (q, a) definieren?
Endliche Automaten in der technischen Informatik
Moore Automaten und Mealy Automaten
33 / 38
Ein Mealy Automat für die Addition
Die Binärzahlen x = 0xn · · · x0 und y = 0yn · · · y0 sind zu addieren.
Die Eingabe ist [x0 y0 ][x1 y1 ] · · · [xn yn ][00].
Das i-te Ausgabe-Bit hängt nur ab von xi−1 , yi−1 und dem im vorherigen Schritt
evtl. erzeugten Übertrag.
00/0
③
01, 10/0
✛✘
✮
00/1
q0
q1
✿ ✚✙
11/0
01, 10/1
Endliche Automaten in der technischen Informatik
✛✘
✾
②
✶ ✚✙
11/1
Moore Automaten und Mealy Automaten
34 / 38
Mealy Automaten und Schaltwerke
Schaltwerke lassen sich durch (Moore Automaten oder) Mealy Automaten
modellieren.
1. Angenommen, das Schaltwerk berechnet
die Ausgabefunktion
gA : {0, 1}r × {0, 1}n → {0, 1}m
mit der Rückkopplung
gR : {0, 1}r × {0, 1}n → {0, 1}r .
2. Wir definieren einen Mealy Automaten M = (Σ, Q, δ, q0 , λ, Ω) wie folgt:
Eingabealphabet Σ = {0, 1}n und Ausgabealphabet Ω = {0, 1}m ,
Zustandsmenge Q = {0, 1}r ,
Ausgabefunktion λ : Q × Σ → Ω mit λ = gA und
Übergangsfunktion δ : Q × Σ → Q mit δ = gR .
M verhält sich wie das Schaltwerk, berechnet also dieselbe Ausgabenfolge.
Automaten können Rückkopplung mit Hilfe ihrer Zustände simulieren und
bieten sich deshalb für die (partielle) Beschreibung von Schaltwerken an!
Endliche Automaten in der technischen Informatik
Moore Automaten und Mealy Automaten
35 / 38
Technische Informatik: Der Entwurf von Schaltwerken
Moore oder Mealy Automaten spielen eine zentrale Rolle.
Der Entwurfsprozess
1. Ein DFA wird zur Lösung eines Teils der Problemstellung entwickelt.
2. Der Automat wird minimiert, d.h. ein äquivalenter Automat mit kleinster
Zustandsmenge wird berechnet und seine Automatentabelle bestimmt.
3. Mit Verfahren der Logik-Optimierung (wie etwa Quine/McCluskey) bestimmt
man die minimale Gatterzahl für den kombinatorischen Teil der Schaltung.
Alle Details und viel, viel mehr in der Vorlesung
Hardwarearchitekturen und Rechensysteme.
Endliche Automaten in der technischen Informatik
Moore Automaten und Mealy Automaten
36 / 38
Bitte, bitte, bitte
keinen partiell definierten Moore oder Mealy Automaten
„in Silikon gießen“.
Abstürzen ist nicht erlaubt!
Wir haben partiell definierte Automaten nur benutzt,
um kompakte Beschreibungen zu erhalten.
Endliche Automaten in der technischen Informatik
Moore Automaten und Mealy Automaten
37 / 38
Können wir heutige Rechner durch DFAs modellieren?
1. Ja: Heutige Rechner besitzen zwar einen modifizierbaren Speicher, aber dieser
Speicher ist beschränkt.
Was immer ein moderner Rechner berechnen kann, lässt sich auch durch Mooreoder Mealy-Automaten berechnen.
2. Aber:
um k Flip-Flops zu simulieren, brauchen wir DFAs mit bis zu 2k Zuständen.
Eine Modellierung moderner Rechner durch DFAs ist deshalb unsinning.
3. Aber DFAs bieten sich zum Beispiel an, um Steuerwerke zu simulieren.
Endliche Automaten in der technischen Informatik
Moore Automaten und Mealy Automaten
38 / 38
Document
Kategorie
Technik
Seitenansichten
29
Dateigröße
522 KB
Tags
1/--Seiten
melden