Eine FSM (FiniteStateMachine, endlicher Automat) ist ein formales Modell, durch das sich viele Probleme der Informatik beschreiben lassen. In diesem Programm werden endliche Automaten zur Modellierung von Schaltwerken verwendet.
Ein Automat beschreibt ein System, das sich in einer aus einer endlichen Anzahl von internen Konfigurationen- sogenannten Zuständen befindet. Der Zustand des Systems umfaßt die Informationen, die sich aus den bisherigen Eingaben ergeben haben und die benötigt werden, um die Reaktion des Systems auf die noch folgenden Eingaben zu bestimmen [HU93]. Einer dieser Zustände wird als Startzustand definiert. Das System kann nun unter bestimmten Bedingungen den Zustand wechseln. So einen Zustandsübergang nennt man im Automatenmodell Transition. Graphisch stellt man Zustände durch Kreise und Transitionen durch Pfeile - beschriftet mit den Übergangsbedingungen - dar (siehe Abbildung).
Formal besteht ein Automat (A) aus einer endlichen Menge von Zuständen (Q), einem Eingabealphabet (I), einer Übergangsfunktion (d), einem Startzustand (q0) und einer Menge von Endzuständen (F).
Bei der Modellierung von Schaltnetzen entfällt die Menge der Endzuständen, da es hier nicht um das Akzeptieren von Wörtern, sondern um die Berechnung von Ausgabewerten und Zustandsübergängen geht. Das Eingabealphabet ist (0,1)n, wobei n die Anzahl der Eingänge ist.
| Beispiel: Q={Zustand 1, Zustand 2, Zustand 3} q0=Zustand 1 I=(0,1) (Werte für a) d(q,z)->(q') z.B.: d(Zustand 1, !a)->(Zustand_2) |
 |
Grundsätzlich gibt es deterministische und nicht-deterministische Automaten. Bei deterministischen Automaten sind die Übergänge immer eindeutig definiert, während es bei nicht-deterministischen mehrere Übergangsmöglichkeiten geben kann, von denen der Automat die richtige "raten" muß. Zum Entwurf von Schaltwerken werden nur deterministische Automaten verwendet, weshalb sie auch diesem Programm zugrunde liegen.
In JavaFSM wird nicht, wie im formalen Modell, eine einzige Übergangsfunktion angegeben. Stattdessen wird für jede Transition eine Übergangsbedingung festgelegt. Da es sich, wie oben erwähnt, um einen deterministischen Automaten handelt, ist jeweils genau eine der Transitionen aktiviert.
Im Chipdesign kommen endliche Automaten beim Design von getakteten Schaltwerken zum Einsatz, da sie die Umsetzung vieler elektronischer Funktionen, insbesondere Ablaufsteuerungen, stark vereinfachen. Um beim Entwurf unhandliche und fehleranfällige Logiktabellen zu vermeiden, bieten neuere Hardware-Beschreibungs-Sprachen deshalb oft direkte Syntax für endliche Automaten an.
