Hier sind die 12 häufigsten Fehler in Klausuren zu endlichen Automaten — jeweils mit Beispiel, Begründung und richtiger Lösung. Wer einen Fehler kennt, macht ihn seltener.
Die 12 häufigsten Fehler
1Unterwegs entschieden
So wird es oft gemacht: Der Dezimalzahl-Automat ist nach 3,5 im Endzustand z3 — „also wird 3,5, akzeptiert“.
Warum falsch: Ein Endzustand unterwegs zählt nicht. Entscheidend ist allein der Zustand nach dem letzten Zeichen; das zweite Komma führt nach zF.
Richtig ist: Zustandsfolge bis zum Ende: z0 · z1 · z2 · z3 · zF → abgelehnt.
Erst nach dem letzten Zeichen wird entschieden.
2Schleife vergessen
So wird es oft gemacht: Fahrstuhl: „In E2 kann man nicht höher fahren, also braucht h dort keinen Pfeil.“
Warum falsch: Vollständig heißt: In jedem Zustand hat jede Eingabe einen Pfeil. Ohne Pfeil ist unklar, was bei h in E2 passiert.
Richtig ist: Schleife h an E2 und r an E0: \(3\cdot 2=6\) Übergänge.
Passiert nichts, zeichne eine Schleife.
3Fehlerzustand ohne Vermerk
So wird es oft gemacht: Im Graphen für ganze Zahlen mit Vorzeichen fehlen alle Pfeile nach zF — ohne ein Wort dazu.
Warum falsch: Automaten gelten als vollständig. Fehlende Übergänge sind nur erlaubt, wenn ausdrücklich vermerkt ist, wohin sie führen. Sonst ist der Graph unvollständig.
Richtig ist: Entweder zF mit allen \(|Z|\cdot|\Sigma|\) Pfeilen einzeichnen oder darunter schreiben: „Nicht eingezeichnete Übergänge führen in den Fehlerzustand zF.“
zF weglassen — nur mit Vermerk.
4Zwei Pfeile mit demselben Zeichen
So wird es oft gemacht: Für „Wörter über {a, b}, die auf ab enden“: Schleife a, b an z0 und zusätzlich z0 –a→ z1.
Warum falsch: Aus z0 führen zwei Pfeile mit a — der Automat wäre nicht deterministisch. Außerdem fehlen Pfeile aus z1 und z2.
Richtig ist: Jeder Zustand bekommt eine Bedeutung (z1 = „endet auf a“, z2 = „endet auf ab“); dann hat jedes Zeichen genau einen Folgezustand.
Pro Zustand und Zeichen genau ein Pfeil.
5Das leere Wort übersehen
So wird es oft gemacht: Automat „Anzahl der a durch 3 teilbar“ (z0 Start und Endzustand): „\(L(A)\) = Wörter mit 3, 6, 9, … a.“
Warum falsch: Die Beschreibung vergisst die Wörter mit 0 a: \(\varepsilon\), b, bbb. Ist der Startzustand ein Endzustand, wird \(\varepsilon\) akzeptiert.
Richtig ist: \(L(A)=\{\,w\in\{a,b\}^*\mid \text{Anzahl der } a \text{ ist durch 3 teilbar}\,\}\) — 0 ist durch 3 teilbar.
Ist der Start ein Endzustand, gehört ε dazu.
6Sprache ungenau beschrieben
So wird es oft gemacht: Zum Automaten „enthält 101“: „Er akzeptiert Wörter mit vielen Einsen.“
Warum falsch: „Viele“ ist keine Bedingung: 111 hat drei Einsen und wird abgelehnt, 101 hat nur zwei und wird akzeptiert.
Richtig ist: \(L(A)=\{\,w\in\{0,1\}^*\mid w \text{ enthält } 101 \text{ als Teilwort}\,\}\) — mit Gegenprobe an 1101, 1001.
Die Beschreibung muss für jedes Wort eindeutig ja oder nein liefern.
7Neuanfang verschenkt
So wird es oft gemacht: Beim Entwurf für „enthält 101“: „Passt das Zeichen nicht, geht es zurück nach z0.“ Also z1 –1→ z0.
Warum falsch: Nach 11 ist die zweite 1 wieder ein möglicher Anfang. 1101 enthält 101, wird aber abgelehnt: z0 · z1 · z0 · z0 · z1.
Richtig ist: z1 –1→ z1: Das längste noch passende Ende ist wieder „1“. Dann: z0 · z1 · z1 · z2 · z3 → akzeptiert.
Rückweg zum längsten noch passenden Ende.
8Ereignis als Zustand
So wird es oft gemacht: Parkhausschranke mit den Zuständen „Ticket“ und „Durchfahrt“.
Warum falsch: Ticket ziehen und Durchfahren sind Ereignisse — sie passieren in einem Moment und gehören als Eingaben an die Pfeile. Ein Zustand ist eine Situation, die andauert.
Richtig ist: Zustände geschlossen und offen; Eingaben Ticket und Durchfahrt an den Pfeilen.
Zustände dauern an, Eingaben passieren.
9Startzustand nicht zurückgesetzt
public boolean akzeptiert(String wort) { for (int i = 0; i < wort.length(); i++) { uebergang(wort.charAt(i)); } return zustand == 0; }
public boolean akzeptiert(String wort) { zustand = 0; // Startzustand for (int i = 0; i < wort.length(); i++) { uebergang(wort.charAt(i)); } return zustand == 0; }
So wird es oft gemacht: akzeptiert setzt zustand nicht auf 0. Nach akzeptiert("1") liefert akzeptiert("10") im Automaten „durch 3 teilbar“ true.
Warum falsch: Der zweite Aufruf startet in z1, dem Endzustand des ersten Worts: z1 · z0 · z0. Dabei ist \(10_2=2\) nicht durch 3 teilbar.
Richtig ist: Erste Anweisung in akzeptiert: zustand = 0; Dann: z0 · z1 · z2 → false.
Jedes Wort beginnt im Startzustand.
10Ungültige Zeichen nicht abgefangen
int s = spalte(wort.charAt(i)); if (s == -1) { return false; } // Zeichen nicht in Σ zustand = delta[zustand][s];
So wird es oft gemacht: Tabellen-Version für Dezimalzahlen: zustand = delta[zustand][spalte(c)]; — auch für 12a.
Warum falsch: spalte liefert für a den Wert −1. Der Zugriff delta[zustand][-1] löst eine Ausnahme aus, statt das Wort abzulehnen.
Richtig ist: Vor dem Tabellenzugriff prüfen: bei −1 sofort false zurückgeben oder in den Fehlerzustand wechseln.
Zeichen außerhalb von Σ führen in den Fehlerzustand.
11Mealy-Ausgabe vergessen oder als 0 geschrieben
So wird es oft gemacht: Fahrkartenautomat: Pfeil 0 € → 1 € nur mit „1 €“ beschriftet — oder mit „1 € / 0“, weil nichts ausgegeben wird.
Warum falsch: Beim Mealy-Automaten trägt jeder Pfeil Eingabe und Ausgabe. „0“ wäre ein echtes Ausgabezeichen und müsste in \(\Omega\) stehen.
Richtig ist: Beschriftung „1 € / \(\varepsilon\)“: Eingabe 1 €, keine Ausgabe. \(\Omega=\{\text{Fahrkarte},\,1\text{ €}\}\) bleibt unverändert.
Nichts ausgeben heißt ε — nicht 0.
12„Mit genug Zuständen geht es“
So wird es oft gemacht: „Ein DEA mit 1000 Zuständen erkennt \(L=\{a^nb^n\mid n\ge 0\}\) — so lange Wörter gibt es praktisch nicht.“
Warum falsch: Bei \(a^{1000}\) wiederholt sich spätestens ein Zustand, dann werden \(a^ib^i\) und \(a^jb^i\) gleich beurteilt. Das gilt für jedes \(k\). Umgekehrt ist \(\{a^nb^m\mid n,m\ge 0\}\) sehr wohl regulär — es fehlt nur der Vergleich der Anzahlen.
Richtig ist: Kein DEA erkennt \(L\). Für \(\{a^nb^n\mid n\le 1000\}\) gibt es einen DEA — das ist aber eine andere, endliche Sprache.
Unbeschränkt zählen kann kein DEA — beschränkt zählen schon.