Automaten implementieren

Beispiel: Der Automat akzeptiert über \(\Sigma=\{a,\,b\}\) alle Wörter mit gerader Anzahl b. z0 ist Start- und Endzustand, jedes b wechselt zwischen z0 und z1.

• Zustände:als ganze Zahlen kodiert: z0 → 0, z1 → 1, zF → 2.
• Attribut:private int zustand speichert den aktuellen Zustand.
• uebergang(char c):verarbeitet ein Zeichen: switch über den Zustand, darin if über das Zeichen.
• Ungültige Zeichen:alles außerhalb von \(\Sigma\) führt in den Fehlerzustand zF.
• akzeptiert(String wort):Startzustand setzen, jedes Zeichen an uebergang geben, am Ende auf Endzustand prüfen.

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

    public void uebergang(char c) {
        switch (zustand) {
            case 0:
                if (c == 'a') { zustand = 0; }
                else if (c == 'b') { zustand = 1; }
                else { zustand = 2; }
                break;
            case 1:
                if (c == 'a') { zustand = 1; }
                else if (c == 'b') { zustand = 0; }
                else { zustand = 2; }
                break;
            default:
                zustand = 2;    // zF: kein Weg zurück
        }
    }

    public boolean akzeptiert(String wort) {
        // … setzt du im Applet zusammen
    }
}

Bei vielen Zuständen wird der switch lang. Kürzer: Die Übergangstabelle wird direkt als zweidimensionales Feld gespeichert.

• delta[z][s]:Zeile = Zustand, Spalte = Nummer des Zeichens, Eintrag = Folgezustand.
• spalte(char c):übersetzt das Zeichen in die Spaltennummer, -1 für Zeichen außerhalb von \(\Sigma\).
• Ein Schritt:zustand = delta[zustand][spalte(c)]; — ein Tabellenzugriff statt vieler Fälle.
• Anderer Automat:nur Tabelle, Spaltenfunktion und Endzustände austauschen, die Methoden bleiben gleich.

public class GeradeBTabelle {
    //                         a  b
    private int[][] delta = { {0, 1},     // z0
                              {1, 0},     // z1
                              {2, 2} };   // zF

    private int spalte(char c) {
        if (c == 'a') { return 0; }
        if (c == 'b') { return 1; }
        return -1;                        // Zeichen nicht in Σ
    }
}

Die Zeilen der Methode akzeptiert sind durcheinandergeraten. Bringe sie in die richtige Reihenfolge — mit der Maus ziehen oder antippen, mit der Tastatur Leertaste zum Aufnehmen, Pfeiltasten zum Verschieben. Oben wählst du Variante A (mit uebergang) oder B (mit Tabelle). Stimmt alles, lässt du den Code ein Wort verarbeiten.

}

Halte fest: Die Schleife enthält genau einen Übergang je Zeichen, der Zustand wird vor der Schleife auf den Start gesetzt und nach der Schleife ausgewertet. Unterwegs wird nie entschieden — außer im Fehlerzustand, aus dem es kein Zurück gibt.