MINT üben

Einen DEA entwickeln

Dreißig Übungen zum Entwurf eines DEA: Gedächtnis, Übergänge, Fehlerzustand und Testwörter — 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
Der Automat im Bild
AFB I

Der Zustandsgraph gehört zu einem vollständigen DEA über \(\Sigma=\{0,\,1\}\). Lesen Sie die gesuchten Angaben ab.

0 0 1 1 z0 z1
Füllen Sie alle Felder aus und prüfen Sie dann auf einmal. Enter prüft ebenfalls.

Zahl der Zustände: · Zahl der Übergänge:

Der Endzustand heißt . Nach dem Wort 10110 befindet sich der Automat im Zustand .

Zwei Kreise, und aus jedem Zustand führt für jedes der beiden Zeichen ein Pfeil: 2 · 2 = 4 Übergänge. Nur z0 trägt den Doppelkreis. Das Wort 10110 führt über z0, z1, z1, z0, z1, z1 — jede 1 wechselt den Zustand, jede 0 ändert nichts.
Zählen Sie die Kreise, dann die Pfeile — und suchen Sie den Doppelkreis.
Verfolgen Sie das Wort vom Startpfeil aus Zeichen für Zeichen: Bei einer 1 wechselt der Automat den Zustand, bei einer 0 bleibt er.
A2
Der Weg zum Automaten
AFB I

Sara soll einen DEA für Variablennamen entwickeln. Stellen Sie ihr Vorgehen in der richtigen Reihenfolge dar.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1Eingabealphabet Σ festlegen
2Überlegen, was sich der Automat merken muss — jede mögliche Antwort wird ein Zustand mit Bedeutung
3Startzustand und Endzustände festlegen
4Für jeden Zustand und jedes Zeichen den Folgezustand bestimmen, bei Bedarf mit Fehlerzustand
5Mit Testwörtern und Grenzfällen prüfen
Erst das Gedächtnis, dann die Pfeile: Welche Zustände es gibt, folgt aus der Frage, was sich der Automat merken muss. Start und Ende ergeben sich aus den Bedeutungen, die Übergänge zuletzt. Typischer Fehler: sofort Pfeile zeichnen. Dann entstehen Zustände ohne klare Bedeutung, und beim Testen weiß niemand, was repariert werden muss.
Ansatz: Ohne Alphabet weiß man nicht, welche Zeichen überhaupt vorkommen.
Weiter: Übergänge kann man erst eintragen, wenn die Zustände mit ihrer Bedeutung feststehen. Getestet wird am Schluss.
A3
Ein Zähler liest ein Wort
AFB IIMix

Der Algorithmus liest das Wort w = baabaaab Zeichen für Zeichen; die Positionen zählen ab 0.

n ← länge(w)
z ← 0
i ← 0
solange i < n wiederhole
  wenn w[i] = "a" dann
    z ← (z + 1) mod 3
  ende wenn
  i ← i + 1
ende solange
Ausgabe: z

Analysieren Sie den Ablauf Schritt für Schritt und beantworten Sie dann, was der Algorithmus über ein Wort verrät.

Spielen Sie den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt Sie weiter.
    Ein Zähler modulo 3 ist ein Gedächtnis mit genau drei Möglichkeiten — also drei Zustände. Der Wert z entspricht dem Zustand, das gelesene Zeichen der Eingabe.
    Führen Sie die Schleife von Position 0 an durch und notieren Sie z nach jedem Zeichen; ein b lässt z unverändert.
    Der Befehl mod 3 gibt den Rest bei Division durch 3 an; nach z = 2 folgt beim nächsten a wieder z = 0. Fragen Sie danach, was sich der Algorithmus merkt.