Algorithmen und Datenstrukturen

Praktische Einführung und Programmierung

Stefan Bosse

Universität Koblenz - FB Informatik

1 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten ::

Endliche Zustandsautomaten

Logik
Mathematik
Graphen
Tabellen
Automaten (die Maschine)

https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/ti_7_4_ger_web.html

2 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Schaltnetze und Schaltwerke

Schaltnetze und Schaltwerke

Ohne Rückkopplung (Schaltnetz)
- Werte an den Ausgängen sind nur abhängig von den Eingängen
- Solche Schaltungen verhalten sich immer gleich (sind zustandslos) und sind durch ihre Schaltfunktion eindeutig beschrieben
- Es ist jedoch nicht möglich, etwas zu speichern
Mit Rückkopplung (Schaltwerk)
- Werte an den Ausgängen sind abhängig von den Eingängen und den vorherigen Ausgangswerten
- Das Zeitverhalten muss genau betrachtet werden
- Die vorherigen Ausgangswerte können als Zustand der Gatter interpretiert werden. Abhängig vom Zustand verhalten sich die Gatter anders (zustandsabhängige Schaltfunktion)
- Es wird möglich, Zustände zu speichern

3 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Schaltwerke

Schaltwerke

Ein Schaltwerk kann auch als eine Kombination aus einem Schaltnetz und einem Zustandsspeicher dargestellt werden
Die Ausgabe eines Schaltwerks kann abhängig vom aktuellen Zustand sein
Abhängig von den Eingangswerten kann sich der Zustand eines Schaltwerks ändern
Zur Beschreibung der zustandsabhängigen Schaltfunktion können endliche Automaten verwendet werden

4 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Endliche Automaten

Endliche Automaten

Ein endlicher Automat (engl. Finite State Machine, FSM) ist definiert durch
- eine endliche Menge A von Eingabesymbolen ai∈A (Alphabet)
- eine endliche Menge S von Zuständen si∈S
- einen Anfangszustand s0∈S
- eine Zustandsübergangsfunktion δ:S×A→S
Des Weiteren kann er umfassen
- eine endliche Menge B von Ausgabesymbolen bi∈B
- eine Ausgabefunktion λ:S×A→B
Bei deterministischen Automaten erfolgen die Zustandsübergänge deterministisch (nicht zufällig)
Endliche Automaten können durch Zustandsübergangsgraphen dargestellt werden

5 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Zustandsübergangsgraphen

Zustandsübergangsgraphen

In einem Zustandsübergangsgraphen wird jeder Zustand si∈S als ein Kreis dargestellt
Die möglichen Zustandsübergänge werden mit Pfeilen gekennzeichnet
Jeder Pfeil wird mit dem zugehörigen Eingabesymbol am∈A beschriftet, für das dieser Zustandsübergang auftritt
Außerdem (abgetrennt durch einen "/") kann jeweils das Ausgabesymbol oder eine Aktion bn∈B angegeben werden

Ein Zustandsübergang vom Zustand s_i nach s_j durch eine Bedingung, hier das Vorliegen eines Eingabesymbols a, mit der Aktion der Ausgabe eines Symbols b.

6 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Zustandsübergangsgraphen

Zustandsübergangsgraphen

Beispiel: Ampelschaltung

Es soll eine Schaltung für eine Fußgängerampelanlage erstellt werden. Es wird dabei die Ampel, die den Autoverkehr regelt, betrachtet (nicht die Fußgängerampel)
- Die Ampel reagiert auf das Drücken eines Ampelknopfs durch einen Fußgänger:
- a0 = 0 bedeutet der Ampelknopf wurde nicht gedrückt
- a1 = 1 bedeutet der Ampelknopf wurde gedrückt
- Im Anfangszustand s0∈S ist die Ampel grün
- Wurde der Ampelknopf gedrückt, soll die Ampel zunächst auf gelb und dann auf rot schalten
- Es wird weiterhin davon ausgegangen, dass das durch den Ampelknopf gesteuerte Eingabesymbol automatisch, nachdem der Fußgänger genug Zeit hatte die Straße zu überqueren, von a1 nach a0 wechselt
- Die Ampel soll dann zunächst gelb-rot zeigen und schließlich wieder grün

7 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Zustandsübergangsgraphen

Zustandsübergangsgraphen

Menge der Eingabesymbole A={a0,a1} binär kodiert mit {0,1}
Menge der Zustände S={s0,s1,s2,s3}
Menge der Ausgabesymbole B={b0,b1,b2,b3} binär kodiert mit y2y1y0 zu {001,010,110,100}
Es gibt |S|⋅|A|=4⋅2=8 mögliche Zustandsübergänge

Beispiel Ampelschaltung: (Links) Zustandsübergangsgraph (Rechts) Die Ausgabe der Zustände

8 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Mealy und Moore-Automaten

Mealy und Moore-Automaten

Moore-Automaten: Bei einem Moore-Automaten ist die Ausgabefunktion λ:S→B nur vom aktuellen Zustand abhängig

Mealy-Automaten: Bei einem Mealy-Automaten ist die Ausgabefunktion λ:S×A→B vom aktuellen Zustand und der Eingabe abhängig

https://unstop.com/blog/difference-between-mealy-and-moore-machine

9 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Vom Zustandsübergangsgraphen zum Automaten

Vom Zustandsübergangsgraphen zum Automaten

Der Zustandsübergangsgraph der Ampelschaltung soll in ein Schaltwerk umgesetzt werden
Zur Erstellung des Schaltwerks kann die Ausgabefunktion, die Übergangsfunktion und der Zustandsspeicher separat betrachtet werden
Für gewünschte Ausgabe- und Übergangsfunktion kann direkt aus dem Zustandsübergangsgraphen abgelesen und als Wahrheitstafel dargestellt werden
Zur Minimierung der Schaltlogik (Boolesche Algebra) können anschließend z.B. BDD verwendet werden

Handelt es sich bei Ampelbeispiel um einen Moore- oder Mealy-Automaten?

10 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Vom Zustandsübergangsgraphen zum Automaten

Vom Zustandsübergangsgraphen zum Automaten

Der Zustandsübergangsgraph der Ampelschaltung soll in ein Schaltwerk umgesetzt werden
Zur Erstellung des Schaltwerks kann die Ausgabefunktion, die Übergangsfunktion und der Zustandsspeicher separat betrachtet werden
Für gewünschte Ausgabe- und Übergangsfunktion kann direkt aus dem Zustandsübergangsgraphen abgelesen und als Wahrheitstafel dargestellt werden
Zur Minimierung der Schaltlogik (Boolesche Algebra) können anschließend z.B. BDD verwendet werden

Handelt es sich bei Ampelbeispiel um einen Moore- oder Mealy-Automaten?

Antwort: Moore-Automat, da die Ausgabefunktion nur abhängig vom aktuellen Zustand ist.

11 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Funktionen und Tabellen für das Schaltwerk

Funktionen und Tabellen für das Schaltwerk

${y}{2}={q}{1}\\ {y}{1}={q}{0}↮{q}{1}\\ {y}{0}=¬{q}{0}∧¬{q}{1}=¬{\left({q}{0}∨{q}{1}\right)}$

Ausgabefunktion als Wahrheitstabelle

12 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Übergangsfunktion

Übergangsfunktion

Es gibt neben einem Schaltnetz, also der Zustandsübergangsfunktion, einen Zustandsspeicher, hier q=(q₀,q₁) mit den Dateneingängen d=(d₀,d₁).

(Links) Zustandsübergangsgraph (Rechts) Zustandsübergangstabelle mit d₁=q₀

13 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Übergangsfunktion

Aus der Zustandsübergangstabelle kann die Übergangsfunktion berechnet werden und z.B. mit BDD Verfahten verinfacht werden.

Normalformen von Booleschen Funktionen können direkt aus der Tabelle (automatisch) abgeleitet werden.

${d}_{{0}}={\left(¬{q}_{{1}}{x}_{{0}}\right)}∨{\left(¬{q}_{{1}}{q}_{{0}}\right)}∨{\left({q}_{{0}}{x}_{{0}}\right)}$

14 / 15

Stefan Bosse - Algorithmen und Datenstrukturen - Modul FSM Endliche Zustandsautomaten :: Vom Zustandsübergangsgraphen zum Schaltwerk

Vom Zustandsübergangsgraphen zum Schaltwerk

Die Maschinen mit Digitallogik (Kombinatorische und sequenzielle Logik)

15 / 15