Einen DEA entwickeln

Beim Entwurf eines DEA beginnst du nicht mit Pfeilen, sondern mit der Frage, was der Automat beim Lesen im Kopf behalten muss.

• Alphabet:erlaubte Zeichen festlegen, hier \(\Sigma=\{1,\,2,\,3\}\).
• Gedächtnis:„Was muss sich der Automat merken?“ — jede mögliche Antwort wird ein Zustand.
• Bedeutung:jeden Zustand in Worten beschreiben, z. B. z2 = „bisher endet die Eingabe auf 12“.
• Start und Ende:Startzustand = noch nichts gelesen; Endzustände = Bedingung erfüllt.
• Übergänge:für jeden Zustand und jedes Zeichen fragen: Was weiß der Automat danach?
• Fehlerzustand:nur nötig, wenn ein Wort nicht mehr zu retten ist — hier nie.
• Testen:Wörter, die angenommen werden, solche, die abgelehnt werden, und Grenzfälle.

Das Schloss liest Ziffern aus \(\{1,\,2,\,3\}\) und öffnet genau dann, wenn die Eingabe auf 123 endet. Die vier Zustände sind vorgegeben — setze alle zwölf Übergänge selbst. Die Testwörter prüfen deinen Automaten nach jeder Änderung.

Halte fest: Die Kette z0 → z1 → z2 → z3 ist schnell gebaut. Die eigentliche Arbeit steckt in den Rückwegen: Jedes Zeichen, das nicht passt, führt in den Zustand, der zum längsten noch passenden Ende gehört.

Die Rückwege findest du, indem du fragst: Welches Ende der bisherigen Eingabe kann noch der Anfang von 123 sein?

• Passt das Zeichen:einen Schritt weiter in der Kette (z0 \(\xrightarrow{1}\) z1 \(\xrightarrow{2}\) z2 \(\xrightarrow{3}\) z3).
• Eine 1:ist immer ein neuer Anfang — aus jedem Zustand nach z1, auch aus z1 selbst.
• Sonst:kein passendes Ende mehr, zurück nach z0.
• Nach z3:Das Schloss liest weiter — z3 ist nur Endzustand, wenn das Wort dort endet.
• Vollständig:\(|Z|\cdot|\Sigma| = 4\cdot 3 = 12\) Übergänge, jede Zeile der Tabelle voll.
• Grenzfälle:\(\varepsilon\), das kürzeste Wort 123 und Wörter mit Überlappung.

Fallen beim Testen (fett: der Zustand, an dem ein flüchtiger Entwurf scheitert):