Zustände deuten
Einen Automaten analysieren heißt herausfinden, welche Wörter er akzeptiert — und warum. Der Schlüssel ist die Frage: Was „weiß“ der Automat in jedem Zustand über das bisher gelesene Wort?
- Bedeutung:für jeden Zustand in Worten notieren, was bisher gelesen wurde, z. B. „zuletzt ein b“.
- Testwörter:systematisch der Länge nach: \(\varepsilon\),
a,b,aa,ab,ba,bb, … - Schleife:das Zeichen ändert nichts an der Bedeutung des Zustands.
- Zyklus:Hin und Her zwischen Zuständen — der Automat „merkt sich“ etwas Wechselndes.
- Fehlerzustand:kein Weg führt mehr zu einem Endzustand; wer hineingerät, wird abgelehnt.
- Endzustände:ihre Bedeutungen zusammen ergeben die Bedingung für akzeptierte Wörter.
Markiere alle Wortkarten, die der Automat akzeptiert (Klick oder Enter, Pfeiltasten wechseln die Karte). Nach dem Prüfen zeigt jede Karte ihren Endzustand, ✓ oder ✗ bewertet deine Einschätzung. Fahre mit der Maus darüber oder fokussiere sie, dann läuft der Weg im Graphen ab.
Halte fest: z0 bedeutet „zuletzt kein b“, z1 „zuletzt genau ein b“, zF „irgendwo stand bb“. Akzeptiert werden also genau die Wörter ohne zwei b hintereinander.
Die Sprache beschreiben
Aus den Bedeutungen der Zustände entsteht die Beschreibung der Sprache — erst in Worten, dann als Menge.
- \(\Sigma^*\):die Menge aller Wörter über \(\Sigma\), einschließlich \(\varepsilon\).
- In Worten:eine Bedingung, die für jedes Wort eindeutig wahr oder falsch ist.
- Als Menge:\(L(A)=\{\,w\in\Sigma^*\mid w \text{ enthält nicht } bb\,\}\).
- Gegenprobe:Wörter aus der Beschreibung müssen akzeptiert, alle anderen abgelehnt werden.
- Grenzfälle:\(\varepsilon\), ein einzelnes Zeichen, das Muster am Anfang und am Ende.
Übergangstabelle mit Bedeutungen zum Automaten aus dem Applet (→ Startzustand, doppelt unterstrichen: Endzustand):
| Zustand | \(a\) | \(b\) | Bedeutung |
|---|---|---|---|
| z0 | z0 | z1 | noch nichts gelesen oder zuletzt a |
| z1 | z0 | zF | zuletzt ein einzelnes b |
| zF | zF | zF | bb kam vor |
Sprache: Ein Wort liegt in \(L(A)\) genau dann, wenn es in einem Endzustand endet — die Bedeutungen der Endzustände liefern die Bedingung in \(L(A)=\{\,w\in\Sigma^*\mid \dots\,\}\).
Allgemeine Hinweise
Das leere Wort prüfen
Ist der Startzustand ein Endzustand, gehört \(\varepsilon\) zur Sprache. Deine Beschreibung muss dann auch das leere Wort erfassen.
Gegenprobe mit Grenzfällen
Teste Wörter, die knapp gelten oder knapp scheitern: b, bab, bb am Anfang, bb am Ende.
Genau statt ungefähr
„Wenige b“ ist keine Beschreibung: babab hat drei b und wird akzeptiert, abba mit zwei nicht.