MINT lernen

Abituraufgaben: Kellerentwurf

Ein Additionsprüfer mit Strichen und ein Training, bei dem der Automat raten muss, was noch kommt.

Dein Fortschritt:
0 / 0 Aufgaben
1

Der Additionsprüfer

13 BEAFB I–II

Ein Lernprogramm für die Grundschule stellt Additionen mit Strichen dar: 11+1=111 steht für 2 + 1 = 3. Ein Kellerautomat soll prüfen, ob eine eingegebene Gleichung stimmt. Das Eingabealphabet ist \(\Sigma=\{1,\,+,\,=\}\); die Sprache ist

\(L=\{1^n+1^m=1^{n+m}\mid n,\,m\ge 1\}\).

  1. Nennen Sie zu jedem der Wörter 1+1=11, 11+1=11, +1=1 und 1+11=111, ob es zu \(L\) gehört. (2 BE)
  2. Beschreiben Sie einen Kellerplan für \(L\): Was wird in welcher Phase abgelegt oder entfernt? (3 BE)
  3. Zeichnen Sie einen Kellerautomaten, der \(L\) erkennt. Geben Sie das Kelleralphabet an. (5 BE)
  4. Stellen Sie den Lauf Ihres Automaten für 1+1=11 als Folge von Konfigurationen dar. (3 BE)

Hinweise

Hinweis zu Aufgabe a)
Zählen Sie die Striche links und rechts vom Gleichheitszeichen. Beachten Sie \(n,m\ge 1\).
Hinweis zu Aufgabe b)
Die Striche vor dem = müssen gezählt werden, die nach dem = mit dieser Anzahl verglichen werden. Was tun + und = mit dem Keller?
Hinweis zu Aufgabe c)
Ein Zustand je Phase: erste Zahl, zweite Zahl (mindestens ein Strich!), Ergebnis, fertig. Denken Sie an (#,ε):#.
Hinweis zu Aufgabe d)
Beginnen Sie mit (z0, 1+1=11, #) und notieren Sie den Keller mit dem obersten Zeichen links.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
  • 1+1=11: gehört zu \(L\) (1 + 1 = 2).
  • 11+1=11: nicht (2 + 1 ≠ 2).
  • +1=1: nicht, die erste Zahl fehlt (\(n\ge 1\)).
  • 1+11=111: gehört zu \(L\) (1 + 2 = 3).
Erwartungshorizont zu Aufgabe b)

Γ = {E, #}. Phase 1 (erste Zahl): jeder Strich legt ein E ab. Das + ändert den Keller nicht. Phase 2 (zweite Zahl): jeder Strich legt ein weiteres E ab — danach liegen \(n+m\) E im Keller. Das = ändert den Keller nicht. Phase 3 (Ergebnis): jeder Strich entfernt ein E. Liegt am Ende # oben, stimmt die Gleichung.

Erwartungshorizont zu Aufgabe c)
Lösung: Additionsprüfer (Σ = {1, +, =}, Γ = {E, #})
z0z1z2z3z4z5(#,1):E#(E,1):EE(E,+):E(E,1):EE(E,1):EE(E,=):E(E,1):ε(#,ε):#

z2 erzwingt mindestens einen Strich der zweiten Zahl, z0 → z1 mindestens einen der ersten. Fehlende Übergänge (z. B. = in z1 oder ein Strich zu viel mit # oben in z4) lassen den Automaten stecken bleiben.

Erwartungshorizont zu Aufgabe d)

(z0, 1+1=11, #) → (z1, +1=11, E#) → (z2, 1=11, E#) → (z3, =11, EE#) → (z4, 11, EE#) → (z4, 1, E#) → (z4, ε, #) → (z5, ε, #): akzeptiert.

2

Einfach oder doppelt

17 BEAFB II–III

Im Sportunterricht wird ein Zirkeltraining protokolliert: a steht für einen Liegestütz, b für eine Kniebeuge. Erst werden alle Liegestütze gemacht, dann die Kniebeugen. Ein Protokoll ist gültig, wenn genauso viele oder doppelt so viele Kniebeugen wie Liegestütze gemacht wurden:

\(L=\{a^nb^n\mid n\ge 0\}\cup\{a^nb^{2n}\mid n\ge 0\}\).

  1. Erläutern Sie, warum ein Kellerautomat für \(L\) schon beim ersten a eine Entscheidung treffen muss, die er erst später überprüfen kann. (3 BE)
  2. Entwerfen Sie einen nichtdeterministischen Kellerautomaten (NKA) für \(L\). (6 BE)
  3. Weisen Sie mit einer Konfigurationsfolge nach, dass Ihr Automat abb akzeptiert, und begründen Sie, warum er aabbb in keinem Lauf akzeptiert. (4 BE)
  4. Tom meint: „Wie ein nichtdeterministischer endlicher Automat lässt sich auch jeder NKA in einen deterministischen Kellerautomaten umbauen.“ Erörtern Sie diese Aussage am Beispiel von \(L\). (4 BE)

Hinweise

Hinweis zu Aufgabe a)
Wie viele Zeichen soll der Automat je a ablegen — eines oder zwei? Wann erfährt er, welcher Fall vorliegt?
Hinweis zu Aufgabe b)
Raten Sie gleich zu Beginn mit zwei ε-Übergängen, welcher Teil von \(L\) vorliegt, und bauen Sie für jeden Teil einen eigenen Zweig.
Hinweis zu Aufgabe c)
Für die Ablehnung müssen Sie alle Läufe betrachten — also beide Zweige.
Hinweis zu Aufgabe d)
Beim endlichen Automaten gibt es die Potenzmengenkonstruktion. Überlegen Sie, ob ein deterministischer Automat bei aabb nach dem vierten Zeichen schon „fertig“ sein darf.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Beim Lesen der a muss der Automat im Keller festhalten, wie viele b folgen dürfen: je a ein Zeichen (Fall \(b^n\)) oder zwei Zeichen (Fall \(b^{2n}\)). Welcher Fall vorliegt, zeigt sich aber erst am Ende der b. Da abgelegte Zeichen später nicht nachträglich verdoppelt werden können, muss er sich beim Ablegen festlegen — ein NKA rät diese Entscheidung und prüft sie am Ende.

Erwartungshorizont zu Aufgabe b)
Lösung: NKA für L (Γ = {A, #})
z0z1z2z3z4z5(#,ε):#(#,ε):#(#,a):A#(A,a):AA(A,b):ε(A,b):ε(#,ε):#(#,a):AA#(A,a):AAA(A,b):ε(A,b):ε(#,ε):#

Oberer Zweig: ein A je a, ein A weg je b (\(a^nb^n\)). Unterer Zweig: zwei A je a, ein A weg je b (\(a^nb^{2n}\)). z0 ist Endzustand für \(n=0\). Nichtdeterministisch sind die beiden ε-Übergänge aus z0 mit # oben.

Erwartungshorizont zu Aufgabe c)

abb über den unteren Zweig: (z0, abb, #) → (z3, abb, #) → (z3, bb, AA#) → (z4, b, A#) → (z4, ε, #) → (z5, ε, #): akzeptiert.

aabbb: Oberer Zweig: nach aa liegen 2 A, nach zwei b liegt # oben, das dritte b findet keinen Übergang — stecken. Unterer Zweig: nach aa liegen 4 A, nach drei b liegt noch ein A oben; das Wort ist gelesen, z4 ist kein Endzustand und (#,ε) passt nicht. Ein Lauf, der in z0 bleibt, liest kein Zeichen. Kein Lauf akzeptiert.

Erwartungshorizont zu Aufgabe d)

Pro: Für endliche Automaten stimmt die Aussage — jeder NEA lässt sich in einen DEA umwandeln. Für manche Sprachen gibt es auch deterministische Kellerautomaten, z. B. für \(\{w\,c\,w^R\}\).

Contra: Bei \(L\) müsste ein deterministischer Automat bei aabb nach dem vierten Zeichen akzeptieren und den Keller dabei so behandeln, dass er bei aabbbb noch zwei weitere b zählen kann. Die Information „wie viele a“ wird beim Vergleich aber verbraucht. Für \(L\) ist bewiesen, dass kein deterministischer Kellerautomat existiert (Beweis nicht gefordert).

Fazit: Toms Aussage ist falsch. Anders als bei endlichen Automaten ist Nichtdeterminismus bei Kellerautomaten echt mächtiger.