State machine

Eine Zustandsmaschine ist eine mathematische Abstraktion, die zur Gestaltung von Algorithmen verwendet wird. Eine Zustandsmaschine liest eine Reihe von Eingaben und wechselt basierend auf diesen Eingaben zu einem anderen Zustand.

Ein Zustand ist eine Beschreibung des Status eines Systems, das darauf wartet, eine Transition auszuführen. Eine Transition ist eine Reihe von Aktionen, die ausgeführt werden, wenn eine Bedingung erfüllt ist oder ein Ereignis empfangen wird. In einem Zustandsdiagramm repräsentieren Kreise jeden möglichen Zustand und Pfeile die Übergänge zwischen den Zuständen.

Anhand des Endzustands kann man etwas über die Reihe von Eingaben, die zu diesem Zustand geführt haben, erkennen.

Es gibt zwei Arten von grundlegenden Zustandsmaschinen:

deterministische endliche Zustandsmaschine

Diese Art erlaubt nur eine mögliche Transition für jede erlaubte Eingabe. Dies ähnelt der "if" Anweisung, in der if x then doThis else doThat nicht möglich ist. Der Computer muss eine der beiden Optionen ausführen.

nicht-deterministische endliche Zustandsmaschine

Bei einem gegebenen Zustand kann eine Eingabe zu mehr als einem unterschiedlichen Zustand führen.

Abbildung 1: Deterministische Endliche Zustandsmaschine.

In Abbildung 1 beginnt der Zustand in Zustand 1; der Zustand ändert sich zu Zustand 2 bei gegebener Eingabe 'X', oder zu Zustand 3 bei Eingabe 'Y'.

Abbildung 2: Nicht-Deterministische Endliche Zustandsmaschine.

In Abbildung 2 kann bei gegebener Eingabe 'X' der Zustand bestehen bleiben oder sich zu Zustand 2 ändern.

Beachten Sie, dass jeder reguläre Ausdruck durch eine Zustandsmaschine dargestellt werden kann.