Aufgabenblock — AFB III
Begründen statt nur ausführen: Automaten selbstständig entwerfen, Behauptungen widerlegen, Grenzen beweisen, Entwürfe und Tests beurteilen. Formulieren Sie Ihre Antwort vollständig, bevor Sie die Musterlösung aufklappen.
Eine vereinfachte E-Mail-Adresse besteht aus einem Namen (mindestens ein Buchstabe), dem Zeichen @ und einer Domain aus mindestens zwei Teilen, die durch Punkte getrennt sind; jeder Teil besteht aus mindestens einem Buchstaben. Beispiele: anna@schule.de, max@mail.nds.de. Verwenden Sie \(\Sigma=\{B,\,@,\,.\}\), wobei B für einen beliebigen Buchstaben steht.
Entwerfen Sie einen DEA, der genau diese Adressen akzeptiert. Geben Sie für jeden Zustand seine Bedeutung an und testen Sie Ihren Automaten mit geeigneten Wörtern, auch mit Grenzfällen.
Musterlösung anzeigen (zählt als erledigt)
Nicht eingezeichnete Übergänge führen in den Fehlerzustand zF.
| Zustand | Bedeutung |
|---|---|
| z0 | noch nichts gelesen |
| z1 | Name mit mind. einem Buchstaben |
| z2 | @ gelesen |
| z3 | erster Domain-Teil begonnen |
| z4 | Punkt gelesen — Teil fehlt noch |
| z5 | mind. zwei Domain-Teile, letzter nicht leer |
| Testwort | Ergebnis |
|---|---|
anna@schule.de | ✓ akzeptiert |
max@mail.nds.de | ✓ akzeptiert |
anna@de | ✗ abgelehnt |
a.b@c.de | ✗ abgelehnt |
@x.de | ✗ abgelehnt |
a@b..de | ✗ abgelehnt |
anna@schule. | ✗ abgelehnt |
Wichtig: z3 darf kein Endzustand sein (anna@de hat nur einen Domain-Teil), z4 auch nicht (Adresse endet auf Punkt). Der Rückweg z5 –.→ z4 erlaubt beliebig viele Domain-Teile, verhindert aber zwei Punkte hintereinander.
Ein Mitschüler behauptet: „Mein Automat akzeptiert genau die Binärzahlen, die durch 4 teilbar sind.“
Widerlegen Sie die Behauptung und geben Sie an, welche Sprache der Automat tatsächlich erkennt. Beschreiben Sie, wie ein korrekter Automat aussehen müsste.
10 (Wert 2) endet in z1 und wird akzeptiert. Der Automat merkt sich nur die letzte Ziffer; für Teilbarkeit durch 4 braucht er die letzten zwei.Musterlösung anzeigen (zählt als erledigt)
Gegenbeispiel: z0 \(\xrightarrow{\text{1}}\) z2 \(\xrightarrow{\text{1}}\) z2 \(\xrightarrow{\text{0}}\) z1 — 110 (Wert 6) wird akzeptiert, 6 ist nicht durch 4 teilbar. Die Behauptung ist falsch.
z1 bedeutet „letzte Ziffer 0“, z2 „letzte Ziffer 1“. Der Automat erkennt \(L(A)=\{\,w\in\{0,1\}^*\mid w \text{ endet auf } 0\,\}\), also die geraden Binärzahlen (führende Nullen zugelassen).
Korrektur: Eine Binärzahl ist genau dann durch 4 teilbar, wenn sie auf 00 endet (oder 0 ist). Der Automat muss sich die letzten zwei Ziffern merken: ein zusätzlicher Zustand „endet auf 00“ als einziger Endzustand neben „nur 0 gelesen“; z1 („endet auf genau eine 0“) ist dann kein Endzustand mehr.
Gegeben ist die Sprache \(L=\{\,w\in\{a,b\}^*\mid w \text{ enthält gleich viele } a \text{ wie } b\,\}\), z. B. aabb, ba, \(\varepsilon\).
Beweisen Sie, dass es keinen DEA gibt, der \(L\) erkennt.
Musterlösung anzeigen (zählt als erledigt)
Annahme: Ein DEA \(A\) mit \(k\) Zuständen erkennt \(L\).
Schubfach: Die \(k+1\) Wörter \(a^0,a^1,\dots,a^k\) können nicht alle in verschiedenen Zuständen enden. Also gibt es \(i<j\), sodass \(A\) nach \(a^i\) und nach \(a^j\) im selben Zustand \(z\) ist.
Gleiches Urteil: Ab \(z\) liest \(A\) bei \(a^ib^i\) und bei \(a^jb^i\) dieselben Zeichen \(b^i\) und endet im selben Zustand. Er akzeptiert also beide oder keines.
Widerspruch: \(a^ib^i\) enthält \(i\) mal a und \(i\) mal b, liegt also in \(L\); \(a^jb^i\) enthält \(j\ne i\) mal a, liegt nicht in \(L\). Die Annahme ist falsch — kein DEA erkennt \(L\), gleichgültig wie groß \(k\) ist.