Dein Fortschritt:
0 / 0 Aufgaben
1
Der Additionsprüfer
13 BEAFB I–IIEin 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\}\).
- Nennen Sie zu jedem der Wörter
1+1=11,11+1=11,+1=1und1+11=111, ob es zu \(L\) gehört. (2 BE) - Beschreiben Sie einen Kellerplan für \(L\): Was wird in welcher Phase abgelegt oder entfernt? (3 BE)
- Zeichnen Sie einen Kellerautomaten, der \(L\) erkennt. Geben Sie das Kelleralphabet an. (5 BE)
- Stellen Sie den Lauf Ihres Automaten für
1+1=11als 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.