Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Kellerautomaten
Mir ist nicht klar, was ich bei folgenden beiden Aufgabenstellungen zu tun habe:
1.)
Geben Sie formal einen nichtdeterministischen Kellerautomaten an, der die Sprache L={a^n b^n c^m} u {a^n b^m c^n}, n, m >= 1 akzeptiert.
Naja, ich kann angeben:
NPDA A = (Q, Sigma, Gamma, delta, q_0, Z_0, F), wobei:
Q = {q_0, q_quer, q_accept}
Gamma = {Z_0} u V u Sigma
q_0 = Startzustand
F = {q_accept}
Z_0 \in Gamma, Kellergrundsymbol
delta-Regeln […] (siehe Vorlesungsmitschrift)
Sigma = Eingabealphabet = {a,b,c} (?)
Aber abgesehen von Sigma würde ich doch dann bei jedem formal anzugebenden Kellerautomaten das Gleiche hinschreiben…? :huh:
Das kann es doch irgendwie nicht sein. Muss ich noch eine passende Grammatik dazu angeben?
Gegeben ist eine kontextfreie Grammatik G […]. Geben Sie einen nichtdeterministischen Kellerautomaten an, der die Sprache L(G) akzeptiert.
Noch mehr Verwirrung. Der Kellerautomat arbeitet doch einfach seine Eingabe nichtdeterministisch mit den Produktionsregeln ab, was muss ich da jetzt noch tun?
Wäre für ein Mini-Beispiel dankbar :-/
Habe das hier bei der 74 raus, allerdings von noch niemanden korrigiert / drübergeschaut. Vielleicht hilft es dir weiter?
NKA = (Q, Sigma, Gamma, delta, q0, #, F)
Q = {q0, q1, q2, q3, q4, qf}
F = {qf}
Sigma = {a, b, c, epsilon}
Gamma = {a, b, c, #, epsilon}
Delta (e = epsilon):
Zustand Eingabe Keller Funktionswert
q0 a # {(q0, a#)}
q0 a a {(q0, aa)}
q0 b a {(q1, e),(q3, a)}
q1 b a {(q1, e)}
q1 c # {(q2, #)}
q2 c # {(q2, #)}
q2 e # {(qf, #)}
q3 b a {(q3, a)}
q3 c a {(q4, e)}
q4 c a {(q4, e)}
q4 e # {(qf, #)}Würd mich aber gleichzeitig auch über Kommentare freuen, vor allem ob das zumindest im Ansatz in die richtige Richtung geht 
Edit: das Grundsymbol ist zu Begin immer auf dem Stack, right?
Ich dachte, ich habe immer nur die drei Zustände q_0, q_quer und q_accept?
Was bedeutet denn {(q0, aa)} als Funktionswert bei dir? Du gehst in den Zustand q_0 und was soll das aa?
Hab tbh gerade eben erst das Verfahren aus der Vorlesung angeschaut, und man kann anscheinend für eine gegebene Grammatik ohne groß Denken den passenden nicht det-Automaten hinschreiben.
Bei der 74 fehlt die Grammatik, vielleicht hätte man die auch angeben können und dann wieder das Verfahren aus der Vorlesung, vermutlich einfacher …
Das “aa” ist was auf den Keller geschrieben wird, also d(q0, a, #) = {(q0, a#)} heißt es war ganz oben ein # auf dem Keller, gelesen wurde ein a, und anschließend direkt hinter das # auf den Stack geschrieben werden, die obersten 2 Zeichen sind dann a#.
Was mich wieder zu der Frage bringt, ob als Einziges nicht einfach nur eine kontextfreie Grammatik verlangt ist, weil sonst jeder Kellerautomat formal angegeben (bis auf das Sigma) gleich aussieht?
Aus dem Satz werde ich nicht ganz schlau. 
Am Anfang befindet sich nur # im Keller. Danach dann a## oder a#?
Wenn man die deltas nicht ausschreiben muss, glaube schon ^^
d(q0, a, #) = (q0, a#): Der Stack sieht aktuell so aus (oben nach unten): #…, die Eingabe (links nach rechts) a…, danach hat der Stack ein Zeichen mehr: a#… und die Eingabe „eines weniger“: …
Noch eine Frage zum Thema Kellerautomaten.
In meiner Vorlesungsmitschrift steht:
Da die Definition nichts ueber den Inhalt des Stacks aussagt: Angenommen mein Stack ist „nicht leer“. Halte ich dann auch akzeptierend, wenn ich einen Zustand aus F erreicht habe und alle Zeichen von x gelesen wurden?
In der Tat wird für „Akzeptanz“ über den Inhalt des Kellers in der Definition, die wir benutzt haben, nichts ausgesagt. D.h. auf dem Keller darf hinterher noch immer etwas stehen.
Zusätzliche Information: Man kann NPDAs auch so definieren, daß sie keine Menge akzeptierender Endzustände haben und genau die Wörter akzeptieren, für die es eine Rechnung gibt, bei der der Keller zum Schluß leer ist. Man kann beweisen, daß diese beiden Varianten äquivalent sind.
MfG
Rolf Wanka
In dieser Aufgabe sollten Sie einen NPDA „programmieren“, also die δ-Tabelle angeben. Ganz konkret sollten Sie beim Programmieren erkennen, daß diese Sprache (so nennt man das dann) inherent mehrdeutig ist. Der NPDA muß bereits vorher raten, ob das Wort, das in der Eingabe „jetzt“ kommen wird, aus der vorderen oder der hinteren Menge stammt. Nach dieser Entscheidung muß er nachprüfen, ob er richtig geraten hat. Das kann man alles ohne Umweg über eine Grammatik machen.
Natürlich können Sie auch eine kontextfreie Grammatik angeben, die L erzeugt (und das auch beweisen :-D), und dann daraus mit der Konstruktion der Vorlesung einen NPDA bauen. Die Konstruktion führt für jede Grammatik zu einem anderen NPDA, deswegen verstehe ich Ihre Aussage
nicht so ganz. Er hat zwar immer nur drei Zustände, aber die δ-Tabelle hängt von den Produktionen der Grammatik ab.
MfG
Rolf Wanka
Mit
war vermutlich das gemeint, was wir für einen Kellerautomaten mit gegebener Grammatik hinschreiben. Nachdem die delta-Tabelle eine so kompakte Schreibweise hat, sieht es so auf als müsste man selber eigentlich nichts mehr anpassen außer dem Alphabet.
Ich bin mir aber immer noch nicht im klaren wie das jetzt genau abläuft. Wie bist du auf die Tabelle gekommen?
Und wie läuft die A75 a) ab?
Wen meinst du mit du? Wenn’s um meine Tabelle geht: vielleicht einfach mal für aabcc die Konfigurationen hinschreiben. Kurz: es werden die ersten beiden a’s auf den Stack geschoben und anschließend mittels Indeterminismus entweder für jedes b oder für jedes c ein a wieder runter genommen.
Ich weis ja nicht, aber es sieht iwi so aus, als würdest du immer wieder mal ein a vom Stack hohlen und dann 2 a-s wieder draufschreiben.
Wenn ich mich nicht irre ist das nicht möglich, man müsste in der Tabelle vom Stack ein epsilon lesen und anschließend nur ein a schreiben, oder?
(Ich meine jetzt q0 a a {q0, aa})
Edit: Und ach ja ich meine mich auch zu erinnern, dass das Grundsymbol nicht automatisch draufsteht, man müsste also so eine Regel in der Richtung q0, e,e → (q0, #) einbauen.
Wenn du mal das Beispiel zu Satz 3.33 anschaust (Konstruktion einer Delta-Tabelle aus einer kf. Grammatik):
Da wir direkt im Startzustand ein Z0 vom Stack lesen muss das Z0 bereits vor Start des NPDA auf dem Stack gelegen sein.
Eine weitere Regel fuer q0 gibt es an der Stelle nicht.
Des weiteren siehst du bereits schon an dieser Regel dass wir uns erlauben auch mehr als ein Zeichen auf einmal auf den Stack zu pushen.
Gleiches siehst du wenige Zeilen drunter erneut: Wir pushen dann fuer die „rechten Seiten“ der Produktionen die kompletten linken Seiten (mehr als ein Zeichen).
-chris
Ok, ich hab irgentwie nurnoch den satz 3.3 und nicht mehr das Beispiel, da muss mir wohl was verloren gegangen sein.
Ich hab mich nur an der Definition der NPDA orientiert und da steht was von
Delta = Q x (Sigma or epsilon) x (Gamma or epsilon) → Potenzmenge(Q x Gamma) (Wobei das so gekritzelt ist, dass des auch Gamma * sein könnte ;-))
Ich hab dort Gamma* stehen 