Automat in der Informatik einfach erklärt

Stell dir einen Computer mit den Zuständen an und aus vor. Im Zustand „aus“ führt die Eingabe „hochfahren“ zum Zustand „an“. Im Zustand „an“ führt „herunterfahren“ zurück zu „aus“.

Eine Eingabe ist ein Zeichen oder Ereignis, auf das der Automat reagieren kann. Der Wechsel vom aktuellen zum nächsten Zustand heißt Übergang oder Transition.

Für einen einzelnen Schritt brauchst du daher drei Angaben:

1. den aktuellen Zustand,
2. die Eingabe,
3. die Regel für den Folgezustand.

Eine Ausgabe ist davon zu unterscheiden: Sie ist eine sichtbare Reaktion wie „Getränk ausgeben“. Nicht jeder Automat erzeugt Ausgaben. Ein reiner Akzeptor entscheidet nur, ob eine vollständige Eingabefolge gültig ist.

In einem Zustandsdiagramm werden Zustände als Kreise und Übergänge als beschriftete Pfeile dargestellt. Ein Pfeil ohne vorherigen Zustand markiert den Startzustand. Bei einem Akzeptor werden akzeptierende Zustände doppelt umrandet.

Eine Übergangstabelle enthält dieselben Regeln in anderer Form. Die Zeile nennt den aktuellen Zustand, die Spalte die Eingabe und das Tabellenfeld den Folgezustand.

Betrachte einen vereinfachten Getränkeautomaten. Die Zustände 0, 1 und 2 geben das vorhandene Guthaben in Euro an.

Aufgabe: Vom Tisch zum Diagramm

Zeichne für die drei Zustände 0, 1 und 2 je einen Kreis. Ergänze alle Übergänge der Eingabefolge „2 Euro, Geld zurück“.

Lösung

Der Startpfeil zeigt auf Zustand 0. Ein mit „2 Euro“ beschrifteter Pfeil führt von 0 nach 2. Ein zweiter Pfeil führt mit „Geld zurück“ von 2 nach 0. Damit stellst du dieselben Regeln wie in der Tabelle dar.

Ein deterministischer endlicher Automat, kurz DFA, befindet sich während einer Berechnung immer in genau einem Zustand. Für einen Zustand und ein Eingabezeichen gibt es höchstens einen möglichen Folgezustand.

Das Alphabet Σ enthält alle erlaubten Eingabezeichen. Ein Wort ist eine endliche Folge solcher Zeichen. Σ* bezeichnet die Menge aller Wörter über dem Alphabet, einschließlich des leeren Wortes ε.

Manche Definitionen verlangen, dass δ für jede Kombination aus Zustand und Zeichen einen Folgezustand liefert. Dann ist der DFA vollständig. Andere Darstellungen erlauben fehlende Übergänge und nennen den Automaten partiell.

Betrachte nun einen Akzeptor für vereinfachte Bezeichner. B steht für Buchstabe, Z für Ziffer.

• Zustände: Q = {0, 1}
• Startzustand: 0
• akzeptierende Zustände: F = {1}

Ein Akzeptor verarbeitet das Wort vollständig. Er akzeptiert es genau dann, wenn der danach erreichte Zustand in F liegt. Die Menge aller akzeptierten Wörter heißt die Sprache des Automaten.

Beim Bezeichnerautomaten ist das Muster leicht zu erkennen:

• Das erste Zeichen muss B sein.
• Danach dürfen beliebig viele B und Z folgen.
• Das leere Wort ε wird nicht akzeptiert, weil der Startzustand 0 nicht akzeptierend ist.

Die Sprache besteht also genau aus den nichtleeren Wörtern über {B, Z}, die mit B beginnen.

Was geschieht bei einem fehlenden Übergang?

Ein partieller DFA lässt manche Übergänge offen. Zur Vervollständigung ergänzt du einen nichtakzeptierenden Fehlerzustand f:

1. Jeder fehlende Übergang führt nach f.
2. In f führt jedes weitere Zeichen wieder nach f.

Beim Wort ZBB lautet die Zustandsfolge des vervollständigten Bezeichnerautomaten daher 0 → f → f → f. Das Wort bleibt abgelehnt. Der Fehlerzustand verändert also nicht die erkannte Sprache; er macht nur alle Übergänge ausdrücklich sichtbar.

Beim DFA gibt es für Zustand und Zeichen höchstens einen Folgezustand. Ein nichtdeterministischer endlicher Automat, kurz NFA, kann dagegen mehrere, einen oder keinen Folgezustand zulassen.

Für ein Eingabewort können dadurch mehrere mögliche Läufe entstehen. Der NFA akzeptiert das Wort, wenn mindestens ein vollständiger Lauf in einem akzeptierenden Zustand endet. Ein abgelehnter Lauf genügt nicht zur Ablehnung, solange ein anderer Lauf akzeptiert.

Manche NFAs besitzen zusätzlich ε-Übergänge. Sie wechseln den Zustand, ohne ein Zeichen der Eingabe zu verbrauchen. Solche Übergänge erleichtern Konstruktionen, machen NFAs aber nicht mächtiger als DFAs: Beide erkennen genau die regulären Sprachen.

Akzeptoren und Automaten mit Ausgabe

Ein Akzeptor beantwortet nach der vollständigen Eingabe eine Ja-nein-Frage: Wird das Wort akzeptiert?

Automaten mit Ausgabe erzeugen dagegen während ihrer Arbeit sichtbare Ergebnisse:

• Beim Mealy-Automaten hängt die Ausgabe vom aktuellen Zustand und der Eingabe beziehungsweise vom ausgeführten Übergang ab.
• Beim Moore-Automaten ist die Ausgabe einem Zustand zugeordnet.

Ein Automat reduziert ein System auf Zustände, Eingaben und Übergangsregeln. Bei Akzeptoren kommt die Entscheidung über vollständige Wörter hinzu. Übergangstabellen helfen dir, jeden Schritt nachvollziehbar zu prüfen.

Wenn du alle drei Fragen begründen kannst, kannst du Automatenregeln lesen, Eingaben verfolgen und die wichtigsten Automatenarten voneinander abgrenzen.