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.
Kellerautomat
Habe ne Frage zur A21
Ein Palindrom (über{a,b})ist ein Wort W,dessen Reverses W^R, d.h. W rückwärts gelesen , mit W identisch ist.
i)Geben Sie eine kontextfreie Grammatik an,die genau die Palindrome erzeugt
ii)Geben Sie auch einen Kellerautomaten an
i)
S->aSa|bSb|a|b|ε
ii)
da hackts jetzt etwas bei mir…hab zwar was aber mein Gefühl sagt mir das es falsch ist…
zε#->zε
za#->zA
zb#->zB
zaA->zε
zεA->zε
zεB->zε
zbB->zε
zaB->zAB
zbA->zBA
mein Problem ist hier das ich nicht hinbekomme das wenn ein a am Anfang steht auch eins am Ende sein muss…vielleicht hat ja wer ne Idee
Der Kellerautomat muß ja “raten”, wann er die Wortmitte erreicht. Das heißt, er muß in einen zweiten Zustand wechseln, wenn er glaubt, die Wortmitte überschritten zu haben.
Dein Automat kann also jederzeit zwischen “ich bin noch in der ersten Hälfte” und “ich bin schon in der zweiten Hälfte” hin und herspringen. Also wäre z.B.
abb bba ab ba
in Deiner Sprache, weil er “abb bba” und dann “ab ba” abarbeiten würde. Du mußt ihn zwingen, zum “Stapellöschen” in einen zweiten Zustand zu gehen, den er dann nicht mehr verlassen kann.
Du könntest jetzt sagen “Aber Kellerautomaten brauchen doch nur einen Zustand”, und da hättest Du recht, aber mit mehreren Zuständen geht’s halt einfacher.
hmm mach halt nen Kellerautomaten der sich das erste zeichen merkt im keller, das zeichen löscht und zum ende fährt vergleicht und dann wieder vor … bis nur noch lauter blanks da sin. d.h wenn der vergleich immer positiv ausgefallen is.
Du beschreibst ne TM. Kellerautomaten können nicht hin- und herfahren, sie können nur von links nach rechts gehen (bzw. nur von rechts nach links, wenn es ein hebräischer oder arabischer Kellerautomat ist).
lös den doch einfach nichtdeterministisch … du kannst also nach jedem schritt schon in der mitte sein und in der stapel lösch zustand springen.
du tust das ganze quasi brute forcen … denn nur eine möglichkeit, nämlich die richtige, (wenn es diese fuer die eingabe gibt) wird bei fertiger eingabe im endzustand mit leerem keller hocken/terminieren.
(ich glaub das das genau das ist was der kleine hans geschrieben hat, aber ich schreibs noch mal so hin wie ich das versteh.)
wenns jmd deterministisch hinkriegt bitte posten! ich krieg das irgendwie net gebacken 
btw. damit der kellerautomat terminiert musser im endzustand mit leerem keller sein oder? oder wie war das noch mal genau
Ich glaube, die Grammtik ist nicht ganz richtig: Mit der könnte man das Wort „a“ oder „b“ erzeugen, das hat dann aber kein Reverses.
Mein Vorschlag:
S-> aSa | bSb | ε
ja, nichtdeterministisch bitte. Wenn Du’s deterministisch nicht hinkriegst: wunderbar, geht nämlich gar nicht.
ww^R ist nämlich eine nichtdeterministisch-kontextfreie Sprache, zu der man keinen det. Kellerautomat bauen kann, hihi!
ob Kellerautomat einen akzeptierenden Endzustand braucht oder mit leerem Keller akzeptiert, ist wurscht, mußt Du nur vorher festlegen. Zumindest bei nichtdeterministischen ist das egal. Bin aber nicht 100% sicher. Mach wie’s Dir paßt.
wenn ich das richtig nachgelesen und verstanden habe dann akzeptiert der nichtdeterministische Automat mit leerem Keller oder Endzustand (is äqui.) und der det. Kellerauto. mit Endzustand.
Der Kellerautomat zu dieser Spache steht auch im Schöning Seite 70/71.
Und Schöning sagtt, daß dieser Automat nichtdeterministisch ist.
ok danke 
habs glaub ich hinbekommen
dann schaut der so aus:
z0,a,# → z0,A#
z0,b,# → z0,B#
z0,a,A → z1,# oder z0,AA
z0,a,B → z0,AB
z0,b,B → z1,# oder z0,BB
z0,b,A → z0,BA
Stimmt`s??
Oder muss man da noch was angeben??
Zustand z1 sollte schon noch ein paar Mal auf der linken Seite auftauchen.
Mein Vorschlag:
z0,a,X → z0, AX (lege X auf den Stack), X∈{A,B,#}
z0,b,X → z0, BX (lege X auf den Stack), X∈{A,B,#}
z0,ε,X → z1, X (rate Mitte, Stack nicht verändern)
z1,a,A → z1, ε
z1,b,B → z1, ε
z1,ε,# → z1, ε (ACCEPT)
Meine Frage: der Automat kann das “#”-Zeichen ja auch löschen, bevor das Wort zu Ende ist, beispielsweise w = abbaa, wenn es also ein Palindrom als Präfix hat. Wie ist das geregelt? Akzeptiert der Kellerautomat, wenn bei Wortende der Keller leer ist?
denk der akzeptirt dann nicht, und er löscht auch das # nicht weil in dem fall wärs ja z1,a,# und nicht z1,ε,#.