Mit Google fortfahren
Endlicher Automat: Aufbau, Ablauf und Entwurf
Ein endlicher Automat beschreibt ein System mit endlich vielen Zuständen. Er liest Eingaben nacheinander, wechselt nach festen Regeln seinen Zustand und kann am Ende entscheiden, ob eine Eingabefolge akzeptiert wird.
Auf dieser Seite lernst du, einen Automaten zu lesen, Eingabewörter zu verfolgen, seine Sprache zu beschreiben und selbst ein einfaches Zustandsmodell zu entwerfen.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Woraus besteht ein endlicher Automat?
Stell dir einen Computer mit den Zuständen an und aus vor. Die Eingabe „herunterfahren“ führt von an nach aus. Die Eingabe „hochfahren“ führt zurück nach an. Genau solche zustandsabhängigen Wechsel bildet ein endlicher Automat ab.
Zustand
Ein Zustand fasst zusammen, was aus den bisherigen Eingaben für das weitere Verhalten wichtig ist. Der Automat befindet sich zu jedem Zeitpunkt in einem aktuellen Zustand.
Zu einem deterministischen erkennenden endlichen Automaten gehören fünf Bestandteile:
- Die Zustandsmenge $Q$ enthält alle möglichen Zustände.
- Das Eingabealphabet $\Sigma$ enthält alle erlaubten Eingabezeichen oder Ereignisse.
- Die Übergangsfunktion $\delta$ legt den Folgezustand für einen Zustand und eine Eingabe fest.
- Der Startzustand $q_0$ ist der Zustand vor der ersten Eingabe.
- Die Menge $F$ enthält die akzeptierenden Endzustände.
Kurz schreibt man:
$$A=(Q, \Sigma, \delta, q_0, F)$$
In einem Zustandsdiagramm werden Zustände als Kreise dargestellt. Ein Pfeil ohne Vorgänger kennzeichnet den Startzustand. Doppelt umrandete Kreise sind akzeptierende Zustände. Beschriftete Pfeile zeigen die Übergänge.
Ein Pfeil mit der Beschriftung $a$ von $q$ nach $r$ bedeutet: Befindet sich der Automat in $q$ und liest $a$, wechselt er nach $r$.
Eine Übergangstabelle enthält dieselben Informationen wie das Diagramm: Die Zeile nennt den aktuellen Zustand, die Spalte die Eingabe und das Tabellenfeld den Folgezustand.
Wie wird ein Eingabewort verarbeitet?
Ein Automat liest ein Wort von links nach rechts und Zeichen für Zeichen. Nach jedem Zeichen wird genau der Übergang benutzt, der zum aktuellen Zustand und zum gelesenen Zeichen gehört.
Betrachte einen Automaten für einfache Bezeichner:
- $Q=\{q_0,q_1\}$
- Startzustand: $q_0$
- akzeptierender Zustand: $q_1$
- $B$ steht für einen Buchstaben, $Z$ für eine Ziffer.
| Zustand | Eingabe $B$ | Eingabe $Z$ |
|---|---|---|
| $q_0$ | $q_1$ | nicht definiert |
| $q_1$ | $q_1$ | $q_1$ |
Verfolge das Wort $BZB$:
- Start in $q_0$.
- $B$ führt von $q_0$ nach $q_1$.
- $Z$ führt von $q_1$ wieder nach $q_1$.
- Das letzte $B$ führt ebenfalls nach $q_1$.
Die Zustandsfolge ist also:
$$q_0, q_1, q_1, q_1$$
Nach dem letzten Zeichen steht der Automat in $q_1$. Weil $q_1$ akzeptierend ist, wird $BZB$ akzeptiert.
Beim Wort $ZBB$ fehlt bereits für die erste Eingabe $Z$ ein Übergang aus $q_0$. Die Verarbeitung scheitert und das Wort wird abgelehnt.
Akzeptiert wird erst nach der vollständigen Verarbeitung des Wortes. Ein zwischenzeitlich erreichter Endzustand genügt nicht, wenn danach noch Zeichen folgen.
Wie beschreibt ein Automat eine Sprache?
Ein einzelnes Eingabewort ist nur eine Zeichenfolge. Die Sprache eines Automaten ist die Menge aller Wörter, die er akzeptiert.
Akzeptierte Sprache
Die akzeptierte Sprache $L(A)$ enthält genau die Wörter, nach deren vollständiger Verarbeitung der Automat in einem Zustand aus $F$ steht.
Der Bezeichner-Automat aus dem vorigen Kapitel akzeptiert genau:
- nichtleere Wörter,
- die mit einem Buchstaben beginnen,
- und danach beliebig viele Buchstaben oder Ziffern enthalten.
Beispiele:
| Wort | Ergebnis | Begründung |
|---|---|---|
| $B$ | akzeptiert | Das Wort endet nach dem ersten Übergang in $q_1$. |
| $BZBZ$ | akzeptiert | Nach dem ersten $B$ bleiben alle weiteren Zeichen in $q_1$. |
| $ZB$ | abgelehnt | Für $Z$ gibt es aus $q_0$ keinen Übergang. |
| leeres Wort | abgelehnt | Ohne Eingabe bleibt der Automat im nicht akzeptierenden Zustand $q_0$. |
Beim Beschreiben einer Sprache reicht es nicht, einzelne akzeptierte Wörter aufzuzählen. Suche stattdessen nach der gemeinsamen Regel aller akzeptierten Wörter.
Wie entwirfst du einen Automaten?
Beginne nicht sofort mit Pfeilen. Kläre zuerst, welche Information das System nach jeder Eingabe behalten muss.
Gehe in fünf Schritten vor:
- Lege die Aufgabe und die erlaubten Eingaben fest.
- Frage, welche Situationen sich im weiteren Verhalten unterscheiden.
- Formuliere für jede solche Situation einen Zustand.
- Bestimme für jeden Zustand die möglichen Übergänge.
- Prüfe typische Eingabefolgen vom Start bis zum Ende.
Deine Entwurfsaufgabe
Ein vereinfachter Verkaufsautomat soll diesen Ablauf darstellen:
- Zu Beginn wartet er auf die Bezahlung.
- Nach dem Bezahlen wartet er auf die Warenauswahl.
- Nach der Auswahl gibt er die Ware aus und wartet auf die Entnahme.
- Nach der Entnahme ist er wieder bereit.
- Nach dem Bezahlen kann der Kauf abgebrochen werden.
Entwirf dafür einen Automaten. Lege mindestens drei Zustände fest, gib jedem Zustand eine eindeutige Bedeutung und wähle kurze Zeichen für die Eingaben bezahlen, auswählen, entnehmen und abbrechen. Erstelle anschließend eine Übergangstabelle und ein Zustandsdiagramm.
Lösung zur Selbstkontrolle
Eine passende Lösung verwendet diese drei Zustände:
- $w$: auf Bezahlung warten
- $a$: bezahlt, auf Auswahl warten
- $r$: Ware ausgegeben, auf Entnahme warten
Die Eingaben sind $p$ für bezahlen, $s$ für auswählen, $t$ für entnehmen und $c$ für abbrechen.
| Aktueller Zustand | Eingabe | Folgezustand |
|---|---|---|
| $w$ | $p$ | $a$ |
| $a$ | $s$ | $r$ |
| $a$ | $c$ | $w$ |
| $r$ | $t$ | $w$ |
Dein Diagramm braucht entsprechend diese vier Pfeile:
- $w$ führt mit $p$ zu $a$.
- $a$ führt mit $s$ zu $r$.
- $a$ führt mit $c$ zu $w$.
- $r$ führt mit $t$ zu $w$.
Der normale Kauf hat die Zustandsfolge:
$$w \rightarrow a \rightarrow r \rightarrow w$$
Der Abbruch nach dem Bezahlen verläuft dagegen von $w$ über $a$ zurück nach $w$.
Andere Zustandsnamen und Eingabezeichen sind ebenfalls richtig, wenn ihre Bedeutung eindeutig ist und sie genau dieses Verhalten abbilden.
Was bedeuten deterministisch, vollständig und nichtdeterministisch?
Bei einem deterministischen endlichen Automaten, kurz DEA oder DFA, ist für einen Zustand und ein Eingabezeichen höchstens ein Folgezustand möglich. Der nächste Schritt ist daher eindeutig.
Viele Definitionen verlangen zusätzlich für jedes Paar aus Zustand und Eingabe einen Übergang. Ein solcher Automat heißt vollständig. Andere Darstellungen erlauben fehlende Übergänge und sprechen von einem partiellen deterministischen Automaten.
Fehlende Übergänge lassen sich durch einen nicht akzeptierenden Fehlerzustand ergänzen. Jeder bisher fehlende Übergang führt dorthin. Von dort führen alle Eingaben wieder in den Fehlerzustand. Dadurch wird die Übergangsfunktion vollständig, ohne dass zusätzliche Wörter akzeptiert werden.
Bei einem nichtdeterministischen endlichen Automaten, kurz NEA oder NFA, kann dieselbe Eingabe aus einem Zustand zu mehreren möglichen Folgezuständen führen. Ein Wort wird akzeptiert, wenn mindestens ein vollständiger möglicher Lauf in einem akzeptierenden Zustand endet.
Deterministische und nichtdeterministische endliche Automaten erkennen dieselbe Klasse von Sprachen: die regulären Sprachen. Nichtdeterminismus kann einen Entwurf vereinfachen, erhöht aber nicht die grundsätzliche Ausdrucksmächtigkeit.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Endlicher Automat
- Aufbau: Zustände, Alphabet, Übergänge, Startzustand und Endzustände
- Verarbeitung: Eingabe Zeichen für Zeichen lesen
- Entscheidung: Endzustand nach dem letzten Zeichen prüfen
- Sprache: alle akzeptierten Wörter gemeinsam beschreiben
- Entwurf: relevante Situationen als Zustände modellieren
- Determinismus: eindeutiger Folgezustand für Zustand und Eingabe
- Vervollständigung: fehlende Übergänge zum Fehlerzustand führen
Abschluss-Check
Du beherrschst den Kern, wenn du bei einem Automaten drei Dinge sicher trennen kannst: Welche Eingabe wird gelesen? In welchen Zustand führt sie? Warum bedeutet der letzte Zustand Akzeptanz oder Ablehnung?