Hilfsmittel: die Anlage mit der Notation (Automaten, Kellerautomaten, Grammatiken). Bearbeiten Sie alle drei Aufgaben; die Lösungen werden nach dem Auswerten freigeschaltet.
Paketcodes im Versandlager
20 PunkteEin Versandlager vergibt Paketcodes: ein Buchstabe für den Lagerbereich, mindestens zwei Ziffern und ein Buchstabe für das Regal, z. B. A07K. Zur Prüfung wird jeder Buchstabe durch b und jede Ziffer durch z ersetzt, \(\Sigma=\{b,\,z\}\).
Nicht eingezeichnete Übergänge führen in den Fehlerzustand zF.
Geben Sie alle Wörter an, die der Automat akzeptiert.
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
Akzeptiert: bzzb (z0 · z1 · z2 · z3 · z4) und bzzzzb (3 P). bzb: nur eine Ziffer; bzz endet in z3; zzb beginnt falsch; bzzbb: nach z4 führt b nach zF.
Berechnen Sie, wie viele Übergänge der Automat hat, wenn der Fehlerzustand vollständig eingezeichnet wird.
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
Zustände z0 bis z4 und zF: \(6\cdot 2=12\) Übergänge (2 P).
Ordnen Sie den Zuständen ihre Bedeutung zu.
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
z1: Bereich gelesen, noch keine Ziffer; z2: genau eine Ziffer; z3: mindestens zwei Ziffern, Regal fehlt; z4: vollständiger Code (je 1 P).
Die Zustände z0, …, z4 werden zu den Nichtterminalen S, A, B, C, D. Erstellen Sie die zugehörige reguläre Grammatik: Welche Regeln gehören dazu?
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
S → bA, A → zB, B → zC, C → zC | bD, D → ε (4 P). Nur z4 ist Endzustand, also gibt es nur D → ε; Pfeile nach zF werden nicht zu Regeln.
Bestimmen Sie für die Grammatik aus 1d die Anzahl der Regeln und die Zahl der Ableitungsschritte für bzzzb.
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
Sechs Regeln (2 P). S ⇒ bA ⇒ bzB ⇒ bzzC ⇒ bzzzC ⇒ bzzzbD ⇒ bzzzb: 6 Schritte (2 P).
Die Lagerleitung möchte zusätzlich verlangen, dass die Anzahl der Ziffern durch 3 teilbar ist. Beurteilen Sie, ob ein DEA das leisten kann.
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
Möglich: Rest 0, 1, 2 der Ziffernanzahl sind endlich viele Informationen; zusammen mit „mindestens zwei“ genügen wenige zusätzliche Zustände (3 P). Anders als bei \(\{a^nb^n\}\) muss keine unbeschränkte Anzahl mit einer zweiten verglichen werden.
Klammerprüfung im Editor
20 PunkteEin Editor prüft runde Klammern mit einem deterministischen Kellerautomaten: \(\Sigma=\{(,\,)\}\), \(\Gamma=\{K,\,\#\}\), Startzustand z0, zugleich Endzustand.
| von | Übergang | nach |
|---|---|---|
| z0 | (#,():K# | z1 |
| z1 | (K,():KK | z1 |
| z1 | (K,)):ε | z1 |
| z1 | (#,ε):# | z0 |
Wenden Sie den Automaten an: Welche Wörter werden akzeptiert?
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
Akzeptiert: (()), ()(), (()()) (3 P). )(: in z0 kein Übergang mit ); (() endet in z1 mit K#; ())(: nach () zurück in z0, dann ) ohne Übergang.
Ermitteln Sie den Kellerinhalt (oben links) nach den Anfangsstücken des Worts (()(.
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
K# · KK# · K# · KK# (je 1 P). Jede ( legt ein K ab, jede ) entfernt eines.
Nennen Sie die größte Anzahl von Zeichen im Keller (einschließlich #) beim Wort ((())(())) und die Anzahl aller Übergänge einschließlich ε-Übergängen beim Wort ()().
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
Tiefen 1, 2, 3, 2, 1, 2, 3, 2, 1, 0: höchstens drei K plus # = 4 (2 P). Bei ()(): (, ), ε, (, ), ε = 6 Übergänge (2 P) — nach jedem geschlossenen äußeren Paar führt (#,ε):# zurück nach z0.
Zusätzlich sollen eckige Klammern [ ] erlaubt sein, die korrekt mit den runden geschachtelt sein müssen, z. B. ([]), aber nicht ([)]. Erweitern Sie den Automaten: Welche Erweiterung ist korrekt?
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
Nur mit einem eigenen Kellersymbol weiß der Automat, welche Klammerart zuletzt geöffnet wurde (4 P). Mit nur K würde ([)] akzeptiert; zwei getrennte Zähler oder Keller verlieren die Reihenfolge.
Die Klammersprache wird von S → (S)S | ε erzeugt. Bestimmen Sie die Zahl der Ableitungsschritte für (()) und begründen Sie, warum kein DEA die Sprache erkennt.
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
S ⇒ (S)S ⇒ ((S)S)S ⇒ (()S)S ⇒ (())S ⇒ (()): 5 Schritte (2 P). Begründung mit dem Schubfachprinzip (3 P); dass eine bestimmte Grammatik nicht regulär ist, beweist nichts über die Sprache.
Listen in einer Konfigurationsdatei
20 PunkteEine Konfigurationsdatei enthält Listen wie [w,[w,w],[]]; w steht für einen Wert. Die Syntax legt die Grammatik G fest:
T = {[, ], ,, w}
Startsymbol: L
Produktionsregeln:
L → [] | [R]
R → W | W,R
W → w | L
Geben Sie alle Wörter an, die zu L(G) gehören.
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
[w,[w]], [[]], [w,w,w] (3 P). [w,]: nach dem Komma fehlt ein Element; [w][w]: zwei Listen statt einer; w: keine Liste.
Stellen Sie die Linksableitung von [w,[]] dar und geben Sie die Zahl der Schritte sowie die Zahl der Ableitungsbäume für [w,w] an.
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
L ⇒ [R] ⇒ [W,R] ⇒ [w,R] ⇒ [w,W] ⇒ [w,L] ⇒ [w,[]]: 6 Schritte (2 P). Für [w,w] gibt es genau einen Baum (L → [R], R → W,R, R → W) (2 P) — die Grammatik ist hier eindeutig.
Ordnen Sie die Grammatiken ein (Startsymbol jeweils L bzw. S).
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
G: kontextfrei (Nichtterminal in der Mitte, [R]); S → aS | ε: regulär; aS → Sa: links zwei Symbole, nicht kontextfrei; S → SS | x: kontextfrei (je 1 P).
Ein Kollege meint: „Die Listen kann man auch mit einem DEA prüfen.“ Widerlegen Sie die Aussage.
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
Schubfach-Argument über die Verschachtelungstiefe (4 P). Viele Werte nebeneinander (w,w,w,…) kann ein DEA dagegen sehr wohl prüfen — das Problem ist nur die unbeschränkte Tiefe.
Die Datei soll Listen höchstens bis zur Tiefe 3 enthalten. Erörtern Sie, ob die Prüfung nun mit einem DEA möglich ist.
Lösung anzeigen (nach Auswerten freigeschaltet)
Erwartungshorizont:
Mit begrenzter Tiefe ist die Sprache regulär (3 P): Ein DEA speichert die aktuelle Tiefe. Nur für [ und ] genügen die Zustände für die Tiefen 0, 1, 2, 3 — 4 Zustände, dazu zF (2 P). Dass G kontextfrei ist, spricht nicht dagegen: Auch eine reguläre Sprache kann durch eine nicht reguläre Grammatik beschrieben sein.
Ergebnis
| Aufgabe | Thema | Punkte |
|---|
Punkteverteilung
| Teilaufgabe | Thema | Aufgabe | AFB | Punkte |
|---|---|---|---|---|
| 1a | Codes prüfen | Aufgabe 1 | AFB I | 3 |
| 1b | Vollständiger Automat | Aufgabe 1 | AFB I | 2 |
| 1c | Bedeutung der Zustände | Aufgabe 1 | AFB II | 4 |
| 1d | Regeln der Grammatik | Aufgabe 1 | AFB II | 4 |
| 1e | Regeln und Ableitung | Aufgabe 1 | AFB II | 4 |
| 1f | Durch drei teilbar | Aufgabe 1 | AFB III | 3 |
| 2a | Wörter prüfen | Aufgabe 2 | AFB I | 3 |
| 2b | Kellerinhalte | Aufgabe 2 | AFB II | 4 |
| 2c | Kellerhöhe und Schritte | Aufgabe 2 | AFB II | 4 |
| 2d | Eckige Klammern | Aufgabe 2 | AFB III | 4 |
| 2e | Grammatik und Grenze | Aufgabe 2 | AFB II | 5 |
| 3a | Gültige Listen | Aufgabe 3 | AFB I | 3 |
| 3b | Linksableitung | Aufgabe 3 | AFB II | 4 |
| 3c | Grammatiktypen | Aufgabe 3 | AFB II | 4 |
| 3d | Nicht regulär | Aufgabe 3 | AFB III | 4 |
| 3e | Begrenzte Tiefe | Aufgabe 3 | AFB III | 5 |
| Summe (AFB I: 11 P · AFB II: 33 P · AFB III: 16 P) | 60 | |||
Notenschema (Notenpunkte der Oberstufe)
| Punkte | Notenpunkte | Beurteilung |
|---|---|---|
| 57 – 60 P | 15 | sehr gut + |
| 54 – 56 P | 14 | sehr gut |
| 51 – 53 P | 13 | sehr gut − |
| 48 – 50 P | 12 | gut + |
| 45 – 47 P | 11 | gut |
| 42 – 44 P | 10 | gut − |
| 39 – 41 P | 9 | befriedigend + |
| 36 – 38 P | 8 | befriedigend |
| 33 – 35 P | 7 | befriedigend − |
| 30 – 32 P | 6 | ausreichend + |
| 27 – 29 P | 5 | ausreichend |
| 24 – 26 P | 4 | ausreichend − |
| 20 – 23 P | 3 | mangelhaft + |
| 16 – 19 P | 2 | mangelhaft |
| 12 – 15 P | 1 | mangelhaft − |
| 0 – 11 P | 0 | ungenügend |