Fachkonzept - Endlicher Automat
Grundidee
Beispiel:
Ein Türsystem wird von einem Zustandsdiagramm gesteuert. Das Zustandsdiagramm befindet sich immer in einem bestimmten Zustand. Im Beispiel ist dies der Zustand alle Türen zu.
Klickt man auf Button 2, so erhält das Zustandsdiagramm die Eingabe 2. An dem Zustand alle Türen zu beginnt ein Pfeil, der mit 2|XOX beschriftet ist und zu dem Zustand mittlere Tür auf führt. Deshalb wechselt das Zustandsdiagramm in den Zustand mittlere Tür auf und erzeugt die Ausgabe XOX.
Die Ausgabe XOX wird an das Türsystem weitergeleitet. Deshalb öffnet sich die mittlere Tür, während die anderen Türen geschlossen bleiben.
Präzissierung
Ein solches Zustandsdiagramm ist eine bildiche Darstellung eines endlichen Automaten.Ein endlicher Automat (kurz: EA) ist eine Verarbeitungseinheit, die durch folgende Bestandteile festgelegt wird:
- eine nichtleere, endliche Menge Z von Zuständen
- eine nichtleere, endliche Menge E von Eingabesymbolen
- eine nichtleere, endliche Menge A von Ausgabesymbolen
- eine Überführungsfunktion f, die jedem Paar aus aktuellem Zustand und Eingabe einen Folgezustand zuordnet
- eine Ausgabefunktion g, die jedem Paar aus aktuellem Zustand und Eingabe eine Ausgabe zuordnet
- ein ausgezeichnetes Element z0 ∈ Z, der sogenannte Anfangszustand
Der Automat im obenstehenden Beispiel besteht aus folgenden Bestandteilen:
- Z = {alle Türen zu, linke Tür auf, rechte Tür auf, mittlere Tür auf}
- E = {1, 2, 3}
- A = {XXX, OXX, XOX, XXO, OOX, OXO, XOO, OOO}
- f:
- (alle Türen zu, 1) -> alle Türen zu
- (alle Türen zu, 2) -> mittlere Tür auf
- ...
- g:
- (alle Türen zu, 1) -> XXX
- (alle Türen zu, 2) -> XOX
- ...
- z0 = alle Türen zu
Die Überführungsfunktion f und die Ausgabefunktion g sind in einem Zustandsdiagramm durch Pfeile und Beschriftungen dargestellt. Sie können auch in einer Tabelle dargestellt werden:
| Zustand | Eingabe | Folgezustand | Ausgabe |
|---|---|---|---|
| alle Türen zu | 1 | alle Türen zu | XXX |
| alle Türen zu | 2 | mittlere Tür auf | XOX |
| alle Türen zu | 3 | alle Türen zu | XXX |
| ... | ... | ... | ... |
