Endlicher Automat (Finite State Machine, FSM)

Was ist Finite State Machine (FSM oder Endlicher Automat)?

Eine Finite State Machine (FSM), auf Deutsch als Endlicher Automat oder Endliche Zustandsmaschine bezeichnet, ist ein mathematisches Modell, das in der Programmierung, Mathematik und Technik verwendet wird. Es dient zur Beschreibung von Systemen, die nur eine begrenzte Anzahl von Zuständen haben, die durch bestimmte Bedingungen erreicht werden. Ein praktisches Beispiel dafür ist ein Videospiel-Controller: Jede Taste ist mit bestimmten Aktionen im Spiel verknüpft. Wenn der Spieler eine Taste drückt, erkennt das System den Zustand und führt die zugehörige Aktion aus.

Der Aufbau eines endlichen Automaten besteht aus Folgendem:

• Eine Menge möglicher Eingabeereignisse.
• Eine Menge von wahrscheinlichen Ausgabeereignissen, die den potenziellen Eingabeereignissen entsprechen.
• Eine Menge von erwarteten Zuständen, die das System annehmen kann.

Ein endlicher Automat kann sowohl in Software als auch in Hardware implementiert werden, um komplexe Probleme übersichtlich darzustellen. In einer FSM sind alle möglichen Zustände in einer endlichen Liste definiert, wobei der Automat zu jedem Zeitpunkt nur einen dieser Zustände annehmen kann. Durch diesen Ansatz lassen sich sämtliche Eingabe- und Ausgabeszenarien systematisch analysieren und testen.

Bestandteile einer Finite State Machine:

• Zustände (States): Das System kann sich in einem von mehreren möglichen Zuständen befinden.
• Startzustand: Der Zustand, in dem das System beginnt.
• Eingaben (Inputs): Ereignisse oder Bedingungen, die Zustandsänderungen auslösen.
• Übergänge (Transitions): Regeln, die bestimmen, wie das System von einem Zustand in einen anderen wechselt, basierend auf Eingaben.
• Endzustände (optional): Zustände, die das Ende des Prozesses signalisieren.

Ein FSM kann etwas sehr Abstraktes sein, wie ein Geschäftsmodell, das durch eine Abbildung dargestellt wird, oder etwas Konkretes, wie ein Verkaufsautomat oder ein Computer. Die Liste der möglichen Kombinationen dieser Elemente ist bei einem endlichen Zustandsautomaten begrenzt. Alternativ dazu kann ein Zustandsautomat auch unscharf sein. Ein unscharfer Zustandsautomat lässt die Möglichkeit von Datenpunkten zu, die nicht in diskrete, vorher festgelegte Kategorien fallen.

Arten von FSM:

• Deterministische FSM (DFA - Deterministic Finite Automation): Jeder Zustand hat für jede Eingabe genau einen definierten Übergang.
• Nichtdeterministische FSM (NFA - Non-Deterministic Finite Automaton): Ein Zustand kann mehrere Übergänge für eine einzelne Eingabe haben, oder es kann Übergänge ohne Eingabe geben.

Automata-Theorie

Während das Wort Maschine traditionell eine physische Komponente enthält, bezieht es sich in diesem Zusammenhang auf eine Abstraktion, die die Form eines Satzes von Eingangsereignissen, eines Computers, einer einfachen analogen Maschine oder eines theoretischen Modells eines abstrakten Konzepts in der Automatentheorie annehmen kann. Automaten sind ein theoretischer Zweig der Informatik und der diskreten Mathematik, der sich mit der Logik einfacher Maschinen beschäftigt. Zu den Arten von Rechenmodellen innerhalb der Automatentheorie gehören:

• Endliche Zustandsautomaten: Modelle für jedes System mit einer begrenzten Anzahl von bedingten Zuständen.
• Pushdown-Automaten: Sie sind komplizierter als endliche Zustandsautomaten und verwenden Speicherbereiche, die Stapel genannt werden, um Informationen als Teil eines Modells zu speichern.
• Linear-Bounded Automata (LBA): Ähnlich wie ein Turing-Automat, aber die Daten sind auf einen Teil der Eingabe innerhalb einer endlichen Gruppe von Eingaben beschränkt.
• Turing-Automaten: Das komplexeste mathematische Modell innerhalb der Automatentheorie zum Testen verschiedener Eingabekombinationen, um ein größeres System oder Problem zu analysieren.

Zustandsübergang (State Transition)

Wenn ein endlicher Automat zwischen Zuständen wechselt, wird dies als Zustandsübergang bezeichnet. Beim Testen der Qualität eines Systems wird jeder Zustand und jeder Zustandsübergang unter Berücksichtigung aller möglichen Eingaben geprüft. In einigen Fällen wird der endliche Zustandsautomat mit Hilfe einer Programmiersprache erstellt, und die Zustandsübergangsfunktionen werden ausgeführt. Darüber hinaus kann künstliche Intelligenz (KI) eingesetzt werden, um mit Hilfe von Mustererkennung und automatischen Modellen Daten über Systeme zu sammeln.

Bei einfacheren Problemen können dieselben Informationen in Tabellen, Matrizen, Abbildungen und Flussdiagrammendargestellt werden, aber mit endlichen Zustandsautomaten können Forscher größere und kompliziertere Szenarien modellieren. Diagramme von endlichen Zustandsautomaten zeigen den logischen Fluss zwischen Eingabe- und Ausgabekombinationen, die innerhalb eines bestimmten Automaten auftreten können.