MINT lernen

Abituraufgaben: Kellerautomat

Ein Automat mit Mittelzeichen und ein Stumpfgleis am Prellbock — beides arbeitet nach „last in, first out“.

Dein Fortschritt:
0 / 0 Aufgaben
1

Ein Automat mit Mittelzeichen

13 BEAFB I–II

Gegeben ist der Kellerautomat P mit dem Eingabealphabet \(\Sigma=\{a,\,b,\,c\}\) und dem Kelleralphabet \(\Gamma=\{\texttt{A},\,\#\}\).

Kellerautomat P
z0z1z2(#,a):A#(A,a):AA(#,c):#(A,c):A(A,b):ε(#,ε):#
  1. Stellen Sie den Lauf von P für das Wort aacbb als Folge von Konfigurationen (Zustand, Resteingabe, Kellerinhalt) dar. (3 BE)
  2. Überprüfen Sie, welche der Wörter c, aacb, cb von P akzeptiert werden. (3 BE)
  3. Beschreiben Sie die von P erkannte Sprache in Mengenschreibweise und in Worten. (3 BE)
  4. Erläutern Sie, welche Aufgabe der Keller in P übernimmt und warum kein DEA diese Sprache erkennen kann. (4 BE)

Hinweise

Hinweis zu Aufgabe a)
Beginnen Sie mit (z0, aacbb, #). Suchen Sie in jedem Schritt den Übergang zum obersten Kellerzeichen und zum nächsten Zeichen; notieren Sie den Keller mit dem obersten Zeichen links.
Hinweis zu Aufgabe b)
Akzeptiert ist ein Wort nur, wenn es vollständig gelesen ist und P dann in z2 steht. Achten Sie darauf, was oben liegt, wenn das nächste b kommt.
Hinweis zu Aufgabe c)
Was passiert vor dem c, was danach? Wie hängen die Anzahlen der a und der b zusammen?
Hinweis zu Aufgabe d)
Wofür steht jedes A im Keller? Übertragen Sie die Schubfach-Idee aus 9.2.2 auf die Vorgeschichten \(a^0, a^1, \dots, a^k\).

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

(z0, aacbb, #) → (z0, acbb, A#) → (z0, cbb, AA#) → (z1, bb, AA#) → (z1, b, A#) → (z1, ε, #) → (z2, ε, #)

Benutzt: (#,a):A#, (A,a):AA, (A,c):A, zweimal (A,b):ε, (#,ε):#. Das Wort wird akzeptiert.

Erwartungshorizont zu Aufgabe b)
  • c: (z0, c, #) → (z1, ε, #) → (z2, ε, #) — akzeptiert.
  • aacb: … → (z1, ε, A#). Oben liegt A, es gibt keinen ε-Übergang mit A; z1 ist kein Endzustand — abgelehnt.
  • cb: (z0, cb, #) → (z1, b, #). Für (#,b) gibt es keinen Übergang; der ε-Übergang nach z2 hilft nicht, weil b ungelesen bleibt — abgelehnt.
Erwartungshorizont zu Aufgabe c)

\(L(P)=\{a^n\,c\,b^n\mid n\ge 0\}\)

In Worten: erst beliebig viele a, dann genau ein c, dann genau so viele b wie vorher a.

Erwartungshorizont zu Aufgabe d)

Der Keller zählt die a: Jedes a legt ein A ab, jedes b entfernt eines. Das c markiert den Wechsel der Phase und lässt den Keller unverändert. Liegt nach dem letzten b wieder # oben, stimmen die Anzahlen.

Ein DEA mit \(k\) Zuständen müsste die \(k+1\) Vorgeschichten \(a^0,\dots,a^k\) unterscheiden. Nach dem Schubfachprinzip enden zwei, \(a^i\) und \(a^j\) mit \(i<j\), im selben Zustand. Dann behandelt er \(a^icb^i\in L\) und \(a^jcb^i\notin L\) gleich — Widerspruch. Kein DEA erkennt \(L(P)\).

2

Das Stumpfgleis

17 BEAFB II–III

Auf einem Rangierbahnhof endet ein Gleis an einem Prellbock (Stumpfgleis). Waggons können nur von einer Seite ein- und ausfahren. Ein Stellwerk protokolliert jeden Vorgang: e steht für „ein Waggon fährt ein“, a für „der vorderste Waggon fährt aus“. Das Gleis ist anfangs leer.

Ein Protokoll über \(\Sigma=\{e,\,a\}\) heißt gültig, wenn nie aus dem leeren Gleis ausgefahren wird und das Gleis am Ende wieder leer ist.

Für die Implementierung steht die Klasse Stack mit den Operationen push, pop, top und isEmpty nach den Ergänzenden Hinweisen zur Verfügung; pop() gibt den entnommenen Inhalt zurück.

  1. Begründen Sie, dass sich das Stumpfgleis wie ein Keller verhält. (2 BE)
  2. Zeichnen Sie einen Kellerautomaten, der genau die gültigen Protokolle akzeptiert. Geben Sie das Kelleralphabet an. (4 BE)
  3. Das Gleis fasst höchstens 3 Waggons. Beurteilen Sie, ob die gültigen Protokolle unter dieser Bedingung auch von einem DEA erkannt werden können, und geben Sie gegebenenfalls die Anzahl der Zustände an. (4 BE)
  4. Implementieren Sie eine Methode boolean gueltig(String protokoll), die Ihren Kellerautomaten aus b) mithilfe eines Stapels nachbildet. (7 BE)

Hinweise

Hinweis zu Aufgabe a)
Welcher Waggon fährt als Nächstes aus — der zuerst oder der zuletzt eingefahrene?
Hinweis zu Aufgabe b)
Ein Kellerzeichen W je Waggon auf dem Gleis. Ein Zustand zum Lesen genügt; der Endzustand wird über (#,ε):# erreicht.
Hinweis zu Aufgabe c)
Wie viele verschiedene Waggonzahlen sind möglich? Denken Sie an den Fehlerzustand.
Hinweis zu Aufgabe d)
Legen Sie zu Beginn '#' auf den Stapel. Entnehmen Sie in jedem Schritt das oberste Zeichen (wie beim Übergang) und legen Sie ab, was der Übergang ablegt. Fehlt ein Übergang, ist das Protokoll ungültig.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Ausfahren kann nur der Waggon, der dem offenen Ende am nächsten steht — das ist der zuletzt eingefahrene. Wie beim Keller gilt „last in, first out“: Einfahren entspricht push, Ausfahren pop.

Erwartungshorizont zu Aufgabe b)
Lösung: Kellerautomat für gültige Protokolle
z0z1(#,e):W#(W,e):WW(W,a):ε(#,ε):#

\(\Gamma=\{\texttt{W},\,\#\}\): Jedes W steht für einen Waggon auf dem Gleis. Ausfahren ist nur möglich, wenn W oben liegt; aus dem leeren Gleis (# oben) fehlt ein Übergang. Nur mit # oben gelangt der Automat nach z1 — das Gleis ist leer.

Erwartungshorizont zu Aufgabe c)

Ja. Mit höchstens 3 Waggons gibt es nur die Belegungen 0, 1, 2 und 3 — endlich viele. Ein DEA mit den Zuständen z0 … z3 („i Waggons“, z0 Start- und einziger Endzustand) und einem Fehlerzustand zF genügt: e führt von zi nach z(i+1), a von zi nach z(i−1); e in z3 und a in z0 führen nach zF. Das sind 5 Zustände.

Ohne Obergrenze wäre das nicht möglich (unbeschränktes Zählen, 9.2.2) — erst dann braucht man den Keller.

Erwartungshorizont zu Aufgabe d)
Java · Methode gueltig
public static boolean gueltig(String protokoll) {
    Stack<Character> keller = new Stack<Character>();
    keller.push('#');                        // Vorbelegung
    for (int i = 0; i < protokoll.length(); i++) {
        char c = protokoll.charAt(i);
        char oben = keller.pop();             // oberstes Zeichen entfernen
        if (c == 'e') {                      // (#,e):W#  bzw.  (W,e):WW
            keller.push(oben);
            keller.push('W');
        } else if (c == 'a' && oben == 'W') {
            // (W,a):ε  — nichts ablegen
        } else {
            return false;                   // kein passender Übergang
        }
    }
    return keller.top() == '#';           // (#,ε):# in den Endzustand
}

Jeder Schleifendurchlauf entspricht einem Übergang: pop entfernt das oberste Kellerzeichen, danach wird abgelegt, was rechts vom Doppelpunkt steht — bei e erst das alte Zeichen, dann W. Die Rückgabe prüft den Übergang (#,ε):#: Nur wenn # oben liegt, ist das Gleis leer. Beispiele: eeaa → true, eaa → false, ae → false, leeres Protokoll → true.