Dein Fortschritt:
0 / 0 Aufgaben
1
Ein Automat mit Mittelzeichen
13 BEAFB I–IIGegeben ist der Kellerautomat P mit dem Eingabealphabet \(\Sigma=\{a,\,b,\,c\}\) und dem Kelleralphabet \(\Gamma=\{\texttt{A},\,\#\}\).
Kellerautomat P
- Stellen Sie den Lauf von P für das Wort
aacbbals Folge von Konfigurationen (Zustand, Resteingabe, Kellerinhalt) dar. (3 BE) - Überprüfen Sie, welche der Wörter
c,aacb,cbvon P akzeptiert werden. (3 BE) - Beschreiben Sie die von P erkannte Sprache in Mengenschreibweise und in Worten. (3 BE)
- 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\).