Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Zehn Aufgaben vom Wiedererkennen der Notation (AFB I) bis zur Beurteilung von Schülerlösungen (AFB III).
A1
Notation erkennen
AFB IOrdne jeder Schreibweise aus der Anlage ihre Bedeutung zu.
Klicke links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Beim Kellerautomaten steht in der Klammer zuerst das oberste Kellerzeichen, dann das Eingabezeichen; hinter dem Doppelpunkt das, was abgelegt wird. Beim Mealy-Automaten ist die Reihenfolge Eingabe / Ausgabe.
Ansatz: Welche Schreibweise hat einen Schrägstrich, welche eine Klammer?
Weiter: ε bedeutet je nach Stelle: nichts ausgeben oder nichts ablegen.
A2
Was die Anlage festlegt
AFB IWende die Regeln der Anlage an und entscheide, ob die Aussagen stimmen.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Diese fünf Punkte stehen fast wörtlich in der Anlage — wer sie sicher kennt, verliert bei der Notation keine Punkte.
Ansatz: Denk an die Reihenfolge beim Ablegen mehrerer Zeichen.
Weiter: Wann wird beim Kellerautomaten akzeptiert — und wann beim DEA?
A3
Konfigurationsfolge
AFB IDer Kellerautomat erkennt \(\{a^nb^n\mid n\ge 1\}\):
| von | Übergang | nach |
|---|---|---|
| S0 | (#,a):A# | S1 |
| S1 | (A,a):AA | S1 |
| S1 | (A,b):ε | S2 |
| S2 | (A,b):ε | S2 |
| S2 | (#,ε):# | S3 (Endzustand) |
Bestimme Zustand und Keller (oberstes Zeichen links) nach jedem Zeichen von aabb. Nach dem letzten Zeichen gilt der Zustand nach einem möglichen ε-Übergang.
Fülle alle Felder aus (Zustände als S0 … S3, Keller wie A#) und prüfe dann.
| gelesen | Zustand | Keller |
|---|---|---|
a | ||
aa | ||
aab | ||
aabb |
Nach dem zweiten b liegt # oben; der ε-Übergang (#,ε):# führt in den Endzustand S3 — das Wort ist gelesen, also akzeptiert.
Ansatz: Jedes a legt ein A ab, jedes b entfernt eines.
Weiter: Achte nach dem letzten b auf den ε-Übergang.
A4
Ableitung mit der Anlagen-Grammatik
AFB IIMit der Grammatik aus der Anlage
N = {A, B, S}
T = {1, 2, a, c}
Startsymbol: S
Produktionsregeln:
S → 1A | 2B
A → 1B
B → aS | cS | a | c
T = {1, 2, a, c}
Startsymbol: S
Produktionsregeln:
S → 1A | 2B
A → 1B
B → aS | cS | a | c
soll 11a2c erzeugt werden. Stelle die Ableitung dar, indem du die Satzformen ordnest.
Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1S
21A
311B
411aS
511a2B
611a2c
S ⇒ 1A ⇒ 11B ⇒ 11aS ⇒ 11a2B ⇒ 11a2c. Die Grammatik ist regulär: Jede Regel hängt ein Zeichen an und gibt an ein Nichtterminal weiter oder endet.
Ansatz: In jeder Satzform steht genau ein Nichtterminal ganz rechts.
Weiter: Nach 11 ist B dran: B → aS geht weiter, B → c beendet.
A5
Mealy-Lösung korrigieren
AFB IITom beschreibt in einer Klausur einen Mealy-Automaten, der nach jedem zweiten a ein X ausgibt. Überprüfe seine Notation.
In dieser Lösung stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen müssen stehen bleiben.
Ein Mealy-Automat wird mit Σ, Ω und einem vollständigen Übergangsgraphen angegeben; jeder Pfeil trägt Eingabe / Ausgabe. Doppelte Ränder gehören zu DEA und Kellerautomaten.
Ansatz: Vergleiche jede Zeile mit der Anlage.
Weiter: Zwei Zeilen sind falsch: eine Reihenfolge und ein Doppelrand.
A6
Welches Modell?
AFB IIOrdne jedes Notationselement dem Modell zu, zu dem es gehört.
Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).
1DEA
2Mealy-Automat
3Kellerautomat
4Grammatik
Jedes Modell hat eigene Alphabete: Σ haben alle Automaten, Ω nur der Mealy-Automat, Γ und # nur der Kellerautomat; Grammatiken verwenden N, T, Startsymbol und Produktionsregeln.
Ansatz: Achte auf die Alphabete: Σ, Ω, Γ, N, T.
Weiter: Der Schrägstrich gehört zum Mealy-Automaten, die Klammer (X,e) zum Kellerautomaten.
A7
Keller und Stack
AFB II MixDer Keller arbeitet wie ein Stapel mit den Operationen push, pop und top aus den Ergänzenden Hinweisen. Vergleiche beide Beschreibungen: Welche Aussagen stimmen?
Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Auswahl prüfen“.
Bei (X,e):W wird X mit pop() entfernt und W von rechts nach links mit push abgelegt: (#,a):A# heißt pop(), push(#), push(A). Ein DEA kommt mit einer Zustandsvariablen aus.
Ansatz: Welches Zeichen von W liegt am Ende oben?
Weiter: Das rechte Zeichen wird zuerst abgelegt.
A8
Kurze Wörter der Anlage
AFB III TrickErmittle, wie viele Wörter der Länge 3 die Grammatik aus der Anlage (siehe A4) erzeugt.
Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.
Mit 1 beginnt der Weg S → 1A → 11B, danach beendet B → a oder B → c:
11a, 11c. Mit 2 entsteht 2B; B → a oder B → c liefert nur Länge 2, und B → aS verlängert um mindestens 3 Zeichen. Also 2 Wörter — wer die Wege über 2 mitzählt, landet bei 4.Ansatz: Schreibe die Wege von S aus auf: 1A … und 2B ….
Weiter: Wie lang ist das kürzeste Wort, das aus S entsteht?
A9
Kellerautomat für aⁿcbⁿ
AFB IIIEntwirf einen deterministischen Kellerautomaten für \(\{a^ncb^n\mid n\ge 1\}\) mit S0 (Start), S1 (a-Phase), S2 (b-Phase) und dem Endzustand S3. Halte deinen Entwurf in Zahlen fest.
Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
- Anzahl verschiedener Kellersymbole außer #, die du mindestens brauchst: Symbole
-
Kellerinhalt (Anzahl Zeichen mit #) nach
aaac: Zeichen -
Kellerinhalt (Anzahl Zeichen mit #) nach
aaacb: Zeichen -
Anzahl aller Übergänge einschließlich ε beim Wort
aacbb: Übergänge
Ein Entwurf: S0 –(#,a):A#→ S1, (A,a):AA an S1, S1 –(A,c):A→ S2, (A,b):ε an S2, S2 –(#,ε):#→ S3. Das c ändert den Keller nicht, es wechselt nur die Phase. Bei
aacbb: a, a, c, b, b und am Ende der ε-Übergang = 6.Ansatz: Jedes a legt ein A ab, jedes b entfernt eines — das c markiert nur die Mitte.
Weiter: Vergiss den ε-Übergang in den Endzustand nicht.
A10
Lösungen beurteilen
AFB IIIBeurteile die Schülerlösungen nach der Anlage.
Wähle für jede Zeile eine Stufe: 1 = korrekt, 2 = formal unvollständig, 3 = fachlich falsch. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.
1 = korrekt3 = fachlich falsch
DEA ohne Fehlerzustand, mit dem Satz „Fehlende Übergänge führen nach zF“
DEA ohne Fehlerzustand und ohne Hinweis
Kellerübergang als (a,A):AA notiert
S → aSb | ε als reguläre Grammatik für aⁿbⁿ angegeben
Mealy-Übergang a / ε für „keine Ausgabe“
Kellerautomat akzeptiert, sobald # oben liegt, auch wenn noch Eingabe übrig ist
Fehlender Vermerk und vertauschte Reihenfolge sind Notationsfehler — der Gedanke stimmt, es gibt Abzüge. S → aSb ist nicht regulär, und Akzeptieren vor dem Ende der Eingabe widerspricht der Anlage: fachlich falsch.
Ansatz: Frage dich: Stimmt die Idee, aber nicht die Schreibweise — oder stimmt schon die Idee nicht?
Weiter: Die Anlage ist der Maßstab.