Endlicher Automat (Zustandsmaschine, Zustandsautomat)
Endlicher Automat, auch Zustandsmaschine oder Zustandsautomat (Finite State Machine, FSM) ist ein Begriff, der von Programmierern, Mathematikern, Ingenieuren und anderen Fachleuten verwendet wird, um ein mathematisches Modell für ein beliebiges System zu beschreiben, das eine begrenzte Anzahl von bedingten Zuständen aufweist.
Ein praktisches Beispiel für einen endlichen Automaten ist eine Reihe von Tasten auf einem Videospiel-Controller, die mit einer bestimmten Reihe von Aktionen innerhalb des Spiels verbunden sind. Wenn ein Benutzer bestimmte Tasten drückt, weiß das System, dass es die entsprechenden Aktionen ausführen muss.
Der Aufbau eines endlichen Automaten besteht aus:
- 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 durch Software oder Hardware implementiert werden, um ein komplexes Problem zu vereinfachen. Bei einem endlichen Automaten sind alle in Frage kommenden Zustände in einer endlichen Liste enthalten, und der abstrakte Automat kann jeweils nur einen dieser Zustände annehmen. Mit diesem Ansatz kann jedes Eingabe- und Ausgabeszenario untersucht und getestet werden.
Ein endlicher Automat kann etwas 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 Automaten begrenzt. Alternativ dazu kann eine Zustandsmaschine auch unscharf sein. Ein unscharfer Automat lässt die Möglichkeit von Datenpunkten zu, die nicht in diskrete, vorher festgelegte Kategorien fallen.
Automatentheorie
Während das Wort Maschine traditionell eine physikalische Komponente beinhaltet, 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 Automaten: Modelle für jedes System mit einer begrenzten Anzahl von bedingten Zuständen des Seins.
- Pushdown Automata: Sie sind komplizierter als endliche Automaten 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-Maschinen: Das komplexeste mathematische Modell innerhalb der Automatentheorie zum Testen verschiedener Eingabekombinationen, um ein größeres System oder Problem zu analysieren.
Zustandsübergang
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 Automat mit Unterstützung einer Programmiersprache erstellt, und die Zustandsübergangsfunktionen werden ausgeführt. Darüber hinaus kann künstliche Intelligenz eingesetzt werden, um mit Mustererkennung und automatischen Modellen Daten über Systeme zu sammeln.
Bei einfacheren Problemen können dieselben Informationen in Tabellen, Matrizen, Abbildungen und Flussdiagrammen dargestellt werden, aber mit endlichen Automaten können Forscher größere und kompliziertere Szenarien modellieren. Diagramme von endlichen Automaten zeigen den logischen Fluss zwischen Eingabe- und Ausgabekombinationen, die in einem bestimmten Automaten auftreten können.
