Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein Modell eines Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Ein Automat heißt endlich, wenn die Menge der Zustände, die er annehmen kann (später S genannt), endlich ist. Ein endlicher Automat ist ein Spezialfall aus der Menge der Automaten.

Ein Zustand kann Information über die Vergangenheit beinhalten, da das System ihn ja auf dessen bisherigem Weg erreicht hat, d. h., er reflektiert in gewissem Umfang die Änderungen der Eingabe seit dem Systemstart bis zum aktuellen Zeitpunkt.

Ein Zustandsübergang ist ein Übergang aus dem aktuellen Zustand in einen neuen (anderen) Zustand. Zu diesem Übergang kommt es, wenn die angegebenen logischen Bedingungen/„Eingaben“ vorliegen, die erfüllt sein müssen, um den Übergang zu ermöglichen.

Eine Aktion ist die „Ausgabe“ des EA, die in einer bestimmten Situation erfolgt. Es gibt vier Typen von Aktionen:

• Eingangsaktion: Die Aktion wird ausgeführt/ausgegeben beim Eintreten in einen Zustand (egal über welchen Zustandsübergang der Zustand erreicht wurde, falls es mehrere gibt).
• Ausgangsaktion: Die Aktion wird beim Verlassen eines Zustandes generiert (egal über welchen Zustandsübergang der Zustand verlassen wird).
• Eingabeaktion: Die Aktion wird abhängig vom aktuellen Zustand und der Eingabe generiert. Einem Zustand können also mehrere Aktionen zugeordnet sein, die abhängig davon ausgeführt werden, über welchen Zustandsübergang er erreicht/verlassen wird.
• Übergangsaktion: Die Aktion wird abhängig/während eines Zustandsübergangs ausgeführt.

Ein EA kann als Zustandsübergangsdiagramm wie in Abbildung 1 dargestellt werden. Zusätzlich werden mehrere Typen von Übergangstabellen (bzw. Zustandsübergangstabellen) benutzt. Die folgende Tabelle zeigt eine sehr verbreitete Form von Übergangstabellen: Die Kombination aus dem aktuellen Zustand (B) und Eingabe (Y) führt zum nächsten Zustand (C). Die komplette Information über die möglichen Aktionen wird mit Hilfe von Fußnoten angegeben. Eine Definition des EA, die auch die volle Ausgabeinformation beinhaltet, ist mit Zustandstabellen möglich, die für jeden Zustand einzeln definiert werden (siehe auch virtueller EA).

Die Definition des EA wurde ursprünglich in der Automatentheorie eingeführt und später in der Computertechnik übernommen.

Zustandsmaschinen werden hauptsächlich in der Entwicklung digitaler Schaltungen, Modellierung des Applikationsverhaltens (Steuerungen), generell in der Softwaretechnik sowie Wort- und Spracherkennung benutzt.

Das Testen der Qualität eines Systems umfasst die Überprüfung aller Zustände und Zustandsübergänge, indem alle potenziellen Eingaben in Betracht gezogen werden, die eingegeben werden können. In einigen Fällen wird der endliche Automat unter Verwendung einer Programmiersprache eingerichtet und Zustandsübergangsfunktionen werden ausgeführt. Darüber hinaus kann künstliche Intelligenz verwendet werden, um Daten über Systeme mit Mustererkennung und automatisierten Modellen zu sammeln. Bei einfacheren Problemen können die gleichen Informationen in Tabellen, Matrizen, Abbildungen und Programmablaufplänen angezeigt werden, aber mit endlichen Automaten können größere und kompliziertere Szenarien modelliert werden.

Klassifizierung

Generell werden zwei Gruppen von EA unterschieden: Akzeptoren und Transduktoren.

Die Logik des EA

Der nächste Zustand und die Ausgabe des EA ist eine Funktion der Eingabe und des aktuellen Zustandes. Abbildung 5 zeigt den Ablauf der Logik.

Das mathematische Modell

Es gibt unterschiedliche Definitionen, je nach Typ des DEA. Ein Akzeptor ist ein 5-Tupel (${\displaystyle Q,s,\Sigma ,F,\delta }$), wobei:

• ${\displaystyle Q}$ ist die endliche Zustandsmenge (${\displaystyle q_{0}-q_{x}}$)
• ${\displaystyle s}$ ist der Startzustand (${\displaystyle s\in Q}$)
• ${\displaystyle \Sigma }$ ist das endliche Eingabealphabet
• ${\displaystyle F}$ ist die Endzustandsmenge (${\displaystyle F\subset Q}$)
• ${\displaystyle \delta }$ ist die Übergangsfunktion, sie lässt sich als Automatentafel oder als Zustandsübergangsgraph darstellen.

Ein Transduktor ist ein 7-Tupel (${\displaystyle \Sigma ,\Gamma ,S,s_{0},F,\delta ,\omega }$), wobei:

• ${\displaystyle \Sigma }$ ist das Eingabealphabet (eine endliche nicht leere Menge von Symbolen),
• ${\displaystyle \Gamma }$ ist das Ausgabealphabet (eine endliche nicht leere Menge von Symbolen),
• ${\displaystyle S}$ ist eine endliche nicht leere Menge von Zuständen,
• ${\displaystyle F}$ ist die Endzustandsmenge (${\displaystyle F\subset S}$)
• ${\displaystyle s_{0}}$ ist der Anfangszustand und ein Element aus ${\displaystyle S}$,
• ${\displaystyle \delta }$ ist die Zustandsübergangsfunktion: ${\displaystyle \delta :S\times \Sigma \to S}$,
• ${\displaystyle \omega }$ ist die Ausgabefunktion: ${\displaystyle \omega :S\times \Sigma \to \Gamma }$,

Falls die Ausgabefunktion eine Funktion von Zustand und Eingabealphabet ist (${\displaystyle \omega :S\times \Sigma \to \Gamma }$), dann handelt es sich um ein Mealy-Modell. Falls die Ausgabefunktion nur vom Zustand abhängt (${\displaystyle \omega :S\to \Gamma }$), dann ist es ein Moore-Modell.

Beispiel

Der EA in Abbildung 6 hat die Zustandsmenge ${\displaystyle S:=\{q_{1},q_{2},q_{3}\}}$, den Startzustand ${\displaystyle q_{1}}$, das Eingabealphabet ${\displaystyle \Sigma$ :=\{a,b\}} , das Ausgabealphabet ${\displaystyle \Gamma$ :=\{0,1\}} , die Zustandsübergangsfunktion ${\displaystyle \delta :S\times \Sigma \to S}$ mit ${\displaystyle \delta (q_{1},a)=q_{3}}$, ${\displaystyle \delta (q_{1},b)=q_{2}}$, ${\displaystyle \delta (q_{2},a)=q_{1}}$, ${\displaystyle \delta (q_{2},b)=q_{2}}$, ${\displaystyle \delta (q_{3},a)=q_{1}}$, ${\displaystyle \delta (q_{3},b)=q_{2}}$ und die Ausgabefunktion ${\displaystyle \omega :S\times \Sigma \to \Gamma }$ mit ${\displaystyle \omega (q_{1},a)=0}$, ${\displaystyle \omega (q_{1},b)=1}$, ${\displaystyle \omega (q_{2},a)=1}$, ${\displaystyle \omega (q_{2},b)=1}$, ${\displaystyle \omega (q_{3},a)=0}$, ${\displaystyle \omega (q_{3},b)=0}$.

Optimierung

Ein EA wird optimiert, indem die Zustandsmaschine mit der geringsten Anzahl von Zuständen gefunden wird, die die gleiche Funktion erfüllt. Dieses Problem kann zum Beispiel mit Hilfe von Färbungsalgorithmen gelöst werden.

Homing-Folgen und UIO-Folgen

Homing-Folgen

Eine Homing-Folge (auch Homing-Sequenz) ist eine Folge von Eingaben, sodass sich anhand der Ausgaben bestimmen lässt, in welchem Zustand sich die Maschine danach befindet. Dadurch kann bei stark zusammenhängenden Zustandsmaschinen sehr leicht eine Folge gefunden werden, um wieder zum Initialzustand zurückzukehren, also nach Hause (englisch home). Jede minimale Zustandsmaschine besitzt eine Homing-Folge.

Homing-Folge zu Abbildung 6

Eingabe	mögliche Zustandsmengen (bei welcher Ausgabe)
ε	${\displaystyle \{q_{1},q_{2},q_{3}\}}$
a	${\displaystyle \{q_{1},q_{3}\}_{0},\{q_{1}\}_{1}}$
aa	${\displaystyle \{q_{1},q_{3}\}_{00},\{q_{3}\}_{10}}$
ab	${\displaystyle \{q_{2}\}_{00},\{q_{2}\}_{01},\{q_{2}\}_{11}}$
b	${\displaystyle \{q_{2}\}_{1},\{q_{2}\}_{0}}$

Implementierung

Darstellung endlicher Automaten

Die allgemeinen Regeln für das Zeichnen eines Zustandsübergangsdiagramms sind wie folgt:

• Kreise stellen Zustände dar. Im Kreis steht der Name des Zustands.
• Pfeile zwischen Zuständen stellen die Transitionen dar. Auf jedem Pfeil steht, welche Bedingungen den Übergang ermöglichen.

Programmierung

Das folgende Codebeispiel in der Programmiersprache Java zeigt die Implementierung eines endlichen Automaten mit der Zustandsmenge${\displaystyle S:=\{\mathrm {Ready} ,\mathrm {Waiting} ,\mathrm {Dispensing} ,\mathrm {Refunding} ,\mathrm {Exiting} \}}$, dem Startzustand ${\displaystyle s:=\mathrm {Ready} }$, der Endzustandsmenge ${\displaystyle F:=\{\mathrm {Exiting} \}}$ und dem Eingabealphabet ${\displaystyle \Sigma$ :=\{\mathrm {Deposit} ,\mathrm {Quit} ,\mathrm {Select} ,\mathrm {Refund} ,\mathrm {Remove} ,\mathrm {Refunding} ,\mathrm {Quiting} \}} .

import java.util.*;

// Deklariert eine Klasse für einen endlichen Automaten
public class FiniteStateMachine
{
	// Deklariert einen Aufzählungstyp für die Zustände
    private enum State
    {
    	// Definiert die möglichen Eingaben für die Zustände
        Ready("Deposit", "Quit"),
        Waiting("Select", "Refund"),
        Dispensing("Remove"),
        Refunding("Refunding"),
        Exiting("Quiting");

    	// Konstruktor, der die möglichen Eingaben für den Zustand speichert
        State(String... inputs)
        {
            this.inputs = Arrays.asList(inputs);
        }

        // Methode, die den Nachfolgezustand für die aktuelle Eingabe und den aktuellen Zustand zurückgibt
        State nextState(String input, State currentState)
        {
        	// Wenn die aktuelle Eingabe in der Liste der möglichen Eingaben enthalten ist, wird der Nachfolgezustand zurückgegeben
            if (inputs.contains(input))
            {
                return map.getOrDefault(input, currentState);
            }
            // Sonst wird der aktuelle Zustand zurückgegeben
            return currentState;
        }

        // Hashtabelle für die Zustandsübergangsfunktion
        final static HashMap<String, State> map = new HashMap<>();
        // Liste für die möglichen Eingaben
        final List<String> inputs;

    	// Definiert die Zustandsübergangsfunktion
        static
        {
            map.put("Deposit", State.Waiting);
            map.put("Quit", State.Exiting);
            map.put("Select", State.Dispensing);
            map.put("Refund", State.Refunding);
            map.put("Remove", State.Ready);
            map.put("Refunding", State.Ready);
        }
    }

    // Hauptmethode, die das Programm ausführt
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        // Startzustand
        State state = State.Ready;
        // Endzustand
        // Wenn der Endzustand nicht erreicht ist
        while (state != State.Exiting)
        {
        	// Gibt die möglichen Eingaben für den aktuellen Zustand auf der Konsole aus
            System.out.println(state.inputs);
            System.out.print("> ");
            // Ruft die Methode für den Nachfolgezustand auf
            state = state.nextState(scanner.nextLine().trim(), state);
        }
        scanner.close();
    }
}

Siehe auch

• Behavior Tree
• Chomsky-Hierarchie
• Ragel
• Zellulärer Automat

Literatur

• John E. Hopcroft, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2. Auflage. Addison-Wesley, Bonn / München 1990, ISBN 3-89319-181-X (englisch, Originaltitel: Introduction to automata theory, languages and computation.). 
• Peter Sander, Wolffried Stucky, Rudolf Herschel: Automaten, Sprachen, Berechenbarkeit. Teubner, Stuttgart 1992, ISBN 3-519-02937-5.
• Ferdinand Wagner: Modeling Software with Finite State Machines: A Practical Approach. Auerbach, Boca Raton 2006, ISBN 0-8493-8086-3.
• Zvi Kohavi: Switching and Finite Automata Theory. McGraw-Hill, New York 1978, ISBN 0-07-035310-7. (englisch)
• Arthur Gill: Introduction to the Theory of Finite-state Machines. McGraw-Hill, New York 1962. (englisch)
• Heinz-Dietrich Wuttke, Karsten Henke: Schaltsysteme – Eine automatenorientierte Einführung. Pearson Studium, München 2003, ISBN 3-8273-7035-3.

Weblinks

• Endlicher Automat mit der Möglichkeit zum Ausprobieren – hwlang.de
• Formale Sprachen und Abstrakte Automaten – Kurs von Tino Hempel
• Kara – Programmieren mit endlichen Automaten – Kurs: Spielerisch den Marienkäfer „Kara“ als EA programmieren und Aufgaben lösen.
• JFLAP – Java-Programm zum Erstellen von Automaten aller Art (englisch)
• FSM Creator – Programm zum Erstellen von endlichen Automaten (englisch)
• Sinelabore – Erzeugt C/C++/Java Code aus UML Zustandsdiagrammen. Der Fokus liegt auf Embedded Systems. (englisch)
• Automaton – Java-Quellcode-Beispiel für einen endlichen Automaten (englisch, deutsche Kommentare)
• YAKINDU Statechart Tools – Ein Open-Source-Werkzeug zur Spezifikation und Entwicklung von reaktiven, ereignisgesteuerten Systemen mit Hilfe von Zustandsautomaten
• C++ Fsm Framework, ein event getriebenes Zustandsmaschinen Framework für C++ mit PERL script zur Generierung von PlantUML Dateien zur FSM Dokumentation.

Einzelnachweise

1. ↑ TechTarget: finite state machine
2. ↑ Pong P. Chu: RTL Hardware Design using VHDL. Wiley Interscience, 2006, ISBN 0-471-72092-5, Kapitel 10, insbesondere 10.4: Moore machine versus Mealy machine.
3. ↑ Rosetta Code: Finite state machine