Zustandsautomat

Ein Zustandsautomat ist eine mathematische Abstraktion, die zur Erstellung von Algorithmen verwendet wird. Ein Zustandsautomat liest eine Menge von Eingaben und wechselt je nach diesen Eingaben in einen anderen Zustand.

Ein Zustand ist eine Beschreibung des Status eines Systems, das auf die Ausführung eines Übergangs wartet. Ein Übergang ist eine Reihe von Aktionen, die ausgeführt werden, wenn eine Bedingung erfüllt ist oder ein Ereignis empfangen wird. In einem Zustandsdiagramm stehen Kreise für jeden möglichen Zustand, und Pfeile repräsentieren Übergänge zwischen Zuständen.

Indem Sie den Endzustand betrachten, können Sie etwas über die Reihe von Eingaben ableiten, die zu diesem Zustand geführt haben.

Es gibt zwei Arten von grundlegenden Zustandsautomaten:

deterministischer endlicher Zustandsautomat

Diese Art erlaubt nur einen möglichen Übergang für jede erlaubte Eingabe. Dies ist wie die "if" Anweisung, in der if x then doThis else doThat nicht möglich ist. Der Computer muss eine der beiden Optionen ausführen.

nicht-deterministischer endlicher Zustandsautomat

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

Abbildung 1: Deterministischer Endlicher Zustandsautomat.

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

Abbildung 2: Nicht-Deterministischer Endlicher Zustandsautomat.

In Abbildung 2 kann der Zustand bei Eingabe 'X' entweder bestehen bleiben oder zu Zustand 2 wechseln.

Beachten Sie, dass jeder reguläre Ausdruck durch einen Zustandsautomaten dargestellt werden kann.