Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen zum Deuten, Testen, Vermuten und Widerlegen — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Zeit pro Zeichen
AFB IEin Hardware-Automat liest die Zeichen eines Wortes nacheinander. Berechnen Sie die Zeiten, indem Sie jeden Wert über die Einheitentreppe zur orange markierten Einheit bringen.
Bringen Sie den Wert über die Treppe zur orange markierten Zieleinheit. Wählen Sie dazu Rechenschritte: Malnehmen führt eine Stufe hinab zur kleineren Einheit, Teilen eine Stufe hinauf. Nur ein passender Faktor bewegt den Wert. Mit der Tastatur: Tab zum Rechenschritt, Enter.
Aufgabe 1 von 3
Zwischen zwei benachbarten Stufen liegt hier immer der Faktor 1000: von der größeren zur kleineren Einheit malnehmen, in die Gegenrichtung teilen.
Entscheiden Sie bei jeder Aufgabe, ob die Zieleinheit kleiner (malnehmen) oder größer (teilen) ist als die gegebene.
Für eine Stufe gilt immer der Faktor 1000; 1 s sind 1000 ms und 1 ms sind 1000 µs.
A2
Zwischendurch am Ziel?
AFB IIAutomat S ist als Zustandsgraph gegeben. Erklären Sie, ob er das Wort abbab akzeptiert, indem Sie ihn Zeichen für Zeichen durchspielen.
Automat S, Σ = {a, b}
Spielen Sie den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt Sie weiter.
S akzeptiert genau die Wörter mit zwei b. abbab hat drei b: Nach dem dritten Zeichen stand der Automat zwar in z2, das vierte a lässt ihn dort, aber das letzte b führt nach z3. Typischer Fehler: schon beim Erreichen eines Endzustands „akzeptiert“ sagen.
Gehen Sie nach jedem Zeichen genau einem Pfeil nach und merken Sie sich den neuen Zustand.
Entscheidend ist allein der Zustand nach dem letzten Zeichen — dass der Automat unterwegs einmal in einem Endzustand stand, genügt nicht.
A3
Was weiß der Automat?
AFB IBeim Analysieren beschreibt man zuerst, was der Automat in jedem Zustand über das bisher gelesene Wort „weiß“. Ordnen Sie jedem Zustand von Automat A seine Bedeutung zu.
Automat A, Σ = {a, b}
Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Der erste Schritt entscheidet endgültig, in welcher „Hälfte“ der Automat bleibt: Von z1/z2 führt kein Pfeil zu z3/z4. Innerhalb einer Hälfte merkt er sich nur das zuletzt gelesene Zeichen. Typischer Fehler: z2 als „zuletzt b“ deuten und vergessen, dass der Automat sich auch den Anfang merkt — sonst wären z2 und z3 dieselbe Bedeutung.
Ansatz: Welche Wörter führen in den jeweiligen Zustand? Schreiben Sie zu jedem Zustand zwei kurze Beispiele auf.
Weiter: Die obere Reihe erreicht man nur mit einem a am Anfang, die untere nur mit einem b. Schleifen zeigen, welches Zeichen zuletzt kam.