Aufgabenblock — AFB II
Zehn Aufgaben aus allen Unterkapiteln: Zustände deuten, Entwürfe vergleichen und erweitern, Automaten implementieren und Mealy-Ausgaben untersuchen — mit gestuften Tipps, wenn Sie nicht weiterkommen.
Gegeben ist ein DEA über \(\Sigma=\{a,\,b\}\).
Analysieren Sie den Automaten, indem Sie für jeden Zustand seine Bedeutung notieren. Wie viele Wörter der Länge 3 bzw. der Länge 4 akzeptiert er?
b? Was ändert ein a? Die Schleifen zeigen: b spielt für den Zustand keine Rolle.a modulo 3. Akzeptiert wird, wenn diese Anzahl durch 3 teilbar ist.bbb, aaa → 2. Länge 4: bbbb und die vier Wörter mit genau drei a → 5.Vollständige Lösung
| Zustand | Bedeutung |
|---|---|
| z0 | Anzahl der a durch 3 teilbar (auch 0) |
| z1 | Anzahl der a lässt Rest 1 |
| z2 | Anzahl der a lässt Rest 2 |
\(L(A)=\{\,w\in\{a,b\}^*\mid \text{Anzahl der } a \text{ in } w \text{ ist durch 3 teilbar}\,\}\) — dazu gehört auch \(\varepsilon\).
Länge 3: 0 oder 3 a, also bbb, aaa → 2. Länge 4: 0 oder 3 a, also bbbb und aaab, aaba, abaa, baaa → 5
Ein Schüler zeichnet den folgenden Graphen über \(\Sigma=\{a,\,b,\,c\}\), ohne einen Vermerk darunter zu schreiben.
Begründen Sie, warum der Graph keinen vollständigen DEA darstellt. Wie viele Übergänge fehlen? Wie viele Übergänge hat der Automat, nachdem Sie ihn um einen Fehlerzustand zF vervollständigt haben?
Vollständige Lösung
Ein vollständiger DEA braucht aus jedem Zustand für jedes Zeichen genau einen Pfeil. Hier fehlen δ(z1, c), δ(z2, a) und δ(z2, b) → 3. Ohne Vermerk ist nicht klar, was bei diesen Eingaben passiert — der Graph ist unvollständig.
Vervollständigt: Die drei Lücken führen nach zF, zF erhält eine Schleife mit a, b, c. Insgesamt \(4\cdot 3\) = 12 Übergänge (6 gezeichnete + 3 neue + 3 Schleifen an zF).
Der folgende DEA liest Binärzahlen, das höchstwertige Bit zuerst. Er akzeptiert genau die Binärzahlen, die durch 3 teilbar sind.
Erläutern Sie, warum Zustand zr bedeutet: „Der bisher gelesene Wert lässt beim Teilen durch 3 den Rest r.“ In welchem Zustand endet der Automat für 100000? (Nummer angeben)
10 (2) wird zu 101 (5).Vollständige Lösung
Hängt man an eine Binärzahl mit Wert \(v\) das Bit \(x\) an, entsteht der Wert \(2v+x\). Für den Rest bei Division durch 3 zählt nur der alte Rest \(r\): neuer Rest \((2r+x)\bmod 3\). Prüfung am Graphen: z1 mit 0 → \((2+0)\bmod 3=2\) → z2; z2 mit 1 → \((4+1)\bmod 3=2\) → z2 (Schleife). Startzustand z0: vor dem ersten Bit ist der Wert 0.
z0 \(\xrightarrow{\text{1}}\) z1 \(\xrightarrow{\text{0}}\) z2 \(\xrightarrow{\text{0}}\) z1 \(\xrightarrow{\text{0}}\) z2 \(\xrightarrow{\text{0}}\) z1 \(\xrightarrow{\text{0}}\) z2 → z2, denn \(32 \bmod 3 = 2\).