Ein Zustand fasst zusammen, was sich das System über die Vergangenheit merken muss. Ein Zustandsübergang ist der Wechsel in einen anderen (oder denselben) Zustand, ausgelöst durch ein Eingabezeichen. Im Zustandsdiagramm sind Zustände Kreise und Übergänge Pfeile, die mit dem auslösenden Zeichen beschriftet sind. Ein Pfeil von außen markiert den Startzustand, ein Doppelkreis einen Endzustand. Die Zustandsübergangstabelle enthält dieselbe Information: eine Zeile je Zustand, eine Spalte je Zeichen, im Feld der Folgezustand.

Ein deterministischer endlicher Automat (DFA) ist ein Tupel $A = (Q, \Sigma, \delta, q_0, F)$. Dabei ist Q die endliche Menge der Zustände, $\Sigma$ das Eingabealphabet, $\delta: Q \times \Sigma \to Q$ die Übergangsfunktion, $q_0 \in Q$ der Startzustand und $F \subseteq Q$ die Menge der Endzustände. „Deterministisch“ heißt: Zu jedem Zustand und jedem Zeichen gibt es genau einen Folgezustand.

Als Akzeptor liest der Automat ein Wort von links nach rechts, beginnend in $q_0$. Steht er nach dem letzten Zeichen in einem Endzustand, akzeptiert er das Wort, sonst lehnt er es ab. Die Menge aller akzeptierten Wörter ist die erkannte Sprache $L(A)$.

Ein Mealy-Automat hat keine Endzustände, sondern gibt bei jedem Übergang ein Zeichen aus. Er ist ein Tupel $(Q, \Sigma, \Gamma, \delta, \lambda, q_0)$ mit dem Ausgabealphabet $\Gamma$ und der Ausgabefunktion $\lambda: Q \times \Sigma \to \Gamma$. Im Diagramm steht an jedem Pfeil „Eingabe/Ausgabe“. Er übersetzt ein Eingabewort in ein Ausgabewort gleicher Länge. Der Akzeptor beantwortet also eine Ja-Nein-Frage, der Mealy-Automat berechnet eine Ausgabe.

Die Sprachen, die ein DFA erkennt, heißen regulär. Nach dem Satz von Kleene sind das genau die Sprachen, die ein regulärer Ausdruck beschreibt: Zu jedem regulären Ausdruck gibt es einen DFA und umgekehrt. Der Ausdruck $\texttt{(a|b)*ab(a|b)*}$ beschreibt zum Beispiel alle Wörter über $\{a, b\}$ mit dem Teilwort ab. Der DFA dazu steht unten bei den Einsatzbereichen. Auch die regulären Grammatiken der nächsten Lektion erzeugen genau diese Sprachen. Ein regulärer Ausdruck beschreibt eine Sprache, ein Automat erkennt sie.

Benutzeroberflächen: Die Wirkung einer Eingabe hängt vom Zustand ab. Das Zustandsdiagramm dient als Entwurf: Im Zustand „angehalten“ startet Play die Wiedergabe, im Zustand „läuft“ hält es sie an.

Protokolle: Der Ablauf einer Kommunikation hat Zustände wie „wartet auf Bestätigung“. Nachrichten, die in einem Zustand nicht vorgesehen sind, führen zum Fehler. So lässt sich zum Beispiel der Verbindungsaufbau von TCP beschreiben.

Substringproblem: Kommt ein Muster p als Teilwort in einem Text vor? Der Automat für p hat $|p| + 1$ Zustände. Zustand i bedeutet: Die zuletzt gelesenen Zeichen enden mit den ersten i Zeichen von p, und kein längerer Musteranfang passt. Zustand $|p|$ ist ein Endzustand und wird nicht verlassen. Für $p = ab$ über $\{a, b\}$:

Der Text wird einmal von links nach rechts gelesen, ohne zurückzuspringen.