Endlicher Automat: Aufbau, Ablauf und Entwurf

Ein endlicher Automat ist ein Modell eines Verhaltens. Er besteht aus Zuständen, Zustandsübergängen und Aktionen (Aktionen brauchst du hier nicht weiter). „Endlich“ heißt: Die Menge der Zustände, die er annehmen kann, ist endlich. Wechselt er bei einer Eingabe immer in einen eindeutig bestimmten Folgezustand, heißt er deterministisch.

Die Bausteine: Ein Zustand sagt, in welcher Lage der Automat gerade ist. Er kann Information über die Vergangenheit enthalten, weil der Automat ihn auf seinem bisherigen Weg erreicht hat. Eine Eingabe ist ein erlaubtes Zeichen. Ein Übergang bringt den Automaten vom aktuellen Zustand in einen neuen. Dazu kommt es, wenn die angegebene Eingabe vorliegt. Der Startzustand ist der Zustand, in dem der Automat steht, bevor er etwas gelesen hat. Die Endzustände sind die akzeptierenden Zustände. Der nächste Zustand hängt vom aktuellen Zustand und von der Eingabe ab.

Ein Beispiel ist der Cola-Automat. Eine Flasche kostet 50 cent. Er nimmt Münzen zu 10, 20 und 50 cent an. Zur Vereinfachung gilt: Es muss genau bezahlt werden, es wird nur der Geldeinwurf für einen Bezahlvorgang betrachtet, und es gibt keinen Abbruch. Die Zustände sind die schon bezahlten Beträge: 0, 10, 20, 30, 40 und 50 cent. Die Eingaben sind die Münzen. Ein Übergang ist zum Beispiel: Zustand 30 cent, Einwurf 10 cent, neuer Zustand 40 cent. Der Startzustand ist 0 cent. Hier gibt es nur einen Endzustand, 50 cent. Es können aber auch mehrere Endzustände sein.

Ein zweites Beispiel ist ein einfacher Getränkeautomat mit drei Zuständen: q0 (wartet auf Münzeinwurf), q1 (wartet auf Getränkewahl) und q2 (Getränk wird ausgeschenkt). Seine Eingaben sind Münze, Getränk, Abbruch und Entnahme. Die Übergänge: Mit „Münze“ geht es von q0 nach q1. Mit „Getränk“ geht es von q1 nach q2. Mit „Entnahme“ geht es von q2 nach q0. Mit „Abbruch“ geht es von q1 nach q0. Hat man die Münze eingeworfen, aber noch kein Getränk gewählt, kann man also noch abbrechen.

Im Zustandsübergangsdiagramm stellen Kreise die Zustände dar, mit dem Namen im Kreis. Pfeile zwischen den Kreisen stellen die Übergänge dar. Auf jedem Pfeil steht, welche Bedingung den Übergang ermöglicht.

Eine Folge von Eingaben heißt Wort. Beim Cola-Automaten ist ein Wort eine Folge von Münzen, zum Beispiel 10 20 20. Der Automat liest das Wort von links nach rechts, ein Zeichen nach dem anderen. Vor dem ersten Zeichen steht er im Startzustand. Bei jedem Zeichen wechselt er den Zustand nach seinen Übergängen.

Beim Cola-Automaten rechnest du dafür: neuer Betrag = alter Betrag + Münze. Nach dem Lesen des letzten Zeichens schaust du, wo der Automat steht. Ist das ein Endzustand, akzeptiert er das Wort. Ist es kein Endzustand, gilt das Wort als verworfen.

Beispiel für ein verworfenes Wort beim Cola-Automaten: 10 10. Der Weg ist 0 → 10 → 20 cent. Der Zustand 20 cent ist kein Endzustand, also wird das Wort verworfen. Ein Automat kann während der Verarbeitung einen Endzustand durchlaufen, ohne dort stoppen zu müssen. Entscheidend ist der Zustand nach dem letzten Zeichen.

Die Wörter, die ein Automat akzeptiert, bilden zusammen seine Sprache. Eine Sprache ist also eine Menge von Wörtern. Nicht jede Münzfolge gehört zur Sprache, sondern nur die, die der Automat akzeptiert.

Um die Sprache in Worten zu beschreiben, fragst du: Welche Wörter führen vom Startzustand in einen Endzustand? Beim Cola-Automaten (Preis 50 cent, Münzen 10, 20 und 50 cent, genaue Zahlung, kein Abbruch) sind das alle Münzfolgen, die zusammen genau 50 cent ergeben. Es gibt neun solche Wörter.

Die Reihenfolge der Münzen gehört zum Wort. 10 10 10 20 und 20 10 10 10 sind deshalb zwei verschiedene Wörter der Sprache. Ein Wort wie 10 10 10 gehört nicht dazu: Es endet bei 30 cent.

Einen Automaten anzupassen heißt: Du überlegst, was die neue Regel an den Bausteinen ändert. Beim Cola-Automaten sind die Zustände die schon bezahlten Beträge. Der Start ist 0 cent. Der Endzustand ist der Betrag, der dem Preis entspricht. Ein Übergang rechnet alter Betrag plus Münze. Die Anpassungen hier sind ausgedachte Übungen, die nur dieses Prinzip anwenden.

Du gehst so vor: Erstens hältst du die Annahmen fest, zum Beispiel genaue Zahlung und kein Abbruch. Zweitens schreibst du die möglichen Beträge als Zustände auf. Drittens legst du den Endzustand fest. Viertens zeichnest du für jede erlaubte Münze die Pfeile. Pfeile, die über den Preis hinausführen, gibt es bei genauer Zahlung nicht.

Ändert sich der Preis, ändern sich der Endzustand und die Menge der Zustände. Werden Münzen gestrichen, fallen deren Pfeile weg. Ändert sich eine Annahme, ändert sich der Automat ebenfalls. Offene Fragen sind zum Beispiel: Was passiert, wenn Überbezahlung erlaubt ist? Was, wenn höchstens drei Münzen angenommen werden?

Auch beim Getränkeautomaten kann eine Regel fehlen. Soll es zu jedem Zustand und jeder Eingabe einen Übergang geben, brauchst du auch einen Zustand für den Abbruch, nachdem ein Getränk schon gewählt, aber noch nicht entnommen wurde.