Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Achtundzwanzig Übungen zum Ablesen, Verfolgen, Übersetzen und Zählen — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Was macht einen DEA aus?
AFB INennen Sie alle Aussagen, die für jeden deterministischen endlichen Automaten gelten.
Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.
Ein DEA ohne Endzustand ist erlaubt — er akzeptiert eben kein einziges Wort. ε ist ein Wort (das Wort der Länge 0), kein Zeichen. Typischer Fehler: zwei a-Pfeile aus einem Zustand zulassen. Dann wäre der Folgezustand nicht mehr eindeutig — genau das verbietet „deterministisch“.
Ansatz: Gehen Sie die Bausteine durch: Σ, Zustände, Startzustand, Endzustände, Übergänge. Was sagt die Definition jeweils genau?
Weiter: „Genau ein Folgezustand“ schließt zwei Dinge aus: gar keinen Pfeil und mehrere Pfeile mit demselben Zeichen.
A2
Die Sperre nach drei Fehlern
AFB IIEine Eingabesperre wird als DEA modelliert: r steht für eine richtige, f für eine falsche Eingabe. Der Endzustand z3 bedeutet „gesperrt“.
Eingabesperre: Σ = {r, f}
Interpretieren Sie jeden Übergang der Sperre: Ordnen Sie ihn dem Bereich zu, der beschreibt, was er bewirkt.
Ordnen Sie jede Karte einem der drei Bereiche zu. Mit der Tastatur: Enter zum Auswählen, dann 1–3 für den Bereich, 0 zurück.
1 bleibt im Zustand
2 wechselt zum nächsten Zustand
3 wechselt zurück nach z0
Eine richtige Eingabe setzt die Sperre aus z1 und z2 zurück nach z0; in z0 selbst ändert sie nichts (Schleife). Jede falsche Eingabe führt eine Stufe näher an die Sperre: z0, z1 und z2 wechseln mit f zum nächsten Zustand. In z3 – dem Endzustand – ist jedes Zeichen eine Schleife: Wer gesperrt ist, bleibt gesperrt.
Prüfen Sie bei jedem Übergang, ob Ausgangs- und Folgezustand gleich sind. Wenn nicht, schauen Sie, ob es der nächste Zustand in der Reihe z0, z1, z2, z3 ist oder z0.
Der Übergang z0 –r→ z0 beginnt und endet in z0: Das ist eine Schleife und kein Zurückspringen. Zurück geht es nur aus z1 und z2.
A3
Ganze Zahlen mit Vorzeichen
AFB IOrdnen Sie jedes Wort zu: Nimmt der Automat es an oder lehnt er es ab?
Ganze Zahlen: Σ = {+, −, 0, 1, …, 9}, d steht für eine beliebige Ziffer
Nicht eingezeichnete Übergänge führen in einen Fehlerzustand zF.
Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).
1akzeptiert
2abgelehnt
0815 wird angenommen — der Automat verbietet führende Nullen nicht. − allein endet in z1, ε bleibt in z0: beides keine Endzustände. 4−2 und +−3 laufen in den nicht gezeichneten Fehlerzustand. Typischer Fehler: nach dem eigenen Zahlgefühl entscheiden statt nach dem Graphen.Ansatz: Verfolgen Sie jedes Wort Zeichen für Zeichen ab z0. Fehlt ein Pfeil, landet das Wort im Fehlerzustand.
Weiter: Nur z2 ist Endzustand. Wo steht der Automat nach dem leeren Wort?