Die Adressprüfung
14 BEAFB I–IIEin Anmeldeformular prüft, ob eine eingegebene E-Mail-Adresse die richtige Form hat. Damit der Automat klein bleibt, wird jedes Zeichen vorher ersetzt: Buchstaben und Ziffern durch b, das At-Zeichen bleibt @, der Punkt bleibt .. Aus lea@schule.de wird so bbb@bbbbbb.bb.
Die Abbildung zeigt den verwendeten DEA über \(\Sigma=\{b,\,@,\,.\}\).
- Nennen Sie den Startzustand und die Endzustände des Automaten und geben Sie die Anzahl der Übergänge an, die der vollständige Automat einschließlich zF besitzt. (3 BE)
- Wenden Sie den Automaten auf die Wörter
b@b.b,b@bb,b.b@b.b,b@b.b.ban. Geben Sie jeweils die Zustandsfolge an und entscheiden Sie, ob das Wort akzeptiert wird. (4 BE) - Erstellen Sie die vollständige Übergangstabelle des Automaten einschließlich des Fehlerzustands. (4 BE)
- Erklären Sie, warum der Übergang mit dem Punkt aus z5 nach z4 und nicht nach z3 führt, und welche Adressen fälschlich akzeptiert würden, wenn z3 ebenfalls Endzustand wäre. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
lea@schule.nds.de.Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Startzustand z0, einziger Endzustand z5.
Mit zF gibt es 7 Zustände, also \(7\cdot3=21\) Übergänge; eingezeichnet sind 9, die übrigen 12 führen nach zF.
Erwartungshorizont zu Aufgabe b)
b@b.b: z0 \(\xrightarrow{b}\) z1 \(\xrightarrow{@}\) z2 \(\xrightarrow{b}\) z3 \(\xrightarrow{.}\) z4 \(\xrightarrow{b}\) z5 — akzeptiertb@bb: z0 \(\xrightarrow{b}\) z1 \(\xrightarrow{@}\) z2 \(\xrightarrow{b}\) z3 \(\xrightarrow{b}\) z3 — abgelehntb.b@b.b: z0 \(\xrightarrow{b}\) z1 \(\xrightarrow{.}\) zF \(\xrightarrow{b}\) zF \(\xrightarrow{@}\) zF \(\xrightarrow{b}\) zF \(\xrightarrow{.}\) zF \(\xrightarrow{b}\) zF — abgelehntb@b.b.b: z0 \(\xrightarrow{b}\) z1 \(\xrightarrow{@}\) z2 \(\xrightarrow{b}\) z3 \(\xrightarrow{.}\) z4 \(\xrightarrow{b}\) z5 \(\xrightarrow{.}\) z4 \(\xrightarrow{b}\) z5 — akzeptiert
Bei b@bb fehlt der Punkt nach dem @, bei b.b@b.b steht der Punkt vor dem @, wofür es aus z1 keinen Pfeil gibt.
Erwartungshorizont zu Aufgabe c)
| Zustand | b | @ | . |
|---|---|---|---|
| z0 | z1 | zF | zF |
| z1 | z1 | z2 | zF |
| z2 | z3 | zF | zF |
| z3 | z3 | zF | z4 |
| z4 | z5 | zF | zF |
| z5 | z5 | zF | z4 |
| zF | zF | zF | zF |
(→ Startzustand, doppelt unterstrichen: Endzustand)
Erwartungshorizont zu Aufgabe d)
z3 bedeutet „nach dem @, noch kein Punkt“, z4 „gerade einen Punkt gelesen, jetzt muss ein Zeichen folgen“. Ein weiterer Punkt in z5 beginnt einen neuen Domain-Teil (z. B. schule.nds.de): Danach genügt ein einziges b, um wieder gültig zu enden — genau das leistet z4.
Führte der Punkt nach z3, verlangte der Automat einen weiteren Punkt: b@b.b.b (etwa lea@schule.nds.de) endete in z3 und würde abgelehnt.
Wäre z3 Endzustand, würden Adressen ohne Punkt hinter dem @ akzeptiert, z. B. b@bb (etwa lea@schule) — die Top-Level-Domain fehlt.
Die Uhrzeit-Eingabe
16 BEAFB II–IIIEine Termin-App prüft Uhrzeiten im 24-Stunden-Format hh:mm mit einem DEA über \(\Sigma=\{0,\,1,\,\dots,\,9,\,:\}\). Gültig sind genau die Eingaben von 00:00 bis 23:59.
- Analysieren Sie die Verarbeitung der Eingaben
23:59,24:00,7:30mithilfe von Zustandsfolgen. (4 BE) - Erläutern Sie, warum der Automat nach der ersten Ziffer zwei verschiedene Zustände z1 und z2 benötigt, während nach dem Doppelpunkt ein Zustand z4 genügt. (4 BE)
- Die App soll zusätzlich einstellige Stunden wie
7:30oder0:05annehmen. Erweitern Sie den Automaten entsprechend, ohne neue Zustände einzuführen. (4 BE) - Ein Entwickler meint: „Ein endlicher Automat kann nur das Format prüfen. Ob eine Uhrzeit zu den Öffnungszeiten 08:00 bis 17:30 passt oder in der Zukunft liegt, kann er nicht entscheiden.“ Erörtern Sie diese Aussage. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
23:59: z0 \(\xrightarrow{2}\) z2 \(\xrightarrow{3}\) z3 \(\xrightarrow{:}\) z4 \(\xrightarrow{5}\) z5 \(\xrightarrow{9}\) z6 — akzeptiert24:00: z0 \(\xrightarrow{2}\) z2 \(\xrightarrow{4}\) zF \(\xrightarrow{:}\) zF \(\xrightarrow{0}\) zF \(\xrightarrow{0}\) zF — abgelehnt7:30: z0 \(\xrightarrow{7}\) zF \(\xrightarrow{:}\) zF \(\xrightarrow{3}\) zF \(\xrightarrow{0}\) zF — abgelehnt
24:00 scheitert an der zweiten Ziffer: Aus z2 gibt es nur Übergänge für 0 bis 3. 7:30 scheitert schon am ersten Zeichen, weil der Automat immer zwei Stundenziffern verlangt.
Erwartungshorizont zu Aufgabe b)
Die erlaubte zweite Stundenziffer hängt von der ersten ab: nach 0 oder 1 jede Ziffer (bis 19), nach 2 nur 0 bis 3 (bis 23). Der Automat muss sich also merken, ob die Stunde mit 2 begann — das ist die unterschiedliche Bedeutung von z1 und z2.
Bei den Minuten ist die Einerziffer immer frei (0 bis 9), egal welche Zehnerziffer 0 bis 5 gelesen wurde. Es gibt nichts zu unterscheiden, deshalb reicht je ein Zustand z4 und z5.
Erwartungshorizont zu Aufgabe c)
Neu: z0 \(\xrightarrow{3\text{–}9}\) z3 (3 bis 9 sind schon vollständige Stunden), z1 \(\xrightarrow{:}\) z4 und z2 \(\xrightarrow{:}\) z4 (0, 1, 2 können auch allein stehen). Nun gilt z. B. z0 \(\xrightarrow{7}\) z3 \(\xrightarrow{:}\) z4 \(\xrightarrow{3}\) z5 \(\xrightarrow{0}\) z6.
Erwartungshorizont zu Aufgabe d)
Teilweise falsch: Die Öffnungszeiten bilden eine feste, endliche Menge von Wörtern. Jede endliche Sprache lässt sich mit einem DEA erkennen; hier genügt es, die Übergänge einzuschränken (erste Ziffer 0 nur mit 8 oder 9, 1 mit 0 bis 7, bei 17 nur Minuten bis 30 usw.).
Richtig ist der zweite Teil: „In der Zukunft“ hängt von der aktuellen Uhrzeit ab. Die Sprache ändert sich also ständig; ein fest gebauter DEA kennt die Uhrzeit nicht. Man bräuchte für jede Minute einen eigenen Automaten oder — praktikabler — einen Vergleich im Programm.
Fazit: Ein DEA prüft mehr als nur das Format, solange die Bedingung fest und endlich beschreibbar ist.