Theoretische Informatik
Automaten und Zustandsdiagramme
Warum eine Ampel, ein Getränkeautomat und eine Passwortprüfung dieselbe Struktur haben: Zustände, Eingaben, Übergänge.
Benötigte Grundlagen
Diese Themen kommen in diesem Kapitel vor und wurden vorher schon erklärt. Wenn dir eines davon unsicher vorkommt, frisch es kurz auf, sonst leg direkt los.
Einführung
Du drückst am Getränkeautomaten die Taste für Cola. Manchmal kommt eine Cola, manchmal passiert gar nichts.
Dieselbe Taste, dasselbe Gerät, verschiedenes Verhalten. Das ist kein Defekt. Der Automat reagiert nicht nur auf die Eingabe, sondern auch darauf, in welcher Lage er sich gerade befindet: Ist schon genug Geld eingeworfen oder nicht?
Diese Lage nennt man Zustand, und die Beobachtung dahinter ist eines der mächtigsten Werkzeuge der Informatik. Erstaunlich viele Dinge lassen sich vollständig beschreiben, indem man ihre Zustände auflistet und angibt, welche Eingabe von welchem Zustand wohin führt.
Das kannst du nach diesem Kapitel
den Begriff Automat definieren und seine Bestandteile benennen.
ein Zustandsdiagramm lesen und den Weg einer Eingabefolge verfolgen.
für einen Alltagsvorgang selbst ein Zustandsdiagramm entwerfen.
ein Diagramm in eine Übergangstabelle übersetzen und umgekehrt.
erklären, was ein Automat nicht kann, und begründen warum.
Warum dieselbe Eingabe Verschiedenes bewirkt
Sehen wir uns den Getränkeautomaten genau an. Die Cola kostet 1 Euro, eingeworfen werden können 50-Cent-Stücke.
Drückt man die Taste, hängt das Ergebnis davon ab, wie viel Geld schon im Automaten ist:
- 0 Euro eingeworfen → nichts passiert
- 50 Cent eingeworfen → nichts passiert
- 100 Cent eingeworfen → Cola kommt heraus
Der Automat muss sich also merken, wie viel schon da ist. Diese gemerkte Lage ist der Zustand. Hier gibt es drei davon, und man kann sie benennen: „leer“, „halb bezahlt“, „bezahlt“.
Damit ist das ganze Verhalten beschreibbar, ohne ein einziges Wort über Elektronik zu verlieren.
Die Ampel als Automat
Alle vier Pfeile tragen dieselbe Beschriftung, und trotzdem passiert jedes Mal etwas anderes. Das ist der ganze Gedanke hinter dem Wort Zustand: Was eine Eingabe bewirkt, hängt nicht nur von ihr ab, sondern davon, wo man gerade steht. Deshalb kann man eine Ampel nicht durch eine Regel der Form „wenn Zeit um, dann grün“ beschreiben, sondern nur durch vier Regeln: eine je Zustand.
Die Bestandteile eines Automaten
Ein endlicher Automat besteht aus:
- einer endlichen Menge von Zuständen
- einem Startzustand, in dem er beginnt
- einer Menge möglicher Eingaben (dem Eingabealphabet)
- den Übergängen: Zu jedem Paar aus Zustand und Eingabe ist festgelegt, in welchen Zustand gewechselt wird
- oft zusätzlich Endzuständen, die einen erfolgreichen Abschluss kennzeichnen
Das Wort endlich ist dabei nicht schmückend. Es bedeutet, dass der Automat sich nur eine feste, begrenzte Zahl von Lagen merken kann, und daraus folgt später genau, was er nicht kann.
Das Zustandsdiagramm
Gezeichnet wird das so:
- Kreise sind Zustände, beschriftet mit ihrem Namen.
- Ein Pfeil von außen zeigt auf den Startzustand.
- Pfeile zwischen Kreisen sind Übergänge; darüber steht die Eingabe, die sie auslöst.
- Doppelkreise sind Endzustände.
Für unseren Automaten:
50ct 50ct
→(leer) ──→ (halb) ──→ ((bezahlt))
↑ │
└────────────────────────┘
Taste
Gelesen: Im Zustand „leer“ führt ein 50-Cent-Stück nach „halb“, von dort ein weiteres nach „bezahlt“. Im Zustand „bezahlt“ führt die Taste zurück nach „leer“, und dabei kommt die Cola heraus.
Beachte, was im Zustand „leer“ beim Drücken der Taste passiert: nichts. Genauer, der Automat bleibt in „leer“. Solche Selbstübergänge gehören dazu und werden als Pfeil gezeichnet, der zum selben Kreis zurückführt. Sie sind kein Versehen, sondern die Antwort auf die Frage „und was, wenn jemand hier diese Eingabe macht?“.
Der Getränkeautomat
Die Zahl im Kreis ist der bereits eingeworfene Betrag in Cent. Drei Bestandteile sind im Bild: die Zustände als Kreise, die Eingaben an den Pfeilen, 50 heißt „eine 50-Cent-Münze eingeworfen“, Ware heißt „das Getränk fällt heraus“ und die Übergänge als Pfeile. Der Startpfeil von außen zeigt, wo der Automat morgens steht; der Doppelkreis, wann ausgegeben werden darf. Wirf gedanklich eine einzelne Münze ein und suche den Weg: Von aus gibt es keinen Pfeil mit Ware, und genau deshalb passiert nichts.
Die Übergangstabelle
Dasselbe lässt sich als Tabelle schreiben, mit einer Zeile je Zustand und einer Spalte je Eingabe:
| Zustand | Eingabe 50ct | Eingabe Taste |
|---|---|---|
| leer | halb | leer |
| halb | bezahlt | halb |
| bezahlt | bezahlt | leer (Cola) |
Die Tabelle ist gleichwertig zum Diagramm und hat einen praktischen Vorteil: Sie zwingt dazu, jede Kombination auszufüllen. Genau dort fallen vergessene Fälle auf, die im Diagramm leicht untergehen.
Beachte die Zeile „bezahlt“ bei Eingabe 50ct: Der Automat bleibt in „bezahlt“. Das ist eine bewusste Entscheidung, kein Zufall; man könnte auch das Geld zurückgeben. Ein Automat ist immer ein Modell, und jede Zelle der Tabelle ist eine Festlegung, die man verantworten muss.
Dasselbe als Tabelle
Diese Tabelle enthält exakt dieselbe wie das Diagramm: drei Pfeile, drei Zeilen. Und trotzdem braucht man beide. Die Tabelle beantwortet zuverlässig „was passiert von hier aus?“ und lässt sich direkt in Programmcode übersetzen. Die Frage „komme ich von hier jemals wieder zum Anfang zurück?“ liest man dagegen nur im Diagramm ab. Sie ist eine Frage nach Wegen, und Wege sieht man in einem Graphen.
Warum das so nützlich ist
Der Automatenbegriff passt auf verblüffend viele Dinge:
- Ampel: Zustände rot, rot-gelb, grün, gelb; Eingabe ist der Zeittakt.
- Passworteingabe: Zustände „wartet“, „ein Versuch falsch“, „zwei Versuche falsch“, „gesperrt“.
- Türschloss mit Zahlencode: ein Zustand je richtig eingegebener Teilfolge.
- Spielfigur: steht, läuft, springt, fällt.
- Textprüfung: Ist diese Zeichenfolge eine gültige E-Mail-Adresse?
Der gemeinsame Kern ist immer derselbe: Das Verhalten hängt nicht nur von der aktuellen Eingabe ab, sondern auch von der Vorgeschichte, und diese Vorgeschichte steckt vollständig im Zustand. Man muss sich nicht merken, was alles passiert ist, sondern nur, wo man gelandet ist.
Ein Zahlenschloss mit dem Code 1 3 7
Hier ist der Automat mitten im Lauf: Zwei Ziffern sind gelesen (grün), die dritte steht noch aus, und der dick umrandete Zustand sagt, wo er gerade steht. Die vier Zustände heißen der Reihe nach „noch nichts richtig“, „die 1 stimmt“, „1 und 3 stimmen“ und, als Doppelkreis, „offen“. Verfolge es selbst: Die führt von nach , die weiter nach , und die öffnet das Schloss. Was das Bild nicht zeigt: Von jedem der drei linken Zustände führt außerdem eine Kante „jede andere Ziffer“ in einen Sperrzustand, aus dem keine Eingabe mehr herausführt. Sie ist weggelassen, damit die vier Wege lesbar bleiben, im Heft gehört sie dazu.
Was ein endlicher Automat nicht kann
Und jetzt die Grenze, die dem Begriff seine Schärfe gibt.
Ein endlicher Automat hat endlich viele Zustände. Er kann sich also nur endlich viele verschiedene Lagen merken. Das genügt nicht immer.
Beispiel: Ein Automat soll prüfen, ob in einer Zeichenfolge gleich viele öffnende wie schließende Klammern stehen. Dazu müsste er mitzählen, wie viele noch offen sind. Diese Zahl ist unbegrenzt: Es könnten drei sein, dreißig oder dreitausend. Für jede mögliche Anzahl bräuchte er einen eigenen Zustand, und davon gibt es unendlich viele.
Also kann kein endlicher Automat diese Aufgabe lösen. Das ist keine Frage der Anstrengung oder besserer Technik, sondern folgt direkt aus der Endlichkeit.
Merke dir die Prüffrage: Muss ich unbegrenzt weit zählen oder mich an beliebig viel erinnern? Wenn ja, reicht ein endlicher Automat nicht. Was dann nötig ist und wo die nächste Grenze liegt, ist Thema der Qualifikationsphase.
Eine Ampel als Automat
Beschreibe eine deutsche Ampel als Automaten und zeichne das Diagramm.
- 1
Zustände sammeln: rot, rot-gelb, grün, gelb. Das sind alle Lagen, in denen die Ampel sein kann.
- 2
Startzustand: rot. Beim Einschalten beginnt die Ampel dort, das ist die sichere Ausgangslage.
- 3
Eingabe: hier gibt es nur eine, den Zeittakt „Zeit abgelaufen“. Ein Automat braucht nicht mehrere Eingaben.
- 4
Übergänge: Jede Phase folgt auf genau eine andere.
→(rot) ──→ (rot-gelb) ──→ (gruen) ──→ (gelb) ──┐ ↑ │ └────────────────────────────────────────────┘ - 5
Endzustände: keine. Eine Ampel soll nie fertig werden; sie läuft im Kreis. Das ist erlaubt, denn Endzustände sind optional.
- 6
Die Nützlichkeit zeigt sich beim Prüfen: Am Diagramm sieht man sofort, dass es keinen Pfeil von rot direkt nach grün gibt. Wäre einer da, wäre die Ampel gefährlich, und man hätte es beim bloßen Programmieren womöglich übersehen.
Vier Zustände in einem Kreis, ein Startzustand rot, eine Eingabe, keine Endzustände.
Eine Eingabefolge verfolgen
Ein Automat prüft Passwortversuche: Zustände „offen“, „1 Fehler“, „2 Fehler“, „gesperrt“. Jeder Fehlversuch geht eine Stufe weiter, ein richtiger Versuch führt zurück nach „offen“. Wo landet man bei der Folge: falsch, falsch, richtig, falsch, falsch, falsch?
- 1
Start in offen. Eingabe falsch → 1 Fehler.
- 2
Eingabe falsch → 2 Fehler.
- 3
Eingabe richtig → zurück nach offen. Der Zähler wird also zurückgesetzt.
- 4
Eingabe falsch → 1 Fehler. Eingabe falsch → 2 Fehler. Eingabe falsch → gesperrt.
- 5
Das Ergebnis ist bemerkenswert: Insgesamt gab es fünf Fehlversuche, gesperrt wird aber erst nach dreien in Folge. Genau diese Regel steckt im Diagramm, ohne dass sie irgendwo als Satz aufgeschrieben wäre; sie ergibt sich aus dem Rückweg nach „offen“.
Endzustand gesperrt. Das Diagramm zählt aufeinanderfolgende Fehler, nicht alle Fehler.
Typischer Fehler
„Für jede Situation brauche ich einen eigenen Zustand, also braucht der Getränkeautomat einen Zustand je möglichem Geldbetrag.“
Der Gedanke wirkt gründlich und führt in eine Sackgasse. Zustände sind teuer: Ein Automat mit hundert Zuständen ist weder zeichenbar noch prüfbar.
Die richtige Frage lautet nicht „welche Situationen gibt es?“, sondern: „Welche Unterschiede ändern das Verhalten?“
Beim Getränkeautomaten mit einem Preis von 1 Euro und 50-Cent-Stücken gibt es genau drei verhaltensrelevante Lagen: noch nichts, die Hälfte, genug. Ob jemand vorher lange überlegt hat oder welche Münze zuerst kam, ändert nichts und gehört deshalb nicht in den Zustand.
Umgekehrt darf man auch nicht zu wenige nehmen. Fasste man „leer“ und „halb“ zu einem Zustand „noch nicht bezahlt“ zusammen, wüsste der Automat beim nächsten 50-Cent-Stück nicht, ob er nun bei 50 oder bei 100 Cent steht.
Die Prüfung ist einfach und funktioniert immer: Zwei Lagen dürfen genau dann zusammenfallen, wenn bei jeder möglichen Eingabe dasselbe passiert. Unterscheidet sich auch nur eine Reaktion, sind es zwei Zustände.
Übung 1
leicht
Ein Lichtschalter im Flur hat zwei Zustände: aus und an. Jeder Druck wechselt den Zustand.
a) Zeichne das Zustandsdiagramm in Worten (Zustände, Startzustand, Eingabe, Übergänge). b) Stelle die Übergangstabelle auf. c) In welchem Zustand ist das Licht nach 7 Drücken, wenn es aus war?
Tipp anzeigen
Zu c): Achte auf gerade und ungerade Anzahl.
Lösung anzeigen
a) Zustände: aus, an. Startzustand: aus. Eingabe: Druck. Übergänge: aus → an bei Druck, an → aus bei Druck.
b) Übergangstabelle:
| Zustand | Eingabe Druck |
|---|---|
| aus | an |
| an | aus |
c) Nach jedem Druck wechselt der Zustand. Bei einer ungeraden Anzahl landet man im anderen Zustand als am Anfang, bei einer geraden im selben. 7 ist ungerade, also ist das Licht an.
Detaillierte Schritterklärung anzeigen
Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.
✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.
- 1
a) Die vier Bestandteile eines Automaten benennen
Ein Automat besteht aus Zuständen (hier: aus, an), einem Startzustand (aus), einer Eingabe (Druck) und den Übergängen: aus wird bei Druck zu an, an wird bei Druck zu aus. Mehr braucht es nicht, und genau das ist die Aussage.
- 2
b) Die Übergangstabelle: dieselbe Aussage in Zeilen und Spalten
Die Tabelle hat je Zustand eine Zeile und je Eingabe eine Spalte; in der Zelle steht der Folgezustand. Zeile „aus“, Spalte „Druck“ ergibt „an“; Zeile „an“, Spalte „Druck“ ergibt „aus“. Sie enthält genau dieselbe wie das Diagramm.
- 3
c) Sieben Drücke: die Regel finden statt sieben Schritte zu gehen
Man kann sieben Übergänge einzeln verfolgen, aber schneller ist die Regel: Jeder Druck wechselt den Zustand, also landet man bei ungerader Anzahl im anderen Zustand als am Anfang, bei gerader im selben. 7 ist ungerade, das Licht ist also an.
, also einmal wechseln
Zwischenergebnis
Das Licht ist an.
Übung 2
mittelEine Drehtür an einem Schwimmbad öffnet nur nach Einwurf eines Tokens. Zustände: „gesperrt“ und „frei“. Eingaben: „Token“ und „Durchgang“.
a) Stelle die vollständige Übergangstabelle auf, auch für die scheinbar unsinnigen Kombinationen. b) Was soll passieren, wenn im Zustand „frei“ ein weiteres Token eingeworfen wird? Nenne zwei mögliche Entscheidungen und ihre Folgen. c) Verfolge die Eingabefolge: Durchgang, Token, Token, Durchgang, Durchgang. d) Erweitere den Automaten so, dass zwei Personen mit zwei Token nacheinander durchgehen können.
Tipp anzeigen
Zu a): Es gibt 2 Zustände und 2 Eingaben, also vier Zellen. Keine darf leer bleiben.
Lösung anzeigen
a) Übergangstabelle:
| Zustand | Eingabe Token | Eingabe Durchgang |
|---|---|---|
| gesperrt | frei | gesperrt |
| frei | frei | gesperrt |
b) Möglichkeit 1: Der Automat bleibt in „frei“. Das Token verfällt; der Automat ist einfach, der Gast verliert Geld. Möglichkeit 2: Der Automat merkt sich das zweite Token und lässt zwei Durchgänge zu. Das ist gerechter, verlangt aber einen zusätzlichen Zustand. Wichtig ist die Einsicht, dass beide Varianten korrekte Automaten sind: Die Entscheidung ist eine Modellentscheidung, keine technische Notwendigkeit.
c) Start in gesperrt. Durchgang → gesperrt (nichts passiert). Token → frei. Token → frei (das zweite verfällt). Durchgang → gesperrt. Durchgang → gesperrt. Endzustand: gesperrt, und ein Token ist verloren.
d) Ein dritter Zustand kommt hinzu: „frei für zwei“.
| Zustand | Token | Durchgang |
|---|---|---|
| gesperrt | frei | gesperrt |
| frei | frei für zwei | gesperrt |
| frei für zwei | frei für zwei | frei |
Das dritte Token verfällt weiterhin. Wollte man beliebig viele Token sammeln, bräuchte man beliebig viele Zustände, und genau das kann ein endlicher Automat nicht.
Detaillierte Schritterklärung anzeigen
Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.
✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.
- 1
Teil a): Die Tabelle zwingt zur Vollständigkeit
Bei 2 Zuständen und 2 Eingaben gibt es Kombinationen. Jede braucht einen Eintrag, auch die, die man für unsinnig hält. „Da macht doch niemand etwas“ ist keine Festlegung, und ein Automat muss auf jede Eingabe reagieren.
2\ \text{Zustände} \times 2\ \text{Eingaben} = 4\ \text{Zellen}
Zwischenergebnis
Vier Zellen, keine darf leer bleiben.
Genau hier liegt der Vorteil der Tabelle gegenüber dem Diagramm: Ein fehlender Pfeil fällt beim Zeichnen kaum auf, eine leere Zelle sofort.
- 2
Teil a): die unscheinbaren Zellen füllen
„Durchgang im Zustand gesperrt“ heißt: Jemand drückt gegen die Tür, sie gibt nicht nach. Der Zustand ändert sich nicht, also ist der Eintrag „gesperrt“. Das ist ein Übergang auf sich selbst.
Zwischenergebnis
gesperrt + Durchgang → gesperrt
- 3
Teil c): Die Folge Schritt für Schritt verfolgen
Man beginnt im Startzustand und liest für jede Eingabe die passende Zelle ab. Wichtig ist, die Zwischenzustände mitzuschreiben; im Kopf verliert man nach vier Schritten den Faden.
\text{gesperrt} \xrightarrow{D} \text{gesperrt} \xrightarrow{T} \text{frei} \xrightarrow{T} \text{frei} \xrightarrow{D} \text{gesperrt} \xrightarrow{D} \text{gesperrt}
Zwischenergebnis
Endzustand gesperrt; das zweite Token ist verfallen.
- 4
Teil d): Warum ein Zustand mehr genügt und warum nicht beliebig viele
Um zwei Durchgänge zu erlauben, muss der Automat unterscheiden können, ob noch einer oder noch zwei offen sind. Das sind zwei verschiedene Lagen, also zwei Zustände.
Zwischenergebnis
Drei Zustände: gesperrt, frei, frei für zwei.
Übung 3
schwera) Entwirf einen Automaten, der prüft, ob eine Folge aus den Zeichen a und b mit ab endet. Gib Zustände, Start, Endzustand und Übergangstabelle an. b) Verfolge die Eingaben aabab und abba. c) Begründe, warum kein endlicher Automat prüfen kann, ob in einer Zeichenfolge gleich viele a wie b vorkommen. d) Erkläre, warum die Aussage aus c) durch schnellere Rechner nicht widerlegt wird.
Tipp anzeigen
Zu a): Der Automat muss sich merken, ob das zuletzt gelesene Zeichen ein a war.
Lösung anzeigen
a) Der Automat muss nur wissen, was zuletzt kam. Drei Zustände genügen:
S0 (nichts Passendes zuletzt), S1 (zuletzt ein a), S2 (zuletzt ab, Endzustand). Start: S0. Endzustand: S2.
| Zustand | Eingabe a | Eingabe b |
|---|---|---|
| S0 | S1 | S0 |
| S1 | S1 | S2 |
| S2 | S1 | S0 |
Die Zeile S2 ist die wichtigste: Nach einem gefundenen „ab“ geht es normal weiter, denn es kommen ja noch Zeichen. Nur wo der Automat am Ende der Eingabe steht, entscheidet.
b) aabab: S0 →a S1 →a S1 →b S2 →a S1 →b S2. Ende in S2, also akzeptiert. abba: S0 →a S1 →b S2 →b S0 →a S1. Ende in S1, also abgelehnt. Stimmt, denn abba endet auf ba.
c) Der Automat müsste den Unterschied zwischen der Anzahl der a und der Anzahl der b mitführen. Dieser Unterschied kann jeden Wert annehmen: bei aaa ist er 3, bei tausend a ist er 1000. Für jeden möglichen Wert bräuchte der Automat einen eigenen Zustand, um ihn von den anderen unterscheiden zu können, also unendlich viele. Ein endlicher Automat hat aber nur endlich viele Zustände. Damit gäbe es zwei verschiedene Differenzen, die in denselben Zustand fallen, und ab da könnte der Automat sie nie wieder auseinanderhalten.
d) Weil die Aussage keine über Geschwindigkeit ist, sondern über die Bauart des Modells. Ein endlicher Automat kann sich nur endlich viele Lagen merken; das ist seine Definition und nicht eine Frage seiner Taktrate. Ein schnellerer Rechner führt Übergänge schneller aus, gibt dem Automaten aber keinen einzigen Zustand mehr. Wer unbegrenzt zählen will, braucht ein anderes Modell, keinen schnelleren.
Detaillierte Schritterklärung anzeigen
Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.
✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.
- 1
a) Zuerst fragen: Was muss sich der Automat merken?
Der Automat kann sich nur seinen Zustand merken. Für „endet auf ab“ genügt zu wissen, was zuletzt kam: nichts Passendes (S0), zuletzt ein a (S1), zuletzt ab (S2, Endzustand). Drei Zustände reichen also, Start ist S0.
- 2
a) Die Übergangstabelle vollständig füllen, besonders die Endzustandszeile
Aus S0 führt a nach S1, b bleibt in S0. Aus S1 führt a nach S1 (das neue a ist jetzt das letzte), b nach S2. Aus S2 führt a nach S1 und b nach S0. Die letzte Zeile ist die wichtigste: Nach einem gefundenen „ab“ geht es normal weiter, denn es kommen ja noch Zeichen.
- 3
b) Beide Eingaben Zeichen für Zeichen verfolgen
aabab: S0 →a S1 →a S1 →b S2 →a S1 →b S2. Ende in S2, also akzeptiert. abba: S0 →a S1 →b S2 →b S0 →a S1. Ende in S1, also abgelehnt, und das stimmt, denn abba endet auf ba.
- 4
c) Warum gleich viele a wie b kein endlicher Automat prüfen kann
Der Automat müsste den Unterschied zwischen der Anzahl der a und der b mitführen. Dieser Unterschied kann jeden Wert annehmen, bei tausend a ist er 1000. Für jeden Wert bräuchte es einen eigenen Zustand, also unendlich viele. Ein endlicher Automat hat nur endlich viele; zwei verschiedene Differenzen fielen also in denselben Zustand und wären danach nie wieder unterscheidbar.
- 5
d) Warum schnellere Rechner daran nichts ändern
Weil die Aussage keine über Geschwindigkeit ist, sondern über die Bauart des Modells. Ein endlicher Automat kann sich nur endlich viele Lagen merken; das ist seine Definition, nicht eine Frage seiner Taktrate. Ein schnellerer Rechner führt Übergänge schneller aus, gibt dem Automaten aber keinen einzigen Zustand mehr.
Zusammenfassung
Ein endlicher Automat beschreibt Systeme, deren Verhalten nicht nur von der Eingabe abhängt, sondern auch von einer gemerkten Lage, dem Zustand. Er besteht aus endlich vielen Zuständen, einem Startzustand, möglichen Eingaben und den Übergängen, die zu jedem Paar aus Zustand und Eingabe den Folgezustand festlegen; Endzustände sind optional. Dargestellt wird er als Zustandsdiagramm mit Kreisen und beschrifteten Pfeilen oder als Übergangstabelle, die zur Vollständigkeit zwingt. Zustände findet man nicht, indem man Situationen zählt, sondern indem man fragt, welche Unterschiede das Verhalten ändern; zwei Lagen dürfen genau dann zusammenfallen, wenn jede Eingabe dasselbe bewirkt. Die Endlichkeit ist die entscheidende Eigenschaft: Ein solcher Automat kann jede feste Obergrenze abbilden, aber niemals unbegrenzt zählen, und daran ändert auch kein schnellerer Rechner etwas.