Dreißig Übungen zum deterministischen endlichen Automaten — von AFB I bis AFB III.
Ihr Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen in gemischter Reihenfolge — Sie klicken, ziehen, ordnen, rechnen und knobeln. Jede Übung gibt Ihnen sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fahren Sie über ein unterstrichenes Arbeitswort, sehen Sie, was es genau von Ihnen verlangt.
A1
Die Bausteine im Überblick
AFB I
Beschreiben Sie die Bausteine eines DEA: Decken Sie immer einen Begriff und die Beschreibung auf, die zu ihm gehört.
Decken Sie zwei Karten auf, die zusammengehören. Mit der Tastatur: Tab zur Karte, Enter aufdecken, Pfeiltasten zum Wandern.
Sechs Paare: Das Eingabealphabet Σ ist die endliche Menge erlaubter Zeichen. Der Startzustand trägt einen Pfeil ohne Ausgangszustand, ein Endzustand ist ein Doppelkreis. Eine Schleife endet im selben Zustand, an dem sie beginnt. Die Zustandsfolge zeigt den Weg durch den Automaten, und im Fehlerzustand bleibt der Automat für immer.
Überlegen Sie bei jedem Begriff, ob er etwas im Graphen zeichnet (Pfeil, Kreis) oder etwas über das Wort aussagt.
Der Startzustand und der Endzustand unterscheiden sich in der Zeichnung: ein Pfeil von außen gegenüber einem zweiten Kreis. Die Schleife erkennen Sie am Pfeil, der bei seinem eigenen Zustand wieder ankommt.
A2
Welcher Rest bleibt?
AFB IIMix
Ein Automat liest eine Dezimalzahl Ziffer für Ziffer. Sein Zustand merkt sich den Rest, den die Summe der bisher gelesenen Ziffern bei der Division durch 3 lässt; in der Tabelle steht jede Spalte für eine Gruppe von Ziffern (→ Startzustand, doppelt unterstrichen: Endzustand).
Zustand
0, 3, 6, 9
1, 4, 7
2, 5, 8
z0
z0
z1
z2
z1
z1
z2
z0
z2
z2
z0
z1
Ordnen Sie jede Zahl dem Zustand zu, in dem der Automat nach dem letzten Zeichen steht.
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).
1endet in z0
2endet in z1
3endet in z2
Der Zustand zählt die Ziffernsumme modulo 3: 123 hat die Summe 6, Rest 0. 1002 hat 3, Rest 0, und 99 hat 18, Rest 0. 850 und 58 haben die Summen 13, Rest 1, und 70 die Summe 7, Rest 1. 47 hat 11, Rest 2, 2024 die 8, Rest 2, und 1001 die 2, Rest 2. Nur in z0 – dem Endzustand – wird die Zahl angenommen: Rest 0 bedeutet, dass sie durch 3 teilbar ist.
Gehen Sie die Ziffern von links nach rechts durch und merken Sie sich nur den aktuellen Zustand – nicht die ganze Zahl.
Sortieren Sie jede Ziffer zuerst in ihre Spalte ein (0, 3, 6, 9 / 1, 4, 7 / 2, 5, 8). Eine Ziffer der mittleren Spalte schaltet um einen Zustand weiter, eine der rechten um zwei, mit z2 → z0 als Rückkehr.
A3
Der Weg durch das Labyrinth
AFB II
Ein Roboter wird durch ein Labyrinth gesteuert. Jeder Zustand ist ein Raum, die Eingabe r bedeutet „rechts abbiegen“, l „links abbiegen“. Der Ausgang des Labyrinths ist der Endzustand z3 (Doppelring), in z4 sitzt der Roboter fest: Jedes Zeichen führt wieder nach z4.
Ermitteln Sie den Weg des Roboters für die Befehlsfolge lrl: Klicken Sie nacheinander alle weiteren Zustände an, in denen der Roboter steht – der Startzustand z0 ist schon gewählt.
Klicken Sie die Zustände Punkt für Punkt nach — der gelaufene Weg wird farbig nachgezeichnet. Mit der Tastatur: Tab zum Punkt, Enter wählt ihn, Rücktaste nimmt den letzten Schritt zurück.
Der Weg lautet z0, z1, z3, z4: l führt von z0 nach z1, r von z1 nach z3 und l von z3 nach z4. Der Roboter steht nach lr zwar im Ausgang z3, aber der Befehl l ist noch nicht abgearbeitet. Entscheidend ist der Zustand nach dem letzten Zeichen – hier die Sackgasse z4, das Wort wird also abgelehnt.
Starten Sie bei z0 und lesen Sie die Befehle von links nach rechts: Zu jedem Zeichen gehört genau ein Pfeil. Die Buchstaben stehen an den Linien.
Der Ausgang z3 liegt auf dem Weg, aber das Wort ist nach lr noch nicht zu Ende. Ein Wort mit drei Zeichen hat vier Zustände in seiner Zustandsfolge.
