Aufgabenblock — AFB I
Zehn Standardaufgaben zum Reproduzieren: Graphen und Tabellen lesen, Keller verfolgen, Regeln anwenden. Bei jeder Aufgabe gibt es eine Erinnerung und die Lösung zum Aufklappen.
Ein vollständiger DEA hat die Zustände z0, z1, z2 und den Fehlerzustand zF sowie das Eingabealphabet \(\Sigma=\{a,\,b,\,c,\,d\}\). Berechnen Sie, wie viele Übergänge (Pfeile einschließlich Schleifen) sein Zustandsgraph hat.
Lösung anzeigen
\(|Z|\cdot|\Sigma| = 4\cdot 4\) = 16 Übergänge
Die vier Schleifen an zF zählen mit.
Der DEA zählt die Einsen eines Binärworts:
Entnehmen Sie dem Graphen, in welchem Zustand der DEA nach 1101011 steht.
Lösung anzeigen
z0 → z1 → z2 → z2 → z0 → z0 → z1 → z2
Das Wort enthält fünf Einsen; 5 : 3 hat den Rest 2. Es wird abgelehnt, denn nur z0 ist Endzustand.
Ein Mealy-Automat mit \(\Sigma=\{a,b\}\) und \(\Omega=\{0,1\}\) ist durch die Tabelle gegeben (Folgezustand / Ausgabe):
| Zustand | a | b |
|---|---|---|
| z0 | z1 / 0 | z0 / ε |
| z1 | z0 / 1 | z1 / ε |
Geben Sie das Ausgabewort zur Eingabe abaab an (ohne Leerzeichen).
Lösung anzeigen
z0 –a/0→ z1 –b/ε→ z1 –a/1→ z0 –a/0→ z1 –b/ε→ z1 → 010
Die beiden b geben nichts aus.