MINT lernen

Übungen: Einen DEA entwickeln

Zehn Übungen vom Gedächtnis des Automaten bis zum fertigen Entwurf — mit Bezeichnern, E-Mails und Kennzeichen.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Übungen zum Planen, Ausfüllen, Reparieren und Entwerfen — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.

A1
Der Weg zum Automaten
AFB I

Sara soll einen DEA für Variablennamen entwickeln. Stellen Sie ihr Vorgehen in der richtigen Reihenfolge dar.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1Eingabealphabet Σ festlegen
2Überlegen, was sich der Automat merken muss — jede mögliche Antwort wird ein Zustand mit Bedeutung
3Startzustand und Endzustände festlegen
4Für jeden Zustand und jedes Zeichen den Folgezustand bestimmen, bei Bedarf mit Fehlerzustand
5Mit Testwörtern und Grenzfällen prüfen
Erst das Gedächtnis, dann die Pfeile: Welche Zustände es gibt, folgt aus der Frage, was sich der Automat merken muss. Start und Ende ergeben sich aus den Bedeutungen, die Übergänge zuletzt. Typischer Fehler: sofort Pfeile zeichnen. Dann entstehen Zustände ohne klare Bedeutung, und beim Testen weiß niemand, was repariert werden muss.
Ansatz: Ohne Alphabet weiß man nicht, welche Zeichen überhaupt vorkommen.
Weiter: Übergänge kann man erst eintragen, wenn die Zustände mit ihrer Bedeutung feststehen. Getestet wird am Schluss.
A2
Was muss der Automat sich merken?
AFB I

Ein Variablenname (Bezeichner) beginnt mit einem Buchstaben, danach folgen beliebig viele Buchstaben oder Ziffern. Nennen Sie alle Informationen, die ein DEA für Bezeichner beim Lesen im Gedächtnis behalten muss.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.
Drei Zustände genügen: z0 „noch nichts gelesen“ (Start), z1 „gültiger Anfang, alles in Ordnung“ (Endzustand) und zF „begann mit einer Ziffer“. Die letzten beiden Informationen fallen zusammen — wer mit einer Ziffer beginnt, ist nicht mehr zu retten. Typischer Fehler: Ziffern oder Länge zählen wollen. Beides ändert nichts an der Entscheidung und würde unendlich viele Zustände verlangen.
Ein passender DEA (b = Buchstabe, z = Ziffer)
z0z1zFbzb, zb, z
Ansatz: Fragen Sie bei jeder Information: Ändert sie etwas daran, ob das Wort am Ende angenommen wird?
Weiter: Nach dem ersten Buchstaben ist alles erlaubt — ab da muss sich der Automat nichts Neues mehr merken.
A3
Testwörter für Bezeichner
AFB I

Bevor der Automat gebaut wird, legt man Testwörter fest. Ordnen Sie jedes Wort zu: Muss ein korrekter Bezeichner-DEA es annehmen oder ablehnen?

Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).
1muss angenommen werden
2muss abgelehnt werden
Ein einzelner Buchstabe wie x ist der kürzeste gültige Bezeichner — ein wichtiger Grenzfall. Das leere Wort ist kein Bezeichner, der Startzustand darf also kein Endzustand sein. Typischer Fehler: 7up annehmen, weil danach Buchstaben folgen. Entscheidend ist allein das erste Zeichen.
Ansatz: Prüfen Sie nur zwei Dinge: Gibt es ein erstes Zeichen — und ist es ein Buchstabe?
Weiter: Denken Sie an die Grenzfälle: das leere Wort und Wörter der Länge 1.
A4
Regeln für den Entwurf
AFB I

Geben Sie zu jeder Aussage über den Entwurf eines DEA an, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Vollständigkeit prüft man mit der Formel |Z| · |Σ| — jede Zeile der Übergangstabelle muss voll sein, auch die von zF. Typischer Fehler: glauben, ein Fehlerzustand gehöre immer dazu. Er ist nur nötig, wenn es Wörter gibt, die durch kein Weiterlesen mehr gültig werden können.
Ansatz: Eine Übergangstabelle hat eine Zeile je Zustand und eine Spalte je Zeichen.
Weiter: Welche Rolle spielt der Startzustand, wenn das Wort gar kein Zeichen enthält?
A5
Dezimalzahlen mit Komma
AFB II

Ein DEA soll Dezimalzahlen wie 3,14, 12 oder 0,05 erkennen: mindestens eine Ziffer, danach optional ein Komma mit mindestens einer weiteren Ziffer. Die Zustände und ihre Bedeutungen stehen fest. Erstellen Sie die Übergangstabelle.

Tragen Sie den Folgezustand ein (z. B. z2 oder zF). Die Zeile von zF ist vorgegeben. Enter in einem Feld prüft ebenfalls.
Zustand — BedeutungZifferKomma
z0 — noch nichts gelesen (Start)
z1 — Ziffern vor dem Komma (Endzustand)
z2 — Komma gelesen
z3 — Ziffern nach dem Komma (Endzustand)
zF — FehlerzustandzFzF
Probe mit Testwörtern: 3,14 z0 → z1 → z2 → z3 → z3 (angenommen), ,5 z0 → zF (abgelehnt), 7, endet in z2 (abgelehnt), 1,2,3 gerät beim zweiten Komma in zF. Typischer Fehler: δ(z3, Komma) = z2 setzen. Dann würde 1,2,3 angenommen — eine Zahl hat aber nur ein Komma.
Ansatz: Fragen Sie für jedes Feld: Was weiß der Automat, nachdem er in diesem Zustand dieses Zeichen gelesen hat?
Weiter: Ein Komma ist nur direkt nach Ziffern vor dem Komma erlaubt, und nur einmal. Ist das Wort nicht mehr zu retten, heißt das Ziel zF.
A6
Sprache und Gedächtnis
AFB II

Für jede Sprache über \(\Sigma=\{a,\,b\}\) braucht der DEA ein anderes Gedächtnis. Bestimmen Sie zu jeder Sprache, welche Zustände (mit Bedeutung) ein möglichst kleiner DEA hat, und verbinden Sie beide.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Drei der Automaten haben vier Zustände — die Anzahl allein entscheidet also nichts, erst die Bedeutung. Bei „genau zwei a“ braucht man einen Zustand für „mehr als 2“: Er ist ein Fehlerzustand, denn weitere a machen das Wort nie wieder gültig. Typischer Fehler: bei „zweites Zeichen ist b“ das zuletzt gelesene Zeichen merken wollen. Wichtig ist nur die Position — danach ist die Entscheidung gefallen.
Ansatz: Formulieren Sie für jede Sprache die Frage: Was muss ich nach dem Lesen eines Teilworts wissen, um am Ende richtig zu entscheiden?
Weiter: Zwei Sprachen führen zu einem Fehlerzustand, eine zu einem Zyklus. Welche?
A7
Fehlersuche: Lenas E-Mail-Automat
AFB II

Lena entwirft einen DEA für E-Mail-Adressen in Kurzform wie max@schule.de: mindestens ein Buchstabe, dann @, mindestens ein Buchstabe, genau ein Punkt, mindestens ein Buchstabe. Sie verwendet \(\Sigma=\{b,\,@,\,.\}\), wobei b für einen Buchstaben steht. Überprüfen Sie ihre Einträge — drei sind falsch.

ZustandBedeutung
z0noch nichts gelesen
z1Name vor dem @
z2@ gelesen
z3Domain nach dem @
z4Punkt gelesen
z5Endung nach dem Punkt
zFFehlerzustand
In Lenas Übergängen stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.
Solche Fehler findet man mit Testwörtern je Zustand: max@.de prüft z2, a@b.c prüft den Weg über z4 nach z5, a@b.c.d prüft z5. Typischer Fehler: Übergänge „nach Gefühl“ auf bekannte Adressen wie a@b.c.d anpassen, statt sich an die Vorgabe zu halten.
Ansatz: Fragen Sie bei jedem Eintrag: Passt der Folgezustand zur Bedeutung — was weiß der Automat nach diesem Zeichen wirklich?
Weiter: Spielen Sie a@b.c durch. Kommt der Automat in z5 an? Und was soll nach der Endung bei einem weiteren Punkt passieren?
A8
Binärliterale wie 0b1011
AFB II Mix

In Java schreibt man Binärzahlen als Literal mit dem Präfix 0b, etwa 0b1011 (Kapitel Codierung). Ein DEA über \(\Sigma=\{0,\,1,\,b\}\) soll genau die Wörter 0b gefolgt von mindestens einer Binärziffer akzeptieren. Bedeutungen: z0 Anfang, z1 „0 gelesen“, z2 „0b gelesen“, z3 „mindestens eine Binärziffer“. Ergänzen Sie die Tabelle um die fehlenden Einträge.

Zustand01b
z0??zF
z1zF??
z2z3z3?
z3?z3?
zFzFzFzF
Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.

δ(z0, 0) =

δ(z0, 1) =

δ(z1, 1) =

δ(z1, b) =

δ(z2, b) =

δ(z3, 0) =

δ(z3, b) =

Endzustand:

Wert des Literals 0b1011 im Dezimalsystem:

Nur der Weg z0 →0→ z1 →b→ z2 →0/1→ z3 führt zum Ziel; z3 hat für 0 und 1 Schleifen. Jedes andere Zeichen an diesen Stellen ist nicht mehr zu retten. \(1011_2=8+2+1=11\). Typischer Fehler: δ(z0, 1) = z3 setzen, weil 1 ja eine Binärziffer ist — ohne Präfix 0b ist es aber kein Binärliteral.
Ansatz: Das Präfix muss genau 0b lauten — erst danach dürfen Binärziffern kommen.
Weiter: Stellenwerte von rechts: 1, 2, 4, 8.
A9
Höchstens 1000 Zeichen
AFB III Trick

Ein vollständiger DEA über \(\Sigma=\{a,\,b\}\) soll genau die Wörter mit höchstens 1000 Zeichen akzeptieren. Ermitteln Sie, wie viele Zustände er mindestens braucht.

Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
Der Automat muss die Längen 0, 1, …, 1000 unterscheiden — das sind 1001 Zustände, alle Endzustände (auch der Startzustand, denn ε hat 0 Zeichen). Dazu kommt ein Fehlerzustand für „mehr als 1000 Zeichen“, damit der DEA vollständig ist: 1002. Typischer Fehler: 1000 antworten und dabei die Länge 0 oder den Fehlerzustand vergessen. Eine riesige, aber endliche Grenze ist für einen DEA kein Problem.
Ansatz: Was muss sich der Automat merken? Zählen Sie die möglichen Antworten, beginnend beim leeren Wort.
Weiter: Nach dem 1001. Zeichen ist das Wort nicht mehr zu retten — wohin führt dieser Übergang?
A10
Ein DEA für Kfz-Kennzeichen
AFB III

Vereinfachte Kennzeichen wie OS-AB123: 1 bis 3 Buchstaben, ein Bindestrich, 1 oder 2 Buchstaben, dann 1 bis 4 Ziffern. Alphabet: \(\Sigma=\{B,\,-,\,Z\}\) mit B = Buchstabe, Z = Ziffer. Entwerfen Sie gedanklich einen möglichst kleinen vollständigen DEA und beantworten Sie die Fragen.

Arbeiten Sie die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. Zustände für den Teil vor dem Bindestrich (nach 1, 2, 3 Buchstaben)
  2. Alle Zustände ohne Fehlerzustand, Startzustand mitgezählt
  3. Davon Endzustände
  4. Übergänge im vollständigen DEA mit Fehlerzustand
  5. Wie viele dieser Übergänge enden in zF?
Zustände: Start, 1/2/3 Buchstaben, „Bindestrich gelesen“, 1/2 Buchstaben, 1/2/3/4 Ziffern — 11 Stück, dazu zF. Endzustände sind die vier Ziffern-Zustände. Vollständig: \(12\cdot 3=36\) Übergänge. Nur 13 davon führen weiter (z. B. aus „2 Buchstaben“ mit B oder −); die übrigen 20 aus den 11 Zuständen und die 3 Schleifen an zF enden in zF: 23. Typischer Fehler: für „1 bis 3 Buchstaben“ nur einen Zustand mit Schleife zeichnen — dann würden auch OSNA-B1 und längere Unterscheidungszeichen angenommen.
Ansatz: Ein DEA kann nur zählen, indem er für jede Anzahl einen eigenen Zustand hat. „1 bis 3“ braucht also drei Zustände.
Weiter: Zählen Sie die Übergänge, die nicht in zF enden, Zustand für Zustand — und ziehen Sie ab.