Übung AFB III

ε-Regeln nur bei B und D — genau dort darf die Zahl enden.

Gegenbeispiel: G mit S → aSb | ε ist kontextfrei und erzeugt \(L=\{a^nb^n\mid n\ge 0\}\).

Kein DEA: Hätte ein DEA k Zustände, würden zwei der Vorgeschichten \(a^0,\dots,a^k\), etwa \(a^i\) und \(a^j\) mit \(i<j\), im selben Zustand enden. Dann behandelt er \(a^ib^i\in L\) und \(a^jb^i\notin L\) gleich — Widerspruch. „Genug Zustände“ hilft nicht, weil das Argument für jedes k gilt.

Also: Jede reguläre Sprache ist kontextfrei, aber nicht umgekehrt.

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

Schubfach: Die k + 1 Vorgeschichten \(a^0, a^1, \dots, a^k\) enden in nur k Zuständen; zwei davon, \(a^i\) und \(a^j\) mit \(i<j\), im selben Zustand z.

Gleiches Urteil: Ab z liest A bei \(a^ib^{2i}\) und \(a^jb^{2i}\) dieselben Zeichen, endet also im selben Zustand — beide werden akzeptiert oder beide abgelehnt.

Widerspruch: \(a^ib^{2i}\in L\), aber \(a^jb^{2i}\notin L\), da \(2i\ne 2j\). Die Annahme ist falsch: Kein DEA erkennt L. (Ein Kellerautomat schafft es, siehe S → aSbb | ε.)

Σ = {a, b, c}, Γ = {A, #}, Endzustand z4.

Deterministisch: Von z3 geht der ε-Übergang nur mit # aus, alle anderen Übergänge von z3 haben A oben. Das Wort aabbcccc wird akzeptiert.

Pro: Die Syntax — geschachtelte Blöcke, Klammern, Ausdrücke mit Punkt vor Strich — wird mit kontextfreien Grammatiken beschrieben; ein Parser (im Kern ein Kellerautomat) prüft sie für beliebige Schachtelungstiefe.

Contra: Viele Regeln hängen vom Kontext ab: Eine Variable muss vor ihrer Verwendung deklariert sein, Typen müssen passen, ein Methodenaufruf braucht so viele Argumente wie Parameter. Das ähnelt \(\{a^nb^nc^n\}\) und geht über einen Keller hinaus; Compiler prüfen es mit Symboltabellen in einer eigenen Phase. Außerdem sagt syntaktische Korrektheit nichts darüber, ob das Programm das Gewünschte tut.

Fazit: Ein Kellerautomat prüft die Syntax vollständig, nicht aber die gesamte Korrektheit.

Mehrdeutig: Für ()() gibt es mehrere Bäume, z. B. S → SS mit den Teilen () und (), oder S → SS mit links S → ε und rechts S ⇒* ()(). Wegen S → SS und S → ε gibt es sogar unendlich viele Bäume für jedes Wort.

Beurteilung: Die Sprache ist richtig beschrieben, aber ein Parser kann keine eindeutige Struktur bestimmen — ungeeignet.

Besser: S → (S)S | ε. Das erste Zeichen entscheidet: „(“ erzwingt S → (S)S, sonst S → ε. Zu jedem Wort gibt es genau einen Baum; das ist auch die Grundlage des deterministischen Kellerautomaten.

Konstruktion: Füge ein neues Nichtterminal E mit der einzigen Regel E → ε hinzu und ersetze jede Regel A → a durch A → aE.

Gleiche Sprache: Jeder Ableitungsschritt … ⇒ wA ⇒ wa der alten Grammatik wird zu … ⇒ wA ⇒ waE ⇒ wa; umgekehrt kann E nur verschwinden, also entsteht nichts Neues. Alle anderen Regeln bleiben gleich.

Deutung am DEA: E ist genau der zusätzliche Endzustand zE, der bei der Umwandlung Grammatik → DEA entsteht.

public class Codewort {
    // Grammatik: S → xA | yS, A → xA | yB, B → xS | yB | ε
    // Zustände: 0 = S, 1 = A, 2 = B
    private int zustand;

    public boolean akzeptiert(String wort) {
        zustand = 0;
        for (int i = 0; i < wort.length(); i++) {
            char c = wort.charAt(i);
            if (c != 'x' && c != 'y') return false;
            switch (zustand) {
                case 0:
                    if (c == 'x') zustand = 1;
                    break;
                case 1:
                    if (c == 'y') zustand = 2;
                    break;
                default:
                    if (c == 'x') zustand = 0;
            }
        }
        return zustand == 2;
    }
}

Test: xy, yxyy, xxyyy → true; xyx, das leere Wort und xz → false. Die Sprache: Wörter, die auf x und mindestens ein y enden.

Theorie: Die Sprache aller korrekten Klammerausdrücke ist nicht regulär; jeder DEA scheitert an einer genügend großen Tiefe. Beschränkt man die Tiefe auf t, genügen t + 1 Zustände für die Tiefen 0 bis t und zF — die Sprache ist dann regulär.

Praxis: Für eine Tiefe bis 999 998 funktioniert der Vorschlag korrekt, ist aber absurd groß: Die Zustände unterscheiden sich nur in einer Zahl. Ein Programm mit einer Zählvariablen (ein Keller mit einer Symbolart) leistet dasselbe ohne Grenze und in wenigen Zeilen.

Bewertung: Korrekt nur mit Einschränkung, unnötig aufwendig — ein Zähler bzw. Kellerautomat ist die bessere Lösung, zumal mit mehreren Klammerarten ohnehin ein Keller nötig ist.

Zu aabaaaab: q0 –a→ q1 –a→ q2 –b→ q0 –a→ q1 –a→ q2 –a/X→ q0 –a→ q1 –b→ q0. Ausgabewort: X (vorher XX). Die ersten beiden a zählen nicht mehr, weil das b dazwischen zurücksetzt.