MINT üben

Automaten implementieren

Dreißig Übungen zur Implementierung eines DEA in Java — von AFB I bis AFB III.

Ihr Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Dreißig Übungen in gemischter Reihenfolge — Sie klicken, ziehen, ordnen, rechnen und knobeln. Jede Übung gibt Ihnen sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fahren Sie über ein unterstrichenes Arbeitswort, sehen Sie, was es genau von Ihnen verlangt.

A1
Das Drehkreuz am Eingang
AFB I

Ein Drehkreuz im Schwimmbad wird als DEA modelliert: Das Zeichen m (Münze einwerfen) entsperrt es, s (Schieben) sperrt es nach dem Durchgang wieder. Ein Wort gilt als angenommen, wenn das Drehkreuz am Ende gesperrt ist. Die Methode akzeptiert setzt zustand = 0;, ruft für jedes Zeichen uebergang(c) auf und liefert am Ende zustand == 0. Der Rumpf von uebergang lautet:

Java · uebergang(char c)
// 0 = z0 gesperrt, 1 = z1 frei
// 2 = zF
switch (zustand) {
  case 0:
    if (c == 'm') {
      zustand = 1;
    } else { zustand = 2; }
    break;
  case 1:
    if (c == 's') {
      zustand = 0;
    } else { zustand = 2; }
    break;
  default:
    zustand = 2;
}

Beschreiben Sie, wie akzeptiert("msm") abläuft: Spielen Sie den Ablauf Zeichen für Zeichen durch.

Spielen Sie den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt Sie weiter.
    Zustandsfolge: 0, 1, 0, 1. Entscheidend ist nur der Zustand nach dem letzten Zeichen: Hier ist es z1, und der einzige Endzustand ist z0. Dass z0 unterwegs besucht wurde, spielt keine Rolle.
    Gehen Sie das Wort von links nach rechts durch und verfolgen Sie in jedem Schritt, welcher case gerade gilt und welche Bedingung zutrifft.
    Maßgeblich ist der Wert von zustand nach dem letzten Zeichen. Vergleichen Sie ihn mit der Zahl in der letzten Zeile von akzeptiert.
    A2
    Fehlersuche: Dezimalzahlen
    AFB III

    Ein DEA soll Dezimalzahlen erkennen: mindestens eine Ziffer, danach optional ein Komma, auf das mindestens eine Ziffer folgt (12, 3,14 ja; ,5, 1,, 1,2,3 nein). Zustände: z0 Start, z1 „nur Ziffern“ (Endzustand), z2 „Komma gelesen“, z3 „Nachkommaziffern“ (Endzustand), zF = 4. Zeilen 1–7 bilden uebergang(char c), Zeilen 8–10 den Rumpf von akzeptiert. Überprüfen Sie den Code — drei Zeilen sind fehlerhaft.

    In diesem Code stecken Fehler. Klicken Sie genau die fehlerhaften Zeilen an — die richtigen müssen stehen bleiben.
    Die drei Fehler wirken ganz verschieden: <= führt zum Absturz, das fehlende break macht nur Wörter mit Komma kaputt, die falsche Rückgabe nur Wörter ohne Komma. Wer nur mit 3,14 testet, findet höchstens einen davon. Zeile 7 ohne break ist dagegen korrekt: Der letzte Fall braucht keins.
    Ansatz: Verfolgen Sie 1,5 und 12 im Kopf Zeichen für Zeichen durch den Code.
    Weiter: Achten Sie auf ein fehlendes break, auf die Schleifengrenze und darauf, welche Zustände Endzustände sind.
    A3
    Ist c ein Großbuchstabe?
    AFB IIMix

    Der Automat eines Kennzeichen-Prüfers soll in uebergang erkennen, ob das Zeichen c (Typ char) ein Großbuchstabe von A bis Z ist. Untersuchen Sie jede der sechs Bedingungen für die if-Abfrage und bewerten Sie sie mit einer Ampelfarbe.

    Geben Sie jeder Zeile eine Ampelfarbe: Klicken Sie auf das passende Licht und prüfen Sie dann. Mit der Tastatur: Tab zur Ampel, ↑/↓ oder 1–3 wählt die Farbe.
    • Rot: Fehlerhaft
    • Gelb: Richtig, aber umständlich
    • Grün: Richtig und gut
    1. c >= 'A' && c <= 'Z'

    2. c >= 65 && c <= 90

    3. c > 'A' && c < 'Z'

    4. c >= "A" && c <= "Z"

    5. c >= 'A' || c <= 'Z'

    6. c - 'A' >= 0 && c - 'A' < 26

    Bewertet wird nur, ob die Bedingung genau die Buchstaben A bis Z erfasst. Grün: richtig und gut lesbar. Gelb: richtig, aber umständlich oder unleserlich (Zeichencodes, Rechnung mit Abständen). Rot: falsch, weil Grenzen fehlen, oder es entsteht ein Compilerfehler oder eine immer wahre Bedingung.
    Setzen Sie probeweise A, M und Z in jede Bedingung ein: Welche Zeichen werden angenommen, welche nicht? Achten Sie auch auf die Anführungszeichen.
    Die Großbuchstaben A bis Z haben im Zeichencode die Nummern 65 bis 90, lückenlos. Eine Bedingung für einen Bereich braucht zwei Grenzen, die mit und verbunden sind und beide dazugehören.