Automaten analysieren: Übungen – Informatik Grundkurs

Ihr Fortschritt:

0 / 0 Aufgaben

Ü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.

Die Sprache von Automat F

AFB I

Automat F ist als Zustandsgraph gegeben. Beschreiben Sie seine Sprache, indem Sie im Raster alle Wörter markieren, die er akzeptiert.

Automat F, Σ = {a, b}

Klicken Sie die passenden Felder an — ein zweiter Klick nimmt die Markierung zurück. Mit der Tastatur: Tab ins Raster, Pfeiltasten wandern, Enter markiert. Vollständige Reihen aus richtigen Feldern ergeben ein Bingo.

Markieren Sie alle Wörter, die Automat F akzeptiert.

F akzeptiert genau die Wörter, die auf ab enden: z2 erreicht man nur mit einem b aus z1, und z1 bedeutet „zuletzt ein a“. Das leere Wort und Wörter wie aba oder abb enden in z0 oder z1 und werden abgelehnt.

Verfolgen Sie jedes Wort Zeichen für Zeichen im Graphen und notieren Sie den Zustand nach dem letzten Zeichen.

Nur z2 ist Endzustand und wird nur über eine b-Kante von z1 erreicht: Das letzte Zeichen muss b sein, davor muss ein a stehen.

Der Ampelzyklus

AFB II

Eine Fußgängerampel ist als Automat mit den Eingaben t (Takt) und s (Störung) gegeben (→ Startzustand). Erstellen Sie die Zustandsfolge als Kreis: Legen Sie die Zustandskarten so im Uhrzeigersinn auf die Plätze, wie der Automat sie beim wiederholten Lesen von t durchläuft. Eine Karte gehört nicht in den Kreis.

Zustand	t	s
gelb	rot	blinkt
rot	rot-gelb	blinkt
blinkt	rot	blinkt
grün	gelb	blinkt
rot-gelb	grün	blinkt

Legen Sie jede Karte auf einen Platz im Kreis: Ziehen — oder erst die Karte und dann den Platz antippen (ein belegter Platz tauscht). Tastatur: Karte mit Tab wählen und die Ziffer des Platzes drücken; auf einem Platz wandern ←/→ im Kreis, Entf legt die Karte zurück. Nicht jede Karte gehört in den Kreis.

In der t-Spalte folgt rot → rot-gelb → grün → gelb → rot: ein Zyklus aus vier Zuständen. blinkt wird nur mit s erreicht und liegt nicht auf diesem Kreis.

Folgen Sie in der t-Spalte immer dem Eintrag des aktuellen Zustands, beginnend bei rot, bis Sie wieder bei rot ankommen.

Die s-Spalte spielt hier keine Rolle: Der Zustand blinkt steht nie in der t-Spalte hinter einem Zyklus-Zustand.

Mias Protokoll zu Automat H

AFB IIMix

Mia prüft mit Automat H Binärzahlen und notiert zu jedem Wort den Dezimalwert und den Rest bei Division durch 4. Nicht alle Notizen stimmen. Weisen Sie bei jeder Zeile nach, ob sie stimmt: Markieren Sie die falschen Zeilen und tragen Sie jeweils die Korrektur ein.

Automat H, Σ = {0, 1}

Klicken Sie die Zeilen an, die Sie für falsch halten — dabei klappt ein Feld für die Korrektur auf. Geprüft wird beides: die Auswahl und die Korrekturen.

H akzeptiert genau die Wörter, die auf 00 enden. Die Binärzahl 10100 ist 16 + 4 = 20, und 7 mod 4 ergibt 3. Das leere Wort liest kein Zeichen und bleibt im Startzustand z0 — der ist kein Endzustand, auch wenn der Wert 0 durch 4 teilbar wäre.

Rechnen Sie bei jeder Zeile den Dezimalwert nach (Stellenwerte von rechts: 1, 2, 4, 8, 16) und bilden Sie den Rest bei Division durch 4.

Ob H ein Wort akzeptiert, entscheidet allein der Zustand am Ende: z2 erreicht man erst nach zwei Nullen in Folge. Das leere Wort hat keine.