Dreißig Übungen zu DEA, Mealy-Automaten und ihren Grenzen — von AFB I bis AFB III.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen in gemischter Reihenfolge — du klickst, ziehst, ordnest, rechnest und knobelst. Jede Übung gibt dir 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. Fährst du über ein unterstrichenes Arbeitswort, siehst du, was es genau von dir verlangt.
A1
Zusammenhänge bei Automaten
AFB I
Bestimme, wie sich die Größen verändern: Stelle die Wörter so ein, dass die vier Sätze über Automaten stimmen.
Klicke auf die farbig hinterlegten Wörter: Jeder Klick schaltet zur nächsten Möglichkeit weiter. Stelle jeden Satz so ein, dass er inhaltlich stimmt. Tastatur: Tab zum Wort, Enter/Leertaste oder ↑/↓ schaltet um.
1
Je mehr Zeichen das Eingabealphabet Σ hat, desto Übergänge hat ein vollständiger DEA mit gleich vielen Zuständen.
2
Je mehr Zustände ein vollständiger DEA bei festem Σ hat, desto Zeilen hat seine Übergangstabelle.
3
Je länger ein Eingabewort ist, desto Übergänge führt ein DEA aus, bis er das Wort annimmt oder ablehnt.
4
Je größer die Schranke n bei „höchstens n-mal das Zeichen a“ ist, desto Zustände braucht der DEA mindestens (Fehlerzustand mitgezählt).
Ein vollständiger DEA hat |Z| · |Σ| Übergänge, also wächst die Zahl mit |Σ|. Die Tabelle hat eine Zeile je Zustand. Pro gelesenem Zeichen läuft genau ein Übergang. Wer bis n zählen muss, braucht die Zustände 0 bis n und zusätzlich den Fehlerzustand: n + 2 Zustände.
Denke an die Formel für die Zahl der Übergänge eines vollständigen DEA und daran, was eine Zeile der Übergangstabelle beschreibt.
Beim Zählen bis n braucht der Automat je einen Zustand für 0, 1, …, n gelesene a und noch einen für „zu viele“.
A2
Entwurf oder DEA?
AFB II
Untersuche die sieben Beschreibungen von Automaten über Σ = {a, b}: Schiebe jede Karte auf „DEA“, wenn alle Bedingungen an einen DEA erfüllt sind, sonst auf „kein DEA“.
Schiebe die oberste Karte auf den passenden Stapel: ziehen, einen der beiden Stapel-Knöpfe drücken oder auf der Karte ←/→. Eine abgelegte Karte holst du mit Klick oder Enter zurück. „Prüfen“ schickt falsch abgelegte Karten mit einem Hinweis zurück in den Stapel.
Zwei Zustände; aus jedem führt für a und für b genau ein Pfeil.
Aus z0 führen zwei Pfeile mit a in verschiedene Zustände.
Der Graph hat zwei Startzustände.
Kein Zustand ist Endzustand; sonst ist alles vollständig.
z2 ist vom Startzustand aus nie erreichbar; sonst ist alles vollständig.
Aus z1 fehlt der Pfeil für b; ein Vermerk dazu steht nicht da.
Aus z1 fehlt der Pfeil für b; der Vermerk besagt, dass nicht eingezeichnete Übergänge in den Fehlerzustand führen.
Ein DEA braucht genau einen Startzustand und für jeden Zustand und jedes Zeichen genau einen Folgezustand, ausgenommen den Fehlerzustand mit Vermerk. Beliebig viele Endzustände sind erlaubt, auch keiner. Ein nicht erreichbarer Zustand ist harmlos.
Gehe die Bausteine eines DEA der Reihe nach durch: Startzustand, Endzustände, Übergänge.
Frage bei jeder Karte: Gibt es zu jedem Zustand und Zeichen genau einen Pfeil? Fehlende Endzustände oder ein unerreichbarer Zustand sind dagegen erlaubt.
A3
Fehlende Pfeile zählen
AFB I
Der Zustandsgraph eines Wortprüfers hat 5 Zustände (der Fehlerzustand zF ist dabei) über Σ = {a, b, c}. Eingezeichnet sind 11 Pfeile; ein Vermerk besagt, dass alle übrigen Übergänge in zF führen.
Berechne, wie viele Übergänge nicht eingezeichnet sind: Ordne jeder Zeile der Rechnung die passende Begründung zu.
Ordne jeder Zeile der Herleitung die passende Begründung zu: Karte anklicken, dann das Feld neben der Zeile (oder Karte direkt auf das Feld ziehen). Mit der Tastatur: Tab zur Karte, Enter, dann Tab zum Feld und Enter. Ein Klick auf ein belegtes Feld legt die Karte zurück. Nicht alle Karten werden gebraucht.
Zu zeigen: Vier Übergänge sind nicht eingezeichnet.
RechnungBegründung
(1)5 · 3 = 15
(2)15 − 11 = 4
(3)4 Übergänge führen nach zF
Mit 5 Zuständen und 3 Zeichen hat der vollständige DEA 5 · 3 = 15 Übergänge. Davon sind 11 eingezeichnet, also fehlen 15 − 11 = 4. Alle vier führen laut Vermerk nach zF.
Wie viele Übergänge hat ein vollständiger DEA insgesamt? Das hängt von der Zahl der Zustände und der Zeichen ab.
Von der Gesamtzahl ziehst du die eingezeichneten Pfeile ab; der Rest ist die gesuchte Zahl.
