Ein DFA ist $M = (Z, \Sigma, \delta, z_0, E)$ mit endlicher Zustandsmenge $Z$, endlichem Alphabet $\Sigma$, Übergangsfunktion $\delta: Z \times \Sigma \to Z$, Startzustand $z_0 \in Z$ und Endzustandsmenge $E \subseteq Z$. Determinismus bedeutet: $\delta$ ist eine Funktion, also für jedes Paar $(z, a)$ genau ein Bildwert. Totalität wird meist als zusätzliche Bedingung gefordert: $\delta$ ist auf ganz $Z \times \Sigma$ definiert, kein Übergang fehlt.

$\delta$ arbeitet symbolweise: $\delta(z, a)$ gibt den Nachfolgezustand für ein einzelnes Symbol $a$. $\hat{\delta}$ arbeitet auf Wörtern: $\hat{\delta}(z, w)$ gibt den Zustand nach Lesen des gesamten Wortes $w$. Sie ist rekursiv über die Wortlänge definiert mit Basis $\hat{\delta}(z, \varepsilon) = z$. In der Praxis läuft man mit $\hat{\delta}$ das Wort einmal durch — das ist genau die Konfigurationsfolge.

Genau dann, wenn $\hat{\delta}(z_0, w) \in E$, also der beim Startzustand beginnende, das Wort abarbeitende Lauf in einem Endzustand endet. Es genügt nicht, unterwegs einen Endzustand zu durchlaufen — er muss am Ende erreicht werden.

$\varepsilon$ wird akzeptiert genau dann, wenn $z_0 \in E$. Denn $\hat{\delta}(z_0, \varepsilon) = z_0$. In vielen Beispielen ist der Startzustand kein Endzustand — dann ist $\varepsilon \notin L(M)$. Wenn er es ist, wie beim DFA für gerade Anzahl an Einsen, gilt $\varepsilon \in L(M)$. In der Klausur immer explizit prüfen.

$L_2$ und $L_3$ sind regulär, also DFA-akzeptierbar. Für $L_2$ reichen drei Zustände (noch kein $a$ gesehen, gerade ein $a$ gesehen, $ab$ schon gesehen — letzterer ist Fangzustand und Endzustand). Für $L_3$ reichen zwei Zustände (Länge gerade/ungerade). $L_1$ ist nicht regulär, da man beliebig viele $a$ zählen müsste, was ein endliches Zustandsgedächtnis nicht leisten kann. Das lässt sich mit dem Pumping-Lemma zeigen.

Für jeden Zustand $z$ und jedes Symbol $a$ sucht man die eindeutig ausgehende, mit $a$ beschriftete Kante — der Zielknoten ist $\delta(z, a)$. Die Tabelle ist sicherer, weil sie strukturell erzwingt, dass für jedes Paar $(z, a)$ genau ein Eintrag steht. Im Diagramm übersieht man leicht eine fehlende Kante und behauptet, der Automat sei total.

Sei $L = L(M)$ mit DFA $M = (Z, \Sigma, \delta, z_0, E)$. Definiere $M' = (Z, \Sigma, \delta, z_0, Z \setminus E)$ — gleicher Automat, nur die Endzustände sind vertauscht. Für jedes $w$ gilt: entweder $\hat{\delta}(z_0, w) \in E$ und $w \in L$, oder $\hat{\delta}(z_0, w) \in Z \setminus E$ und $w \in L(M')$. Also $L(M') = \Sigma^* \setminus L$. Wichtig: das funktioniert nur, weil $\delta$ total ist. Bei einem unvollständigen DFA würde das Vertauschen der Endzustände nicht das Komplement liefern.

Seien $M_1 = (Z_1, \Sigma, \delta_1, s_1, E_1)$ und $M_2 = (Z_2, \Sigma, \delta_2, s_2, E_2)$. Der Produktautomat ist $M = (Z_1 \times Z_2, \Sigma, \delta, (s_1, s_2), E_1 \times E_2)$ mit $\delta((p, q), a) = (\delta_1(p, a),\, \delta_2(q, a))$. Er simuliert beide Automaten parallel. Ein Wort wird nur akzeptiert, wenn beide Komponenten in Endzuständen enden — genau $L(M_1) \cap L(M_2)$. Für Vereinigung nimmt man stattdessen $E = (E_1 \times Z_2) \cup (Z_1 \times E_2)$.

Nein, denn $\delta$ ist nicht total. Streng nach der 5-Tupel-Definition ist es kein DFA. Man kann ihn totalisieren, indem man einen Fangzustand $z_f$ hinzunimmt, $\delta(z_2, 1) = z_f$ setzt und $\delta(z_f, a) = z_f$ für alle $a \in \Sigma$. Der Fangzustand ist kein Endzustand. Danach ist es ein DFA mit derselben akzeptierten Sprache.

Man schreibt die Startkonfiguration $(z_0, w)$, wendet die Übergangsrelation $\vdash$ pro Symbol an und erhält eine Kette $(z_0, w) \vdash (z_1, w_1) \vdash \dots \vdash (z_k, \varepsilon)$. Ist $z_k \in E$, folgt per Definition $w \in L(M)$. Der Beweis besteht aus dem korrekten Anwenden jedes Einzelschritts gemäß $\delta$ und dem Endcheck. In der Klausur immer alle Zwischenkonfigurationen hinschreiben — Teilpunkte werden dafür vergeben, selbst wenn die Endaussage falsch ist.