Übung AFB II

Gegeben ist ein DEA über \(\Sigma=\{a,\,b\}\).

Analysieren Sie den Automaten, indem Sie für jeden Zustand seine Bedeutung notieren. Wie viele Wörter der Länge 3 bzw. der Länge 4 akzeptiert er?

Ein Schüler zeichnet den folgenden Graphen über \(\Sigma=\{a,\,b,\,c\}\), ohne einen Vermerk darunter zu schreiben.

Begründen Sie, warum der Graph keinen vollständigen DEA darstellt. Wie viele Übergänge fehlen? Wie viele Übergänge hat der Automat, nachdem Sie ihn um einen Fehlerzustand zF vervollständigt haben?

Der folgende DEA liest Binärzahlen, das höchstwertige Bit zuerst. Er akzeptiert genau die Binärzahlen, die durch 3 teilbar sind.

Erläutern Sie, warum Zustand zr bedeutet: „Der bisher gelesene Wert lässt beim Teilen durch 3 den Rest r.“ In welchem Zustand endet der Automat für 100000? (Nummer angeben)

Gesucht ist ein vollständiger DEA über \(\Sigma=\{0,\,1\}\), der genau die geraden Binärzahlen ohne führende Null akzeptiert: 0, 10, 110, 1000 ja, aber 00, 010, ε, 11 nein.

Erstellen Sie die Übergangstabelle mit einer Bedeutung für jeden Zustand. Wie viele Zustände (einschließlich Fehlerzustand) benötigt Ihr Automat mindestens, und wie viele davon sind Endzustände?

Der DEA für ganze Zahlen mit optionalem Vorzeichen hat die Zustände z0 (Start), z1 (Vorzeichen gelesen), z2 (mindestens eine Ziffer, Endzustand) und zF. Vorzeichen sind nur als erstes Zeichen erlaubt.

Implementieren Sie den Automaten als Klasse mit einem ganzzahligen Attribut zustand (z0 → 0, z1 → 1, z2 → 2, zF → 3), einer Methode uebergang für ein Zeichen und einer Methode akzeptiert für ein Wort. Zeichen außerhalb von Σ führen in zF. Welchen Wert hat zustand nach dem Aufruf akzeptiert("-0-")?

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

    public void uebergang(char c) {
        boolean ziffer = c >= '0' && c <= '9';
        boolean vorzeichen = c == '+' || c == '-';
        switch (zustand) {
            case 0:
                if (vorzeichen) { zustand = 1; }
                else if (ziffer) { zustand = 2; }
                else { zustand = 3; }
                break;
            case 1:
            case 2:
                if (ziffer) { zustand = 2; }
                else { zustand = 3; }
                break;
            default:
                zustand = 3;         // zF: kein Weg zurück
        }
    }

    public boolean akzeptiert(String wort) {
        zustand = 0;
        for (int i = 0; i < wort.length(); i++) {
            uebergang(wort.charAt(i));
        }
        return zustand == 2;
    }
}

Zwei Entwürfe sollen genau die Wörter über {0, 1} akzeptieren, die 101 als zusammenhängendes Teilwort enthalten.

Vergleichen Sie die beiden Entwürfe. Welche Länge hat das kürzeste Wort, das die Entwürfe unterschiedlich behandeln?

Ein Mealy-Automat steuert das Treppenhauslicht: T ist ein Tastendruck, t meldet, dass eine Minute vergangen ist. Die Zustände an2 und an1 geben an, wie viele Minuten das Licht noch brennt.

Untersuchen Sie das Verhalten für die Eingabefolge T t T t t t. Nach dem wievielten Eingabezeichen geht das Licht aus? Wie viele Minuten brennt es nach dem letzten Tastendruck noch?

Ein Fahrkartenautomat verkauft Fahrkarten zu 2 € und nimmt bisher nur 1-€- und 2-€-Münzen an (Zustände 0 € und 1 €). Er soll zusätzlich 50-ct-Münzen annehmen; zu viel Gezahltes gibt er zusammen mit der Fahrkarte als Wechselgeld zurück.

Erweitern Sie den Mealy-Automaten, sodass \(\Sigma=\{50\text{ ct},\,1\text{ €},\,2\text{ €}\}\) gilt und die Zustände das bisher eingeworfene Guthaben speichern. Wie viele Zustände hat der erweiterte Automat, und wie viele Übergänge geben Wechselgeld aus?

Überprüfen Sie für jede Sprache, ob es einen DEA gibt, der sie erkennt. Wie viele der sechs Sprachen sind regulär?

1. Wörter über {a, b} mit gleich vielen a wie b
2. Wörter über {a, b}, deren Anzahl der a durch 5 teilbar ist
3. korrekt geklammerte Ausdrücke mit Schachtelungstiefe höchstens 3
4. Palindrome über {a, b}, z. B. aabbaa
5. \(\{a^n b^m \mid n,\,m\ge 0\}\): erst beliebig viele a, dann beliebig viele b
6. \(\{a^n b^n \mid 0\le n\le 100\}\)

Der Mealy-Automat erhält eine Binärzahl mit dem niederwertigsten Bit zuerst und soll die um 1 erhöhte Zahl ausgeben, ebenfalls niederwertigstes Bit zuerst. Beispiel: 0111 steht für \(0\cdot1+1\cdot2+1\cdot4+1\cdot8=14\).

Bestätigen Sie mit einem Ablaufprotokoll, dass der Automat für 0111 die Zahl 15 ausgibt. Welchen Dezimalwert hat die Ausgabe zur Eingabe 1110?