Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen zum Klicken, Zuordnen, Nachverfolgen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Welcher Automat genügt?
AFB IOrdnen Sie jede Sprache über dem passenden Alphabet dem schwächsten Automaten zu, der sie erkennt.
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).
1DEA genügt
2Kellerautomat nötig
3auch Keller reicht nicht
Ohne Vergleich zweier unbeschränkter Anzahlen reicht ein DEA. Ein Vergleich (aⁿ gegen bⁿ⁺¹, w gegen wᴿ, m gegen n) gelingt mit einem Keller. Bei aⁿbⁿcⁿ muss dieselbe Anzahl zweimal verglichen werden — nach dem Vergleich mit den b ist der Keller leer und die Information verloren.
Ansatz: Muss der Automat überhaupt etwas Unbeschränktes vergleichen?
Weiter: Ein Keller kann eine Anzahl einmal abbauen. Wie oft muss hier verglichen werden?
A2
Entwurfsschritte
AFB IGeben Sie zu jedem Entwurfsschritt die Leitfrage oder das Kennzeichen an, indem Sie beide verbinden.
Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Die Schritte bauen aufeinander auf: Erst der Kellerplan, dann Zustände für die Phasen, dann die Übergänge mit dem Abschluss. Getestet wird am Ende — gerade Randfälle wie ε decken vergessene Übergänge auf.
Ansatz: Beginnen Sie mit dem Abschluss — dort steht fast schon die Notation.
Weiter: Raten muss ein Automat nur, wenn er einen Wechsel nicht am gelesenen Zeichen erkennt.
A3
Rest im Keller
AFB IDer Automat M lässt Reste im Keller zu.
Kellerautomat M für \(\{a^nb^m\mid n\ge m\ge 0\}\) (z0 und z1 Endzustände)
Bestimmen Sie, wie viele A nach dem vollständigen Lesen von aaaab im Keller liegen.
Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
Vier a legen vier A ab, das b entfernt eines: Es bleiben 3 A (Keller
AAA#). M steht in z1, einem Endzustand — das Wort wird trotz Rest akzeptiert. Hier ist das gewollt: Es dürfen mehr a als b vorkommen. Typischer Fehler: 4 — das gelesene b nicht abziehen.Ansatz: Zählen Sie die abgelegten A und die entfernten A.
Weiter: Jedes a legt ein A ab, jedes b entfernt eines.