Übung AFB III

Nicht eingezeichnete Übergänge führen in den Fehlerzustand zF.

Wichtig: z3 darf kein Endzustand sein (anna@de hat nur einen Domain-Teil), z4 auch nicht (Adresse endet auf Punkt). Der Rückweg z5 –.→ z4 erlaubt beliebig viele Domain-Teile, verhindert aber zwei Punkte hintereinander.

Gegenbeispiel: z0 \(\xrightarrow{\text{1}}\) z1 \(\xrightarrow{\text{1}}\) z2 \(\xrightarrow{\text{0}}\) z1 — 110 (Wert 6) wird akzeptiert, 6 ist nicht durch 4 teilbar. Die Behauptung ist falsch.

z1 bedeutet „letzte Ziffer 0“, z2 „letzte Ziffer 1“. Der Automat erkennt \(L(A)=\{\,w\in\{0,1\}^*\mid w \text{ endet auf } 0\,\}\), also die geraden Binärzahlen (führende Nullen zugelassen).

Korrektur: Eine Binärzahl ist genau dann durch 4 teilbar, wenn sie auf 00 endet (oder 0 ist). Der Automat muss sich die letzten zwei Ziffern merken: ein zusätzlicher Zustand „endet auf 00“ als einziger Endzustand neben „nur 0 gelesen“; z1 („endet auf genau eine 0“) ist dann kein Endzustand mehr.

Annahme: Ein DEA \(A\) mit \(k\) Zuständen erkennt \(L\).

Schubfach: Die \(k+1\) Wörter \(a^0,a^1,\dots,a^k\) können nicht alle in verschiedenen Zuständen enden. Also gibt es \(i<j\), sodass \(A\) nach \(a^i\) und nach \(a^j\) im selben Zustand \(z\) ist.

Gleiches Urteil: Ab \(z\) liest \(A\) bei \(a^ib^i\) und bei \(a^jb^i\) dieselben Zeichen \(b^i\) und endet im selben Zustand. Er akzeptiert also beide oder keines.

Widerspruch: \(a^ib^i\) enthält \(i\) mal a und \(i\) mal b, liegt also in \(L\); \(a^jb^i\) enthält \(j\ne i\) mal a, liegt nicht in \(L\). Die Annahme ist falsch — kein DEA erkennt \(L\), gleichgültig wie groß \(k\) ist.

\(L(A)=\{\,w\in\{a,b\}^*\mid |w|\ge 2 \text{ und das vorletzte Zeichen von } w \text{ ist } a\,\}\)

Begründung: z2 und z3 sind genau die Zustände, in denen das vorletzte gelesene Zeichen ein a war (…ab bzw. …aa). Jedes weitere Zeichen verschiebt das Fenster: z3 –b→ z2 (aus …aa wird …ab), z2 –a→ z1 (aus …ab wird …ba) usw. Wörter mit weniger als zwei Zeichen enden in z0 oder z1 und werden abgelehnt.

Gegenprobe: ε ✗, a ✗, ab ✓, ba ✗, bab ✓, abb ✗, baa ✓

public class VorletztesA {
    //                         a  b
    private int[][] delta = { {1, 0},     // z0
                              {3, 2},     // z1
                              {1, 0},     // z2  (Endzustand)
                              {3, 2} };   // z3  (Endzustand)
    private int zustand;

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

    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; }    // ungültiges Zeichen
            zustand = delta[zustand][s];
        }
        return zustand == 2 || zustand == 3;
    }
}

Der Automat selbst hat keinen Fehlerzustand: Aus jedem Zustand ist ein Endzustand erreichbar. Ungültige Zeichen fängt akzeptiert mit dem Sofort-Abbruch ab — ohne diese Prüfung würde delta[zustand][-1] eine Ausnahme auslösen. Wichtig ist außerdem zustand = 0; zu Beginn jedes Aufrufs.

\(\Omega=\{\text{an},\,\text{aus},\,\text{flackern}\}\), \(4\cdot 3=12\) Übergänge. D im Zustand an2/an1 gibt \(\varepsilon\) aus, weil das Licht bereits brennt.

Ausgabewort: an, flackern, aus, an, aus — die Minute t im Dauerbetrieb bleibt ohne Wirkung.

Jeder Pfeil steht für 26 Übergänge (einer je Buchstabe), insgesamt \(2\cdot 26=52\).

HALLO: H+1 = I, A+2 = C, L+1 = M, L+2 = N, O+1 = P → Ausgabewort ICMNP.

Entschlüsseln: gleicher Aufbau, Beschriftungen x / x−1 und x / x−2. Probe: ICMNP → HALLO.

Ein Zustand reicht nicht: Das zweite L in HALLO wird zu N, das erste zu M — dieselbe Eingabe, verschiedene Ausgaben. Bei nur einem Zustand hinge die Ausgabe allein vom Eingabezeichen ab.

Bedeutung: g = „bisher gerade Anzahl Einsen“, u = „ungerade Anzahl“. Die Ausgabe muss die Parität nach dem Lesen angeben.

Testeingabe 0110: Soll 0100, Ist 0110 — Abweichung im dritten Zeichen, genau beim Pfeil u –1→ g. Korrektur: Beschriftung 1 / 0. Eingaben ohne zwei Einsen (z. B. 100) hätten den Fehler nicht aufgedeckt.

Bewertung: Alle vier Wörter sollen akzeptiert werden — die Liste prüft nur, dass nichts Gültiges abgelehnt wird. Ein Automat, der jedes Wort akzeptiert, oder einer, bei dem z2 fälschlich Endzustand ist, bestünde sie. Grenzfälle fehlen völlig. Die Liste ist deshalb unzureichend.

Mit dieser Liste wird jeder Übergang aus z0 bis z3 mindestens einmal benutzt, und zu jedem Endzustand gibt es ein akzeptiertes und zu jedem anderen Zustand ein abgelehntes Wort, das dort endet.

Pro: Ein DEA liest jedes Zeichen genau einmal, braucht keinen Zusatzspeicher und ist mit einer Tabelle schnell implementiert. Für eine feste Höchsttiefe (z. B. 10) gibt es einen DEA: je Tiefe 0 bis 10 ein Zustand, dazu zF für „zu viele schließende Klammern“ oder „zu tief“.

Contra: Allgemein korrekt geklammerte Ausdrücke sind nicht regulär. Wie bei \(L=\{a^nb^n\mid n\ge 0\}\) müsste der Automat beliebig viele offene Klammern mitzählen; mit \(k\) Zuständen landen die Vorgeschichten (ⁱ und (^j für ein Paar \(i<j\) im selben Zustand, und (ⁱ)ⁱ und (^j)ⁱ würden gleich beurteilt. Ein reiner DEA prüft also nicht jeden Quelltext korrekt.

Fazit: Als alleiniges Werkzeug ist ein DEA ungeeignet. Vertretbar ist er nur mit einer dokumentierten Tiefenbegrenzung; sonst braucht das Programm zusätzlich einen unbeschränkten Zähler für die offenen Klammern — also mehr als endlich viele Zustände.