Übungen: Automaten in Java

Jede Java-Zeile einer Automaten-Klasse setzt einen Teil des Modells um. Ordnen Sie jedem Code-Baustein seine Aufgabe im Automaten zu.

Ein DEA über Σ = {0, 1} akzeptiert genau die Binärzahlen, die durch 3 teilbar sind. Zustand zr bedeutet: Die bisher gelesene Zahl lässt beim Teilen durch 3 den Rest r. Zeichen außerhalb von Σ führen in den nicht eingetragenen Fehlerzustand zF.

Geben Sie für jede Lücke der Java-Klasse den passenden Eintrag an.

public class DurchDrei {
    private int zustand;        // 0 = z0, 1 = z1, 2 = z2, 3 = zF

    public void uebergang(char c) {
        switch (zustand) {
            case 0:
                if (c == '0') { zustand = 0; }
                else if (c == '1') { zustand = — wählen —0123; }
                else { zustand = 3; }
                break;
            case 1:
                if (c == '0') { zustand = — wählen —0123; }
                else if (c == '1') { zustand = — wählen —0123; }
                else { zustand = 3; }
                break;
            case 2:
                if (c == '0') { zustand = — wählen —0123; }
                else if (c == '1') { zustand = 2; }
                else { zustand = 3; }
                break;
            default:
                zustand = — wählen —0123;
        }
    }

    public boolean akzeptiert(String wort) {
        zustand = 0;
        for (int i = 0; i < wort.length(); i++) {
            uebergang(wort.charAt(i));
        }
        return — wählen —zustand == 0zustand == 3zustand != 3zustand > 0;
    }
}

Es geht um die beiden Implementierungen aus dem Kapitel: switch in uebergang(char c) und Tabelle int[][] delta. Nennen Sie zu jeder Aussage, ob sie stimmt.

Ein DEA prüft Uhrzeiten der Form hh:mm (z. B. 07:45). Er hat die Zustände z0 bis z6 und zusätzlich den Fehlerzustand zF. Σ besteht aus den zehn Ziffern und dem Doppelpunkt; jedes Zeichen bekommt eine eigene Spalte. Berechnen Sie, wie viele int-Werte das Feld delta speichert.

Die Klasse GanzeZahl prüft ganze Zahlen mit optionalem Vorzeichen (z. B. -17, +3, 42).

public class GanzeZahl {
    private int zustand;               // 0 = z0, 1 = z1, 2 = z2, 3 = zF
    //                         +  -  Ziffer
    private int[][] delta = { {1, 1, 2},     // z0
                              {3, 3, 2},     // z1
                              {3, 3, 2},     // z2
                              {3, 3, 3} };   // zF

    private int spalte(char c) {
        if (c == '+') { return 0; }
        if (c == '-') { return 1; }
        if (c >= '0' && c <= '9') { return 2; }
        return -1;
    }

    public boolean akzeptiert(String wort) {
        zustand = 0;
        for (int i = 0; i < wort.length(); i++) {
            int s = spalte(wort.charAt(i));
            if (s == -1) { zustand = 3; }
            else { zustand = delta[zustand][s]; }
        }
        return zustand == 2;
    }
}

Stellen Sie den Aufruf akzeptiert("-4+2") als Tracetabelle dar (Zustände als Zahlen 0–3, Rückgabe als true oder false).

Zur Fehlersuche soll die Klasse DurchDrei aus A2 eine zusätzliche Methode String zustandsfolge(String wort) erhalten. Für das Wort 110 soll sie den Text z0 z1 z0 z0 liefern — Startzustand zuerst, danach der Zustand nach jedem Zeichen. Implementieren Sie den Methodenrumpf, indem Sie die Zeilen ordnen.

Ein Spielautomat zeigt nacheinander die Symbole K (Kirsche) und S (Stern). Die Klasse Glueck prüft, ob eine Symbolfolge gewinnt.

public class Glueck {
    private int zustand;
    //                         K  S
    private int[][] delta = { {1, 0},     // z0
                              {2, 0},     // z1
                              {3, 0},     // z2
                              {3, 3} };   // z3

    private int spalte(char c) {
        if (c == 'K') { return 0; }
        if (c == 'S') { return 1; }
        return -1;
    }

    public boolean akzeptiert(String wort) {
        zustand = 0;
        for (int i = 0; i < wort.length(); i++) {
            int s = spalte(wort.charAt(i));
            if (s == -1) { return false; }
            zustand = delta[zustand][s];
        }
        return zustand == 3;
    }
}

Wenden Sie den Code auf das Wort KKSKKKS an: Geben Sie die Zustandsnummer nach den genannten Anfangsstücken an und zuletzt den Rückgabewert.

Von einer Automaten-Klasse über Σ = {a, b} kennen Sie nur die Übergangstabelle und die letzte Zeile von akzeptiert; akzeptiert setzt wie üblich zuerst zustand = 0;.

    //                         a  b
    private int[][] delta = { {1, 0},     // z0 (Start)
                              {1, 2},     // z1
                              {1, 0} };   // z2
    …
    return zustand == 2;                  // Ende von akzeptiert

Analysieren Sie den Automaten und markieren Sie alle zutreffenden Aussagen.

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.

Das ist die korrigierte Klasse für Dezimalzahlen aus A9 (zF = 4):

public void uebergang(char c) {
    boolean ziffer = c >= '0' && c <= '9';
    switch (zustand) {
        case 0: if (ziffer) { zustand = 1; } else { zustand = 4; } break;
        case 1: if (ziffer) { zustand = 1; } else if (c == ',') { zustand = 2; } else { zustand = 4; } break;
        case 2: if (ziffer) { zustand = 3; } else { zustand = 4; } break;
        case 3: if (ziffer) { zustand = 3; } else { zustand = 4; } break;
        default: zustand = 4;
    }
}
public boolean akzeptiert(String wort) {
    zustand = 0;
    for (int i = 0; i < wort.length(); i++) { uebergang(wort.charAt(i)); }
    return zustand == 1 || zustand == 3;
}

Beurteilen Sie jede Änderung: Liefert akzeptiert danach für jedes Wort und bei jedem Aufruf dasselbe Ergebnis wie vorher?