MINT lernen

Abituraufgaben: Umwandeln

Ein Prüfbaustein für Dreierzahlen und ein Roboter mit Fahrprogrammen — hin und zurück zwischen Graph und Regeln.

Dein Fortschritt:
0 / 0 Aufgaben
1

Durch 3 teilbar

13 BEAFB I–II

Ein Prüfbaustein liest Binärzahlen von links nach rechts und akzeptiert genau die, deren Wert durch 3 teilbar ist; führende Nullen sind erlaubt, das leere Wort gilt als 0. Der Zustand ri bedeutet „der bisher gelesene Wert hat bei Division durch 3 den Rest i“.

DEA „durch 3 teilbar“ über Σ = {0, 1}
r0 r1 r2 0 1 1 0 0 1
  1. Geben Sie die Zustandsfolgen für 110 und 111 an und entscheiden Sie jeweils, ob das Wort akzeptiert wird. (3 BE)
  2. Stellen Sie die zugehörige reguläre Grammatik in der Notation N, T, Startsymbol, Produktionsregeln auf. (4 BE)
  3. Stellen Sie die Ableitung von 1001 dar und ordnen Sie jedem Schritt den Zustand des DEA zu. (3 BE)
  4. Das leere Wort soll nicht mehr erzeugt werden, alle anderen Wörter der Sprache schon. Erläutern Sie, wie die Grammatik dafür geändert werden kann. (3 BE)

Hinweise

Hinweis zu Aufgabe a)
Folgen Sie ab r0 den Pfeilen; die Zustandsfolge hat ein Element mehr als das Wort Zeichen.
Hinweis zu Aufgabe b)
Ordnen Sie r0, r1, r2 die Nichtterminale S, A, B zu. Jeder Pfeil wird eine Regel, der Endzustand eine ε-Regel.
Hinweis zu Aufgabe c)
Das Nichtterminal am Ende jeder Satzform ist der aktuelle Zustand.
Hinweis zu Aufgabe d)
Einfach S → ε zu streichen, reicht nicht — dann fehlen auch 11 oder 0. Ein neues Startsymbol hilft.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

110: r0 → r1 → r0 → r0 — akzeptiert (Wert 6).

111: r0 → r1 → r0 → r1 — nicht akzeptiert (Wert 7, Rest 1).

Erwartungshorizont zu Aufgabe b)

N = {S, A, B} mit S = r0, A = r1, B = r2; T = {0, 1}; Startsymbol: S

S → 0S | 1A | ε
A → 0B | 1S
B → 0A | 1B

Erwartungshorizont zu Aufgabe c)

S ⇒ 1A ⇒ 10B ⇒ 100A ⇒ 1001S ⇒ 1001

Zustände: r0 (S) → r1 (A) → r2 (B) → r1 (A) → r0 (S); der letzte Schritt nutzt S → ε, weil r0 Endzustand ist. 1001 hat den Wert 9.

Erwartungshorizont zu Aufgabe d)

S → ε wird gebraucht, weil jedes durch 3 teilbare Wort über S endet. Man führt deshalb ein neues Startsymbol Z ein, das die Regeln von S ohne die ε-Regel übernimmt: Z → 0S | 1A. S, A und B bleiben unverändert. Aus Z entsteht kein leeres Wort, aber z. B. Z ⇒ 0S ⇒ 0 und Z ⇒ 1A ⇒ 11S ⇒ 11. (Im DEA: neuer Startzustand, der kein Endzustand ist.)

2

Fahrprogramme für einen Roboter

17 BEAFB II–III

Ein Lernroboter führt Programme aus den Befehlen v (vorwärts), l (links drehen), r (rechts drehen) und s (stopp) aus. Gültige Programme werden durch die Grammatik G beschrieben:

N = {S, A}
T = {v, l, r, s}
Startsymbol: S
Produktionsregeln:
S → vS | lA | rA | s
A → vS
  1. Zeichnen Sie den Zustandsgraphen eines DEA, der genau die von G erzeugten Programme akzeptiert. Nicht eingezeichnete Übergänge dürfen mit Vermerk in einen Fehlerzustand führen. (5 BE)
  2. Begründen Sie, warum Ihr Automat deterministisch ist und warum er einen Zustand braucht, der keinem Nichtterminal entspricht. (3 BE)
  3. Implementieren Sie in Java eine Methode boolean gueltig(String prog), die den DEA simuliert. (5 BE)
  4. Damit der Roboter auch zweimal hintereinander drehen kann, ergänzt ein Entwickler bei A die Regeln A → lA | lS. Beurteilen Sie diese Änderung im Hinblick auf die Umwandlung in einen DEA und geben Sie eine Grammatik ohne dieses Problem für dieselbe Sprache an. (4 BE)

Hinweise

Hinweis zu Aufgabe a)
S und A werden Zustände. Wohin führt die Regel S → s?
Hinweis zu Aufgabe b)
Schauen Sie für jedes Nichtterminal, wie viele Regeln mit demselben Terminal beginnen.
Hinweis zu Aufgabe c)
Eine Variable für den Zustand, eine Schleife über die Zeichen, ein switch über den Zustand. Ungültige Zeichen führen in den Fehlerzustand.
Hinweis zu Aufgabe d)
Nach „A liest l“ ist unklar, ob es mit A oder mit S weitergeht. Ein neues Nichtterminal kann beide Möglichkeiten zugleich darstellen.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
Lösung: DEA der Fahrprogramme
z0 z1 zE v l, r v s

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

z0 = S, z1 = A (nach einer Drehung muss v folgen), zE = neuer Endzustand für S → s.

Erwartungshorizont zu Aufgabe b)

Für jedes Nichtterminal beginnt höchstens eine Regel mit einem bestimmten Befehl (S: v, l, r, s; A: v) — also hat jeder Zustand für jedes Zeichen höchstens einen Pfeil; fehlende Pfeile führen nach zF. Die Regel S → s endet ohne Nichtterminal; nach dem Stopp ist das Programm fertig. Dafür braucht man einen eigenen Endzustand zE ohne ausgehende Pfeile.

Erwartungshorizont zu Aufgabe c)
Java
// Zustände: 0 = S, 1 = A, 2 = zE, 3 = zF
public static boolean gueltig(String prog) {
    int z = 0;
    for (int i = 0; i < prog.length(); i++) {
        char c = prog.charAt(i);
        switch (z) {
            case 0:
                if (c == 'v') z = 0;
                else if (c == 'l' || c == 'r') z = 1;
                else if (c == 's') z = 2;
                else z = 3;
                break;
            case 1:
                if (c == 'v') z = 0;
                else z = 3;
                break;
            default:
                z = 3;
        }
    }
    return z == 2;
}

Test: vvlvs → true, lrvs → false (nach l muss v folgen), vsv → false (nach dem Stopp darf nichts folgen).

Erwartungshorizont zu Aufgabe d)

Mit A → vS | lA | lS gibt es zwei Regeln mit l bei A. Der Zustand A hätte zwei Pfeile mit l (nach A und nach S) — das ist kein DEA mehr; die direkte Umwandlung scheitert.

Abhilfe: ein neues Nichtterminal X für „nach l in A: A oder S“. X übernimmt die Regeln von A und S: X → vS | lX | rA | s, und A → vS | lX. Zu jedem Nichtterminal und Befehl gibt es wieder höchstens eine Regel, die Sprache bleibt gleich.