Automat in der Informatik einfach erklärt

Ein Automat ist in der Informatik ein Modell eines Rechners. Es ist zunächst egal, ob man ihn wirklich bauen könnte. Er ist stark vereinfacht, damit man sein Verhalten leichter versteht.

Dem Automaten wird von außen eine Eingabe gegeben. Das ist eine Folge von Zeichen. Der Automat befindet sich immer in einem bestimmten Zustand. Wenn ein Zeichen eintrifft, kann er in einen neuen Zustand wechseln. Der neue Zustand heißt Folgezustand. Der Wechsel heißt Übergang. Der Folgezustand hängt vom Zeichen und vom jetzigen Zustand ab.

Manche Automaten haben auch eine Ausgabe. Das ist eine Aktion, die in einer bestimmten Situation erfolgt, zum Beispiel ein Motor, der startet.

In Zeichnungen stehen Kreise für Zustände. Pfeile zwischen den Kreisen stehen für Übergänge.

Eine Übergangstabelle ist eine Tabelle, die zu den Zuständen und den Eingaben die Folgezustände auflistet. Sie ist eine Alternative zu einer Zeichnung mit Kreisen und Pfeilen.

So gehst du vor: Du beginnst in einem Zustand. Du liest das erste Zeichen. Du suchst in der Tabelle die Zeile mit diesem Zustand und diesem Zeichen. Dort steht der Folgezustand. Dann liest du das nächste Zeichen und machst es genauso weiter.

Die Tabelle unten zeigt einen Getränkeautomaten. Sie zeigt nur diese vier Übergänge.

Ein endlicher Automat kennt nur endlich viele Zustände. Ein Akzeptor ist ein endlicher Automat mit einem Startzustand und mit Endzuständen. Das Wort ist seine Eingabe.

Der Automat liest das Wort von links nach rechts, ein Zeichen nach dem anderen. Bei jedem Zeichen wechselt er den Zustand. Steht er nach dem letzten Zeichen in einem Endzustand, akzeptiert er das Wort. Steht er danach in einem Zustand, der kein Endzustand ist, gilt das Wort als verworfen.

Unterwegs darf der Automat einen Endzustand durchlaufen, ohne dort stoppen zu müssen. Das reicht nicht für das Akzeptieren. Es zählt der Zustand nach dem letzten Zeichen.

Bei einem deterministischen endlichen Automaten (DFA) gibt es für jeden Zustand genau einen Übergang für jede mögliche Eingabe. Der Folgezustand ist also eindeutig. Bei einem nichtdeterministischen endlichen Automaten (NFA) kann es für eine Eingabe keinen oder auch mehr als einen Übergang geben. Der NFA darf dann unter mehreren Möglichkeiten wählen. Ein DFA ist eine Sonderform des NFA.

Ein NFA akzeptiert ein Wort, wenn es für das Wort eine Folge von Zustandswechseln gibt, bei der er nicht vorzeitig stehen bleibt und der letzte Zustand ein Endzustand ist. Gibt es für ein Zeichen keinen Übergang, bleibt er vorzeitig stehen und verwirft die Eingabe.

Ein Akzeptor ist ein Automat mit Endzuständen. Er zeigt durch seinen Zustand, ob er das Wort akzeptiert. Daneben gibt es Automaten mit Ausgabe, die Transduktoren. Im Moore-Automaten hängt die Ausgabe nur vom Zustand ab. Im Mealy-Automaten hängt die Ausgabe vom Zustand und von der Eingabe ab. Die Aufzugtür von eben gibt es als Moore-Automat und als Mealy-Automat mit dem gleichen Verhalten.

Mealy-Automaten brauchen oft weniger Zustände. Ihre Funktion ist aber oft schwieriger zu verstehen. Wenn man das zeitliche Verhalten unberücksichtigt lassen kann, sind Moore- und Mealy-Automaten gleichwertig.