DEA entwerfen
- Bestandteile:Eingabealphabet Σ, Zustände, genau ein Startzustand (Pfeil „Start“), Endzustände (Doppelkreis), Übergänge.
- Vollständig:aus jedem Zustand führt für jedes Zeichen aus Σ genau ein Übergang — sonst ist es kein DEA.
- Fehlerzustand:darf im Zustandsgraphen fehlen, wenn das ausdrücklich erläutert wird.
- Akzeptieren:ein Wort wird akzeptiert, wenn der Automat nach dem letzten Zeichen in einem Endzustand steht.
Der Automat soll genau die Wörter über Σ = {a, b} akzeptieren, die auf ab enden. Drei Übergänge zeigen noch in den falschen Zustand: Ziehe die Pfeilspitzen (Maus oder Tab + Pfeiltasten) zum richtigen Zustand — die Testwörter werten sofort neu aus.
Halte fest: Jeder Zustand steht für eine Information über das bisher gelesene Wort — hier: „endet auf nichts Passendes“, „endet auf a“, „endet auf ab“.
Mealy-Automaten und Grenzen
- Mealy-Automat:Übergänge tragen Eingabe / Ausgabe, z. B.
b / B; zusätzlich gibt es ein Ausgabealphabet Ω. - Leere Ausgabe:wird mit ε notiert:
c / ε. Statt einzelner Zeichen sind auch Wörter als Ausgabe erlaubt. - Kein Endzustand:ein Mealy-Automat erzeugt Ausgaben — er entscheidet nicht über Akzeptieren.
- Implementieren:der Zustand wird eine Variable; für jedes gelesene Zeichen entscheidet eine Verzweigung über Folgezustand und Ausgabe.
- Grenzen:ein endlicher Automat kann nicht beliebig weit zählen: die Sprache aⁿbⁿ erkennt er nicht.
Mealy-Übergang: Eingabezeichen / Ausgabe
Allgemeine Hinweise
Vollständigkeit prüfen
Nach dem Zeichnen jeden Zustand abgehen: Gibt es für jedes Zeichen aus Σ genau einen Pfeil? Fehlende Übergänge kosten Punkte.
Endzustand ist kein Halt
Ein DEA liest immer das ganze Wort. Er darf einen Endzustand wieder verlassen.
Zustände benennen
Vor dem Zeichnen jedem Zustand eine Bedeutung geben, etwa „zuletzt a gelesen“. Dann ergeben sich die Übergänge fast von selbst.