Probe-Klausur

Erwartungshorizont:

Akzeptiert: H-AB12, OS-KL1 (3 P). HAN-X7: drei Buchstaben vor dem Bindestrich; H-A1234: vier Ziffern; B-X endet in z4, H-12 fehlt der zweite Buchstabenblock.

Erwartungshorizont:

Zustände z0 bis z8 und zF: \(|Z|=10\), \(|\Sigma|=3\) → \(10\cdot 3=30\) Übergänge (2 P). Davon sind 10 eingezeichnet, 17 führen nach zF, 3 sind Schleifen an zF.

Erwartungshorizont:

z2: zwei Buchstaben des Kreises gelesen; z3: Bindestrich gelesen, noch kein Buchstabe danach; z5: zwei Buchstaben nach dem Bindestrich, noch keine Ziffer; z7: genau zwei Ziffern gelesen (je 1 P). z1 bedeutet „ein Buchstabe des Kreises“, z6 „genau eine Ziffer“, z8 „drei Ziffern — keine weitere erlaubt“.

Erwartungshorizont:

Neuer Zustand z2′ („drei Buchstaben des Kreises gelesen“): z2 –B→ z2′, z2′ –-→ z3; alle anderen Eingaben in z2′ führen nach zF. Mit z0 bis z8 und z2′ sind das 10 Zustände ohne zF (1 P). Eine Schleife an z2 würde beliebig lange Kreiskennungen erlauben (2 P).

Erwartungshorizont:

Die Kennzeichen-Sprache ist endlich: höchstens 4 Buchstaben und 3 Ziffern. Ein DEA kann die Anzahl der Buchstaben (0–4) im Zustand mitführen und beim Lesen der Ziffern herunterzählen — endlich viele Kombinationen. Anders als bei \(L=\{a^nb^n\mid n\ge 0\}\) muss keine unbeschränkte Anzahl gespeichert werden (3 P).

Erwartungshorizont:

z2: / und x bleiben im Kommentar, * → z3. z3: / schließt ab (z4), ein weiteres * bleibt in z3 (**/ soll schließen), x → zurück nach z2 (je 1 P).

Erwartungshorizont:

Akzeptiert: /**/, /*x*/, /***/ (3 P).

Erwartungshorizont:

public class Kommentar {
    //                         /  *  x
    private int[][] delta = { {1, 5, 5},     // z0
                              {5, 2, 5},     // z1
                              {2, 3, 2},     // z2
                              {4, 3, 2},     // z3
                              {5, 5, 5},     // z4 (Endzustand)
                              {5, 5, 5} };   // zF
    private int zustand;

    private int spalte(char c) {
        if (c == '/') { return 0; }
        if (c == '*') { return 1; }
        return 2;                            // jedes andere Zeichen
    }

    public boolean akzeptiert(String text) {
        zustand = 0;
        for (int i = 0; i < text.length(); i++) {
            zustand = delta[zustand][spalte(text.charAt(i))];
            if (zustand == 5) { return false; }   // zF: kein Weg zurück
        }
        return zustand == 4;
    }
}

/*x*/ führt nach z4, das angehängte x nach zF → zustand = 5 (2 P). Zutreffend: Zurücksetzen, früher Abbruch in zF, Tabellenschritt. Falsch: Unterwegs wird nicht entschieden; die Zeile für z4 wird gebraucht, weil nach dem Kommentarende weitere Zeichen folgen können (3 P).

Erwartungshorizont:

Bei beliebiger Tiefe müssten die Vorgeschichten /*, /*/*, /*/*/*, … alle unterschieden werden, denn jede braucht eine andere Anzahl */. Ein DEA mit \(k\) Zuständen kann das nicht (Schubfachprinzip). Nur mit einer festen Höchsttiefe wäre ein DEA möglich (3 P).

Erwartungshorizont:

Ausgabewort: Bon 50 ct, Bon 1 € → 2 Bons (1 P), zusammen 150 ct (2 P). Das letzte B in s0 gibt \(\varepsilon\) aus.

Erwartungshorizont:

\(\Omega=\{\text{Bon 25 ct},\ \text{Bon 50 ct},\ \text{Bon 75 ct},\ \text{Bon 1 €}\}\), also 4 Elemente (2 P). \(\varepsilon\) ist kein Element von \(\Omega\).

Erwartungshorizont:

Die vierte Flasche löst den Bon über 1 € aus und setzt auf s0 zurück; die fünfte Flasche beginnt neu, B druckt dann 25 ct (4 P, anteilig).

Erwartungshorizont:

Zutreffend: keine Endzustände (es zählt die Ausgabe), Vollständigkeit wie beim DEA (\(4\cdot 2=8\) Pfeile), Ausgabe abhängig von Zustand und Eingabe. Falsch: \(\varepsilon\) ist das leere Wort, kein Zeichen aus \(\Omega\); das Ergebnis ist das Ausgabewort, nicht der letzte Zustand (4 P, anteilig).

Erwartungshorizont:

Pro: Für jede feste Obergrenze gibt es einen Automaten. Contra: Bei beliebig vielen Flaschen müssten die Vorgeschichten F, FF, FFF, … alle unterschieden werden, da B jeweils einen anderen Bon ausgibt. Mit endlich vielen Zuständen landen zwei davon im selben Zustand und erhielten denselben Bon — Widerspruch. Ohne Obergrenze ist das also nicht möglich (3 P).

Mit Obergrenze 20: Zustände s0 bis s19 für 0 bis 19 Flaschen; die 20. Flasche führt mit „Bon 5 €“ nach s0 → 20 Zustände (2 P).