Die Kennwortregel
13 BEAFB I–IIDer Anmeldeserver einer Schule prüft einen Teil der Kennwortregel mit dem abgebildeten DEA \(A\) über \(\Sigma=\{b,\,z\}\). Vor der Prüfung wird jeder Buchstabe durch b und jede Ziffer durch z ersetzt; aus Mai24x wird so bbbzzb.
- Ermitteln Sie für die Wörter \(\varepsilon\),
b,zb,bzb,zbz,bbzzbbjeweils den Zustand nach dem letzten Zeichen und entscheiden Sie, ob das Wort akzeptiert wird. (3 BE) - Ordnen Sie den drei Zuständen jeweils eine der folgenden Bedeutungen zu und begründen Sie eine Zuordnung am Graphen: „Ziffer schon gelesen, zuletzt ein Buchstabe“ · „noch keine Ziffer gelesen“ · „zuletzt eine Ziffer gelesen“. (3 BE)
- Formulieren Sie die von \(A\) akzeptierte Sprache \(L(A)\) in Worten und als Menge. Übersetzen Sie die Bedingung in eine Kennwortregel. (4 BE)
- Begründen Sie, dass jedes abgelehnte Wort durch Anhängen von höchstens zwei Zeichen zu einem akzeptierten Wort wird, und erklären Sie damit, warum \(A\) keinen Fehlerzustand hat. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| Wort | letzter Zustand | Ergebnis |
|---|---|---|
| \(\varepsilon\) | z0 | abgelehnt |
b | z0 | abgelehnt |
zb | z2 | akzeptiert |
bzb | z2 | akzeptiert |
zbz | z1 | abgelehnt |
bbzzbb | z2 | akzeptiert |
Erwartungshorizont zu Aufgabe b)
- z0: „noch keine Ziffer gelesen“
- z1: „zuletzt eine Ziffer gelesen“
- z2: „Ziffer schon gelesen, zuletzt ein Buchstabe“
Begründung (z. B.): Jeder Pfeil mit z führt nach z1, also war das zuletzt gelesene Zeichen dort eine Ziffer. z0 hat nur die b-Schleife als eingehenden Pfeil außer dem Startpfeil — dort wurde noch keine Ziffer gelesen.
Erwartungshorizont zu Aufgabe c)
In Worten: alle Wörter über \(\{b,z\}\), die mindestens ein \(z\) enthalten und auf \(b\) enden.
\[L(A)=\{\,w\in\{b,z\}^*\mid w \text{ enthält ein } z \text{ und endet auf } b\,\}\]Kennwortregel: „Das Kennwort muss mindestens eine Ziffer enthalten und mit einem Buchstaben enden.“ Gegenprobe: \(\varepsilon\), \(b\) und \(zbz\) werden abgelehnt, \(zb\) akzeptiert.
Erwartungshorizont zu Aufgabe d)
Aus jedem Zustand führt \(z\) nach z1 und danach \(b\) nach z2. Also landet jedes Wort \(w\) mit dem Anhang \(zb\) im Endzustand: \(wzb\in L(A)\).
Weil von jedem Zustand aus ein Endzustand erreichbar ist, gibt es keinen Zustand, aus dem ein Wort „nicht mehr zu retten“ ist — genau das wäre ein Fehlerzustand.
Der Prüfbaustein
16 BEAFB II–IIIEin Prüfbaustein in einer Lagerverwaltung liest Artikelnummern als Binärzahlen Bit für Bit von links nach rechts, also mit dem höchstwertigen Bit zuerst. Er verwendet den abgebildeten DEA \(B\) über \(\Sigma=\{0,\,1\}\).
- Untersuchen Sie das Verhalten von \(B\) für die Eingaben
110,1001,111,10101. Geben Sie dazu jeweils die Zustandsfolge und den Dezimalwert der Zahl an. (4 BE) - Analysieren Sie die Bedeutung der drei Zustände und beschreiben Sie \(L(B)\) als Menge. (4 BE)
- Hängt man an eine Binärzahl mit Wert \(x\) das Bit \(b\) an, hat die neue Zahl den Wert \(2x+b\). Zeigen Sie mit dieser Regel, dass alle sechs Übergänge von \(B\) zur Bedeutung „Rest bei Division durch 3“ passen. (4 BE)
- Eine Kollegin schlägt vor: „Für die Prüfung auf Teilbarkeit durch 5 genügen ebenfalls drei Zustände, man muss ja nur ‚teilbar‘ und ‚nicht teilbar‘ unterscheiden.“ Widerlegen Sie diese Aussage. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
1 und 10 mit dem Anhang 01.Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
110\(=6\): z0 \(\xrightarrow{1}\) z1 \(\xrightarrow{1}\) z0 \(\xrightarrow{0}\) z0 — akzeptiert1001\(=9\): z0 \(\xrightarrow{1}\) z1 \(\xrightarrow{0}\) z2 \(\xrightarrow{0}\) z1 \(\xrightarrow{1}\) z0 — akzeptiert111\(=7\): z0 \(\xrightarrow{1}\) z1 \(\xrightarrow{1}\) z0 \(\xrightarrow{1}\) z1 — abgelehnt10101\(=21\): z0 \(\xrightarrow{1}\) z1 \(\xrightarrow{0}\) z2 \(\xrightarrow{1}\) z2 \(\xrightarrow{0}\) z1 \(\xrightarrow{1}\) z0 — akzeptiert
Akzeptiert werden 6, 9 und 21, abgelehnt wird 7 — Vermutung: \(B\) akzeptiert die durch 3 teilbaren Zahlen.
Erwartungshorizont zu Aufgabe b)
z0, z1, z2 bedeuten: Der bisher gelesene Teil hat bei Division durch 3 den Rest 0, 1 bzw. 2 (z. B. 1 → z1, 10 \(=2\) → z2, 11 \(=3\) → z0, 100 \(=4\) → z1).
Dazu gehören auch \(\varepsilon\) (Wert 0) und Wörter mit führenden Nullen wie 0110.
Erwartungshorizont zu Aufgabe c)
Ist \(x=3q+r\), so gilt \(2x+b=6q+2r+b\); der Rest von \(2x+b\) ist also der Rest von \(2r+b\).
| Zustand (Rest r) | Zeichen b | \((2r+b)\bmod 3\) | Folgezustand laut Graph |
|---|---|---|---|
| z0 | 0 | \(0 \bmod 3 = 0\) | z0 |
| z0 | 1 | \(1 \bmod 3 = 1\) | z1 |
| z1 | 0 | \(2 \bmod 3 = 2\) | z2 |
| z1 | 1 | \(3 \bmod 3 = 0\) | z0 |
| z2 | 0 | \(4 \bmod 3 = 1\) | z1 |
| z2 | 1 | \(5 \bmod 3 = 2\) | z2 |
Alle sechs Folgezustände stimmen überein. Da der Start z0 zum Wert 0 (Rest 0) passt, steht \(B\) nach jedem Präfix im Zustand seines Rests; akzeptiert wird genau bei Rest 0.
Erwartungshorizont zu Aufgabe d)
Die Präfixe 1 (Rest 1) und 10 (Rest 2) sind beide nicht durch 5 teilbar, müssen aber unterschieden werden: Mit dem Anhang 01 entsteht 101 \(=5\) (teilbar) bzw. 1001 \(=9\) (nicht teilbar).
Endeten beide im selben Zustand, müsste der Automat beide Wörter gleich behandeln — Widerspruch. Ebenso lassen sich alle fünf Reste 0 bis 4 paarweise durch einen passenden Anhang trennen. Ein DEA für Teilbarkeit durch 5 braucht also mindestens fünf Zustände; „teilbar/nicht teilbar“ reicht als Gedächtnis nicht aus.