Automaten verstehen
Ein endlicher Automat reagiert auf Eingaben, indem er seinen Zustand wechselt. Ein DEA liest so ein Wort Zeichen für Zeichen und nimmt es an oder lehnt es ab.
8.1.1
Systeme mit Zuständen
- Zustand: Situation, in der sich das System gerade befindet (gesperrt, frei).
- Eingabe: Ereignis von außen, steht am Pfeil (Münze, Drücken).
- Übergang: Wechsel in den Folgezustand; Schleife = Eingabe ändert nichts.
- Startpfeil zeigt auf den Startzustand; Zustandsfolge = durchlaufene Zustände.
8.1.2
Der deterministische Automat
- \(\Sigma\): Eingabealphabet; Wort = Zeichenfolge, \(\varepsilon\) = leeres Wort.
- Endzustände als Doppelkreis, genau ein Startzustand.
- Deterministisch: je Zustand und Zeichen genau ein Folgezustand.
- Fehlerzustand zF darf fehlen — nur mit Vermerk.
8.1.3
Automaten analysieren
- Für jeden Zustand die Bedeutung notieren: Was weiß der Automat?
- Testwörter der Länge nach: \(\varepsilon\), a, b, aa, ab, …
- Schleife: Zeichen egal · Zyklus: wechselnde Information.
- Gegenprobe mit Grenzfällen: am Anfang, am Ende, \(\varepsilon\).
Notation
Kurz und genau
| Zustand | a | b |
|---|---|---|
| z0 | z1 | zF |
| z1 | z1 | z2 |
| z2 | z1 | z2 |
| zF | zF | zF |
- Übergangstabelle: Zeile = Zustand, Spalte = Zeichen; → Start, doppelt unterstrichen = Ende.
- \(\Sigma^*\): alle Wörter über \(\Sigma\), einschließlich \(\varepsilon\).
- \(L(A)\): Menge aller Wörter, die \(A\) akzeptiert.
- Zustände z0, z1, …; Fehlerzustand zF; Wörter in Schreibmaschinenschrift.
Beispiel oben: aab → z0, z1, z1, z2 — akzeptiert. aba ist nach ab im Endzustand, endet aber in z1 — abgelehnt.
Nicht zwischendurch entscheiden
Ein Endzustand unterwegs zählt nicht. Und aus dem Fehlerzustand gibt es kein Zurück: Wer einmal in zF ist, wird abgelehnt.
Automaten entwickeln
Beim Entwurf zählt die Frage, was sich der Automat über das bisher Gelesene merken muss. Die Implementierung übersetzt Zustände und Tabelle direkt in Code.
8.2.1
Einen DEA entwickeln
| Zustand | 1 | 2 | 3 |
|---|---|---|---|
| z0 | z1 | z0 | z0 |
| z1 | z1 | z2 | z0 |
| z2 | z1 | z0 | z3 |
| z3 | z1 | z0 | z0 |
- Alphabet festlegen.
- Was muss sich der Automat merken? Jede Antwort wird ein Zustand mit Bedeutung.
- Start = noch nichts gelesen; Endzustände = Bedingung erfüllt.
- Für jeden Zustand und jedes Zeichen einen Übergang festlegen.
- Testen: angenommene, abgelehnte Wörter, Grenzfälle, Überlappungen (
1123).
8.2.2
Automaten implementieren
public boolean akzeptiert(String wort) { zustand = 0; for (int i = 0; i < wort.length(); i++) { uebergang(wort.charAt(i)); } return zustand == 2; }
- Attribut
int zustand; Zustände als Zahlen kodiert. uebergang(char c): switch über den Zustand, if über das Zeichen.- Tabellen-Version:
int[][] deltaundspalte(char c). - Zeichen außerhalb von \(\Sigma\) → Fehlerzustand bzw. sofort
false.
zustand = delta[zustand][spalte(c)];Im Code bewirkt jedes Zeichen genau einen Übergang; akzeptiert wird, wenn nach der Schleife ein Endzustand erreicht ist.
Startzustand zurücksetzen
Ohne zustand = 0; am Anfang von akzeptiert beginnt der zweite Aufruf im Endzustand des ersten Worts.
Ausgabe und Grenzen
Ein Mealy-Automat erzeugt bei jedem Übergang eine Ausgabe. Und: Mit endlich vielen Zuständen lässt sich nicht beliebig weit zählen.
8.3.1
Der Mealy-Automat
| Zustand | 50 | 100 |
|---|---|---|
| 0 ct | 50 ct / ε | 100 ct / ε |
| 50 ct | 100 ct / ε | 0 ct / Getränk |
| 100 ct | 0 ct / Getränk | 0 ct / Getränk, 50 ct |
- \(\Sigma\) Eingabealphabet, \(\Omega\) Ausgabealphabet.
- Pfeil e / a: e lesen, a ausgeben; auch Wörter erlaubt; \(\varepsilon\) = keine Ausgabe.
- Ausgabe hängt von Zustand und Eingabe ab.
- Keine Endzustände, aber vollständig: jedes Zeichen braucht einen Pfeil.
8.3.2
Mealy-Automaten entwickeln
| Zustand | Eingabe | Ausgabe | Folge |
|---|---|---|---|
| z0 | 1 | 1 | z1 |
| z1 | 0 | 1 | z0 |
| z0 | 0 | 0 | z0 |
| z0 | 1 | 1 | z1 |
- Ausgabe mit Beispielpaaren klären: Eingabewort → Ausgabewort.
- Was muss sich der Automat merken? → Zustände mit Bedeutung.
- Ablaufprotokoll: Schritt, Zustand, Eingabe, Ausgabe, Folgezustand.
- Ist- und Soll-Ausgabe Zeichen für Zeichen vergleichen; jeden Pfeil testen.
8.3.3
Grenzen endlicher Automaten
- Einziges Gedächtnis eines DEA ist sein aktueller Zustand.
- \(k\) Zustände → höchstens \(k\) Vorgeschichten unterscheidbar.
- Schubfach: Von \(a^0,\dots,a^k\) enden zwei, \(a^i\) und \(a^j\), im selben Zustand — dann werden \(a^ib^i\) und \(a^jb^i\) gleich behandelt.
- Beschränkt zählen geht (modulo 3, Tiefe ≤ 2, endliche Sprachen).
- Unbeschränkt zählen geht nicht (Klammerung beliebiger Tiefe, Palindrome).
Vergleich
DEA oder Mealy?
| DEA | Mealy | |
|---|---|---|
| Zweck | Wort prüfen | Wort übersetzen |
| Pfeil | e | e / a |
| Endzustände | ja | nein |
| Ergebnis | ja / nein | Ausgabewort |
- Beide lesen Zeichen für Zeichen und haben endlich viele Zustände.
- Beide müssen vollständig sein: je Zustand und Zeichen genau ein Pfeil.
- Beim Mealy-Automaten \(\varepsilon\) statt eines fehlenden Schrägstrichs schreiben.
Ein DEA mit \(k\) Zuständen unterscheidet höchstens \(k\) Vorgeschichten. Darum erkennt kein DEA \(L=\{a^nb^n\mid n\ge 0\}\) — mehr Zustände verschieben das Problem nur.
ε ist nicht 0
\(\varepsilon\) heißt: Es wird nichts ausgegeben. Die Ausgabe 0 ist ein echtes Zeichen aus \(\Omega\).
Die Regeln, an denen die Punkte hängen
Was in Klausuren zu endlichen Automaten am häufigsten Punkte kostet:
Regel 1 — vollständig oder Vermerk
Jeder Zustand braucht für jedes Zeichen einen Pfeil. Wer den Fehlerzustand weglässt, schreibt dazu: „Nicht eingezeichnete Übergänge führen in den Fehlerzustand zF.“
Regel 2 — Bedeutung zu jedem Zustand
Beim Entwerfen und Analysieren gehört zu jedem Zustand ein Satz, was er bedeutet. Das macht den Automaten nachprüfbar und bringt Begründungspunkte.
Regel 3 — Testen mit Grenzfällen
Immer auch \(\varepsilon\), das kürzeste Wort, Wörter, die knapp scheitern, und beim Mealy-Automaten Eingaben, die jeden Pfeil benutzen.