Diskussion:Kellerautomat

Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine.

Quelle?

Erk/Priese, Theoretische Informatik, Springer Verlag, 3. Auflage, 2008, S. 337. Soll das im Artikel angegeben werden? -- UKoch 23:59, 27. Apr. 2011 (CEST)

Sollte vielleicht, muss aber aus meiner Sicht nicht. (Was ist so schwer daran, zu sehen, dass 2 Stacks ein Band ergeben, auf dem man sich nach links und rechts bewegen kann?) Viel besser wäre vielleicht ein Zipper-Artikel! :D --Daniel5Ko 00:14, 28. Apr. 2011 (CEST)

Ein Kellerautomat akzeptiert die Syntax der meisten Programmiersprachen.

"Ein Kellerautomat akzeptiert die Syntax der meisten Programmiersprachen." (Ich glaub der letzte Satz stimmt so nicht, Compilerbau ist aber auch bei mir schon wieder ne ganze Weile her... --Coma 13:24, 5. Feb 2003 (CET))

obiges habe ich von der Artikelseite zur Diskussion geschoben. --Walter Koch 22:47, 17. Feb 2003 (CET)

Die BNF lässt sich mittels eines Kellerautomaten erkennen und wird bei vielen Programmiersprachen zur Syntaxbeschreibung verwendet. Hierbei werden natürlich keine Inhaltlichen Fehler (Vergessene Variablendeklarationen, fehlerhafte Methodenaufrufe u.Ä) erkannt. --Horratio 19:57, 2. Feb 2006 (CET)

Kellerautomat als 7-Tupel?

(sorry ich hab keine Ahung wie man hier mathematische Zeichen macht ;) Einfach mal Hier nach schauen im letzten Kapitel geht es im Kellerautomaten. Vllt mach ich es auch nacher, aber erst muss ich den Mist Freitag bestehen ;) --Unterstrichmoepunterstrich 00:41, 5. Mär. 2009 (CET)

Geht es nicht auch etwas allgemeinverständlicher?

Vielleicht bin ich ja auch total bescheuert, aber ich versteh' hier einfach gar nichts mehr. Ist es nicht unklug, einen Artikel zu beginnen mit "X ist ein Produkt dieser Wissenschaft und besteht aus Y"? zum Vergleich: "Ein Auto ist ein Produkt des Maschinenbaus. Es besteht aus Metall, Plastik und Gummi." Also: Wer hat Lust, mir (und sicher auch anderen) zu erklären, was ein Kellerautomat leistet, welchem Zweck er dient?--213.167.161.211 08:44, 4. Nov 2004 (CET)

Hab' mal ein bischen was - ich hoffe Allgemeinverständlicheres - ergänzt. 217.246.68.147 12:03, 12. Dez 2004 (CET)

Leider passt das erste Bild nicht zum Beispieltext, ich weiß nicht warum da ausgerechnet B,A und C im Keller stehen. Aber ansonsten ist der praktische Teil schon recht hilfreich. Danke. Kolossos 13:01, 23. Feb. 2007 (CET)

Wenn der Artikel auch richtig sein mag (keine Ahnung), so ist er doch für mathematische Laien maximal unverständlich. Ich bin über die Erklärung von Google Android darauf gekommen, in der die Rede davon war, dass bei der Programmierung Kellerautomaten benutzt werden und wollte nur GROB wissen, was das bedeutet, aber deswegen nicht zum Experten für dieses Thema werden. So nützt mir die "Erklärung" nichts. Es fehlt im Anfang eine ganz simple Erklärung, was das Konzept ist, warum es Kellermaschine heißt und was die Ursache war, dass man dieses Konzept benutzt. (nicht signierter Beitrag von Ksmichel (Diskussion | Beiträge) 11:45, 24. Mär. 2010 (CET))

Wikipedia:TeX

Es wäre super, wenn jemand bei Gelegenheit die etwas pfuschigen Notationen in TeX-Notation umwandeln könnte. Stern !? 14:32, 3. Mär 2005 (CET)

Funktionsweise: Grundlegende Idee

Ich hab damit ein Problem:

1. Das gelesene Zeichen wird immer sofort verarbeitet. In den Keller schreiben ist auch eine Verarbeitung. Insofern merkwürdige Formulierung und entspricht wohl eher ein einzelnen Anwendungsfall.

2. Es muss nicht zwangsläufig das gelesene Zeichen in den Keller geschrieben werden. Das Eingabealphabet kann sich sogar vollständig vom Kelleralphabet unterscheiden. Das ist schon an der Übergangsfunktion erkennbar

$\delta :Q\times \Sigma \times \Gamma \rightarrow \Sigma \times \Gamma ^{*}$

Das ist nirgends erwähnt, dass $\Sigma$ und $\Gamma$ identisch sein müssen. Ebenso können (wegen $\Gamma ^{*}$) mehr als ein Zeichen, also auch mehr als gelesene Zeichen pro Schritt in den Keller geschoben werden.

3. Die Bearbeitung wird nicht nachgeholt, es wird nur darauf reagiert, was im Keller steht. Dies kann (Anwendungsfall) eben das Nachholen sein, muss es aber nicht zwangsläufig (siehe 1. und 2.)

Naja, wollte nur kurz los werden, dass ich mich daran etwas störe ^^ Vielleicht teilt da jemand meine Meinung. --KingCrunch 22:57, 17. Jun. 2007 (CEST)

Dem kann ich mich nur anschließen - auch informelle Beschreibungen sollten korrekt sein. Hast du Lust das zu korrigieren? --89.247.76.158 20:57, 19. Jun. 2007 (CEST)

Programmbeispiel

Aus dem Absatz geht nach meiner Ansicht nicht klar genug hervor, dass es sich um C handelt. Ich habe mir deshalb erlaubt, das zu ergänzen. --Merlin G. 17:24, 9. Sep. 2007 (CEST)

Warum wurde das Programmbeispiel kommentarlos gelöscht? Ich habe die Seite jetzt wiederhergestellt, da ich das Programmbeispiel gut fand. -- Merlin G. 11:31, 1. Dez. 2007 (CET)

Ist mit leerem Keller definitiv Schluss?

Ich habe jetzt mehrfach gehört, dass ein PDA mit leerem Keller die Eingabe akzeptiert und dann stillsteht. Ist das der Fall oder darf auch mit leerem Keller weitergelesen werden? Mir ist dieser Gedanke durchaus logisch, doch ich habe das bisher noch nicht in einer Definition von einem Kellerautomaten entdeckt. --92.226.149.5 17:18, 25. Mai 2008 (CEST)

Ja, wenn der Stack leer wird, hält der PDA auf jeden Fall, unabhängig vom Akzeptanzmodus. Allerdings wird dann im Akzeptanzmodus "akzeptierende Zustände" die Eingabe dann auf jeden Fall verworfen, während im Akzeptanzmodus "leerer Stack" die Eingabe genau dann akzeptiert wird, wenn bereits die komplette Eingabe gelesen wurde. Dass die Eingabe bei leerem Stack immer akzeptiert wird, ist also nicht richtig. --Denis 16:58, 10. Jul. 2008 (CEST)

Völliger Unsinn. Bei leerer Eingabe ist Schluss, der Keller kontrolliert nur die möglichen Übergänge. Andernfalls könnte man $\{a^{n}b^{n}a^{n}b^{n}|n\in \mathbb {N} \}$ gar nicht erkennen. Aber nach Lesen von $a^{n}b^{n}$ ist der Stack leer und der Automat kann und muss weiterarbeiten, wenn die Eingabe mehr Zeichen enthält. --Zahnradzacken 20:28, 27. Jul. 2011 (CEST)

Also so, wie's momentan im Artikel steht, ist ein nicht-leerer Stack unbedingt erforderlich für einen Zustandsübergang.

Das stört allerdings nicht, da ein effizienter Automat für $\{a^{n}b^{n}a^{m}b^{m}|n,m\in \mathbb {N} \}$ nach dem Lesen von $a^{n}b^{n}$ bei einem Stack angekommen wäre, der # enthält.

(Deine Beispielsprache ($\{a^{n}b^{n}a^{n}b^{n}|n\in \mathbb {N} \}$) bzw. der Automat dafür funktioniert nicht als Beispiel. Denn wenn tatsächlich nach dem Lesen der ersten as und bs der Keller leer wäre (oder nur noch # enthielte), wäre jegliche Information über das gefundene $n$ verschwunden.)

--Daniel5Ko 21:09, 27. Jul. 2011 (CEST)

Als ich mit den Worten "völliger Unsinn" begann, ahnte ich schon, dass ich bestimmt falsch liege :D Dein Beispiel ist natürlich sinnvoll, im Gegensatz zu meinem. Der Artikel gibt aber kaum etwas her ohne die Definition von Konfiguration und Berechnung. Ich vermute (völlig spekulativ), dass man einen ganz leeren Stack nicht braucht (oben habe ich Stack = leer mit Stack = # verwechselt). Eine vielleicht unglückliche Definition, mutmaße ich. Ein wahre Freude, wenn man eine Hand voll unterschiedlicher Definitionen nur grob in Erinnerung hat. --Zahnradzacken 01:31, 28. Jul. 2011 (CEST)

Naja, man hat schon etwas mehr Ausdrucksmöglichkeiten, wenn man zwischen leerem Stack und Stack mit lediglich # unterscheidet. Zum Beispiel kann der Automat das # konsumieren und einen leeren Stack hinterlassen, und die Bedeutung davon ist: Wenn jetzt noch ein weiteres Eingabesymbol kommt, akzeptiere ich nicht. Diese Bedeutung ergibt sich ganz natürlich, wenn man alle möglichen Läufe parallel simuliert. Eine "Hyper-"Konfiguration $K$ wäre dann

$K\in {\mathcal {P}}(Z\times \Gamma ^{*}\times \Sigma ^{*})$

und der Hyperkonfigurations-Übergang wäre

$f\colon {\mathcal {P}}(Z\times \Gamma ^{*}\times \Sigma ^{*})\to {\mathcal {P}}(Z\times \Gamma ^{*}\times \Sigma ^{*}),$

${\begin{aligned}K\ \mapsto &\{(z',\gamma '\gamma ,\alpha )|(z,g\gamma ,a\alpha )\in K,(z',\gamma ')\in \delta (z,a,g)\}\\\cup &\{(z',\gamma '\gamma ,\alpha )|(z,g\gamma ,\alpha )\in K,(z',\gamma ')\in \delta (z,\varepsilon ,g)\}.\end{aligned}}$

(die Elemente von $K$ mit leerem Stack flögen raus, da ihre Stacks nicht aufs Muster $g\gamma$ passen.)

Ach ja: Ein Wort $\omega$ wird in dieser Formulierung akzeptiert, wenn es ein $n\in \mathbb {N}$, ein $z_{F}\in F$ und ein $\gamma \in \Gamma ^{*}$ gibt, sodass $(z_{F},\gamma ,\varepsilon )\in f^{n}(\{(z_{0},\#,\omega )\})$. --Daniel5Ko 12:04, 28. Jul. 2011 (CEST)

Vermischst du hier nicht Akzeptanz durch leeren Stack und Akzeptanz durch Endzustand? Letzteres könnte man doch auch ohne völlig leeren Stack erreichen, wenn für jedes $z\in Z$ und jedes $a\in \Sigma$ ein zusätzlicher Übergang

$(z_{\neg F},\#)\in \delta (z,a,\#)$ mit $z_{\neg F}\notin F$ eingeführt wird und natürlich sonst aus $z_{f}$ kein Übergang herausführt. Bei Akzeptanz durch leeren Stack sehe ich schon eher einen Zweck des leeren Stacks, nämlich Akzeptanz gdw $(z,\varepsilon ,\varepsilon )\in f^{n}(\{(z_{0},\#,\omega )\})$, wenn aber die Konfiguration auch das restliche zu verarbeitende Wort enthält, sehe ich momentan nicht den Vorteil gegenüber $(z,\#,\varepsilon )\in f^{n}(\{(z_{0},\#,\omega )\})$ als Bedingung fürs Akzeptieren. --Zahnradzacken 13:04, 28. Jul. 2011 (CEST)

Ich vermische nicht Akzeptanz durch leeren Stack und Akzeptanz durch Endzustand. Ich gab nur eine Definition für letzteres an.

Vermischen war vielleicht das falsche Wort. Jedenfalls sehe ich bei Akzeptanz durch Endzustand keinen Mehrwert darin, den leeren Stack zu betrachten. Vielleicht habe ich auch deine Wortwahl "mehr Ausdrucksmöglichkeiten" falsch verstanden. Ich dachte du meinst, man kann damit eine größere Sprachklasse beschreiben – in welchem Fall ich noch nicht überzeugt wurde. --Zahnradzacken 16:41, 28. Jul. 2011 (CEST)

Oh, 'tschuldigung. Ich meinte tatsächlich lediglich "bequemeres" Programmieren. :) --Daniel5Ko 18:22, 28. Jul. 2011 (CEST)

Dass ein leerer Stack entstehen kann, man für eine Anwendung von $\delta$ aber einen nicht-leeren benötigt, ergibt sich aus $\delta \colon Z\times (\Sigma \cup \{\varepsilon \})\times \Gamma \rightarrow {\mathcal {P}}(Z\times \Gamma ^{*})$.

Ja, daran habe ich nicht gezweifelt; nur daran, dass man davon etwas hat. --Zahnradzacken 16:41, 28. Jul. 2011 (CEST)

Ich weiß jetzt auch nicht, wieviel das im einzelnen bringt. Die ollen Epsilon-Schritte zerstören jeglichen größeren Nutzen, der mir so in der Sinn kommt... --Daniel5Ko 18:22, 28. Jul. 2011 (CEST)

Über Akzeptanzverhalten im Zusammenhang mit dem leeren Stack sagte ich lediglich, dass ein Element $(z,\varepsilon ,\omega ')\in f^{k}(\{(z_{0},\#,\omega )\})$ nichts zu $f^{k+1}(\{(z_{0},\#,\omega )\})$ beitragen kann. Das heißt, dass auf diesem Pfad, falls $\omega '\neq \varepsilon$, $\omega$ jedenfalls nicht akzeptiert wird.

Habe ich verstanden. Aber sagst du damit nicht aus, dass der leere Stack keine Auswirkung auf den Umfang der Sprachklasse hat? Worin siehst du dann "mehr Ausdrucksmöglichkeiten", außer in Pfaden, die nicht weiter verfolgt werden können? --Zahnradzacken 16:41, 28. Jul. 2011 (CEST)

Siehe oben. --Daniel5Ko 18:22, 28. Jul. 2011 (CEST)

Ach ja, noch 'ne Bemerkung am Rande: Die Eingabe führe ich übrigens nur deswegen in den Konfigurationen mit, weil es Epsilon-Übergänge gibt. Ohne die könnte man aus $\delta$ auch direkt eine Funktion $\Sigma ^{*}\to {\mathcal {P}}(Z\times \Gamma ^{*})$ generieren, die für jedes Wort die Menge aller erreichbaren (nur aus Zustand und Stack bestehenden) Konfigurationen nach Konsumierung des Wortes berechnet. --Daniel5Ko 14:32, 28. Jul. 2011 (CEST)

Aber auch hier spielt die Konfiguration mit leerem Stack keine herausragende Rolle. --Zahnradzacken 16:41, 28. Jul. 2011 (CEST)

Es ist ja nicht so, dass wir den leeren Stack extra reingebaut haben. Er ist Teil von legalen Konfigurationen, welche über die Akzeptierung eines Wortes entscheiden können.

Der Stack kann nur dann nicht leer werden, wenn wir # sonderbehandeln: z.B. die Typen von $\delta$ und $f$ als

$\delta \colon Z\times \Sigma \times \Gamma \to {\mathcal {P}}(Z\times (\Gamma \setminus \{\#\})^{*})$ und

$f\colon {\mathcal {P}}(Z\times \Gamma ^{*}\times \Sigma ^{*})\to {\mathcal {P}}(Z\times \Gamma ^{*}\times \Sigma ^{*}),$

festlegen und f so anpassen, dass die # erhalten bleiben (genauer: es gibt immer nur eins, und das ist ganz unten. Als Element von $\Gamma$ ist es zudem trotzdem als Eingabe an $\delta$ geeignet.)

Dann hätte man auch nicht mehr das Problem, was "akzeptieren wenn leer" überhaupt bedeutet: Ist # ein leerer Stack? etc. Der echt leere Stack träte nicht mehr auf.

--Daniel5Ko 18:22, 28. Jul. 2011 (CEST)

Oder man verzichtet auf # und behandelt $\varepsilon$ als einzigen Sonderfall. Aus der Sicht kann man # als "extra reingebaut" bezeichnen. (Nebenbemerkung: Ich bezweifle, dass dein angepasstes delta sicherstellt, dass # erhalten bleibt, denn # matcht auf $\#\gamma$ mit $\gamma =\varepsilon$; und mit $\gamma '=\varepsilon \in (\Gamma \setminus \{\#\})^{*}$ ist $\gamma '\gamma =\varepsilon$. Und weg ist #. Aber beenden wir das OT.) --Zahnradzacken 20:00, 28. Jul. 2011 (CEST)

Ich würde ja f mit anpassen, wie gesagt. Und das "sieht" ja den Stack. Zwei Fälle würden beachtet werden müssen: $\#$ und $g\gamma$ mit $g\neq \#$. Der erste Fall schreibt das # einfach an die Ausgaben von $\delta$ wieder hinten ran.

Schön werden die Formeln zwar nicht, aber es geht...

Und ob man nun $\varepsilon$ oder $\#$ als Sonderfall nimmt, läuft ungefähr aufs gleiche raus. Mal probieren: Die zwei Fälle wären dann $\varepsilon$ und $g\gamma$.

Hmm, das "für g ungleich #" fällt weg. Naja, vielleicht ist sorum auch schön. :) --Daniel5Ko 20:33, 28. Jul. 2011 (CEST)

Formeltest: ($\#\notin \Gamma$!)

$\delta \colon Z\times (\Sigma \cup \{\varepsilon \})\times (\Gamma \cup \{\varepsilon \})\to {\mathcal {P}}(Z\times \Gamma ^{*})$,

$f\colon {\mathcal {P}}(Z\times \Gamma \times \Sigma )\to {\mathcal {P}}(Z\times \Gamma \times \Sigma )$

${\begin{aligned}K\mapsto &\{(z',\gamma '\gamma ,\alpha )&|&(z,g\gamma ,a\alpha )\in K,(z',\gamma ')\in \delta (z,a,g)\}\\\cup &\{(z',\gamma ',\alpha )&|&(z,\varepsilon ,a\alpha )\in K,(z',\gamma ')\in \delta (z,a,\varepsilon )\}\\\cup &\{(z',\gamma '\gamma ,\alpha )&|&(z,g\gamma ,\alpha )\in K,(z',\gamma ')\in \delta (z,\varepsilon ,g)\}\\\cup &\{(z',\gamma ',\alpha )&|&(z,\varepsilon ,\alpha )\in K,(z',\gamma ')\in \delta (z,\varepsilon ,\varepsilon )\}\\\end{aligned}}$

Ürx! Naja, mit # wär's noch ein wenig schlimmer. :) --Daniel5Ko 20:57, 28. Jul. 2011 (CEST)

Zwischenüberschrift

Hab' mal in die ersten zwei drei Bücher geschaut, die man so über Google Books finden kann.

• Die haben alle $\delta \colon Z\times (\Sigma \cup \{\varepsilon \})\times \Gamma \to {\mathcal {P}}(Z\times \Gamma ^{*})$ als Typ für $\delta$ und $\#\in \Gamma$ (modulo Bezeichnungen natürlich), also so, wie's schon im Artikel steht.
• Für das eine, das Akzeptieren-durch-leeren-Stack definierte, war sowohl $\#$ als auch $\varepsilon$ der leere Stack.

Das heißt: Entweder schreiben die alle voneinander ab, oder das ist wirklich erheblich einfacher so und drängt sich förmlich auf. Man muss ja auch bedenken: manche Automaten (bzw. eher die meisten, wenn man TI macht) programmiert ja nicht ein intelligenter Mensch, sondern ein Programm bzw. ein Beweis, die als Eingabe z.B. eine beliebige cf Grammatik kriegen usw.

Kurzum: mEn. muss man echt-leere Stacks nicht ausschließen, wenn man $\#\in \Gamma$ hat, und umgekehrt. Nicht mal aus ästhetischen oder puristischen Gründen. Meine simplere $f$-Version von weiter oben kann (nach geeigneter Umbenennung von f und Permutation der Konfigurationstupel) ziemlich direkt in den Artikel übernommen werden. --Daniel5Ko 00:52, 29. Jul. 2011 (CEST)

Ich habe auch nochmal Bücher konsultiert (Hopcroft/Ullman, Lutz/Erk, Schöning, Hromkovic) und konnte auch keine abweichende Notation feststellen. Da muss ich wohl von falscher Intuition getrieben gewesen sein. Zu deiner Notation oberhalb der Zwischenüberschrift könnte ich noch Verknappung durch Abstraktion vorschlagen (mit $g\in (\Gamma \cup \{\varepsilon \})$ sind die Teilmengen 2 und 4 überflüssig), aber überwiegend ist hier alles gesagt. Von mir aus könnte man das ganze hier archivieren, nicht nur wegen meines peinlichen Irrtums, sondern weil deswegen das hier ganz schön aufgebläht ist. --Zahnradzacken 22:18, 29. Jul. 2011 (CEST)

Zum letzten vorletzten Vorschlag: die zwei Mengen stehen ja für die Situation "leerer Stack". Und "nicht-leerer Stack" soll da eben nicht matchen. Beim Muster "$g\gamma$ mit $g\in \Gamma \cup \{\varepsilon \}$" haben wir da ein Problem...

Wenn wir die Mengen trennen wollen, ja, aber ich sehe nicht, wofür die Sonderbehandlung ist. --Zahnradzacken 00:09, 30. Jul. 2011 (CEST)

Wir müssen dem Automaten gestatten, einen leeren Stack erkennen zu können. Wenn jeder Stack matcht (das wäre der Fall, wenn das Epsilon im Muster das $\varepsilon \in \Gamma ^{*}$ wäre), oder überhaupt keiner matcht (das Epsilon im Muster ist Zusatzsymbol in erweitertem Alphabet, tritt nie als Zeichen in einem Wort aus $\Gamma ^{*}$ auf), ist die Information für den Automaten nicht ermittelbar. Der Automat könnte das Problem zwar umgehen, indem er als allererste Aktion in einem Epsilon-Schritt ein sonst nicht verwendetes # pusht, aber dann sind wir wieder in der Situation, echt leere Stacks und #-Stacks zu haben. Zudem funktioniert das nur, wenn Epsilon-Schritte erlaubt sind. --Daniel5Ko 00:51, 30. Jul. 2011 (CEST)

Kein Einspruch mehr. Danke fürs Erklären. --Zahnradzacken 11:31, 30. Jul. 2011 (CEST)

Zum letzten Vorschlag: Also mir ist's recht Wurst, ob's archiviert wird. Aber ich hab' die Diskussion auch ein bisschen zum Experientieren mit Formeln und Formulierungen benutzt, welche jetzt zu einer relativ großen Ergänzung im Artikel geführt haben... --Daniel5Ko 22:41, 29. Jul. 2011 (CEST)

Mir ist es auch egal. Wer das hier (evtl. in 1000 Jahren) liest und zu groß findet, darf es archivieren. --Zahnradzacken 00:09, 30. Jul. 2011 (CEST)

:) --Daniel5Ko 00:51, 30. Jul. 2011 (CEST)

Beispiel

In dem Beispiel ist folgende Tabelle angegeben:

Definition für δ

Parameter			Funktionswert
Zustand	Eingabe	Keller	Zustand	Keller
z0	a	#	z0	a#	(1)
z0	a	a	z0	aa	(2)
z0	b	a	z1	ε	(3)
z1	b	a	z1	ε	(4)
z1	ε	#	z2	ε	(5)

Mir ist da die letzte Spalte "Keller" nicht ganz klar. Soll diese nicht die aktuellen Werte im Keller (nach der Operation) darstellen? Dann müsste sie doch so lauten:

Definition für δ

Parameter			Funktionswert
Zustand	Eingabe	Keller	Zustand	Keller
z0	a	#	z0	a#	(1)
z0	a	a	z0	aa#	(2)
z0	b	a	z1	a#	(3)
z1	b	a	z1	#	(4)
z1	ε	#	z2	ε	(5)

Aber ich kann mir kaum vorstellen, dass das falsch so lange im Artikel stand. Kann es jemand also genauer erklären, was unter den Spalten zu verstehen ist? Danke --StYxXx ⊗ 03:52, 9. Jul. 2009 (CEST)

Wenn ich von dem Beispiel im Weblink ausgehe, sollte dort bei den ersten beiden Zeilen "a" stehen und sonst ε? Bei den beiden ersten wird a geschrieben, sonst ein Zeichen entfernt, was laut Link so ausgedrückt werden würde. --StYxXx ⊗ 04:17, 9. Jul. 2009 (CEST)

Im Beispiel kann man die erste Zeile so übersetzen: Befindet sich der Keller im Zustand z₀ und liegt ein 'a' als Eingabezeichen und ein '#' als nächstes Kellerzeichen vor (blaue Spalten), dann entferne diese Zeichen von der Eingabe (bzw. aus dem Keller) bleibe im Zustand z₀ und schreibe die beiden Zeichen 'a#' in den Keller. Im Keller wird damit das '#' durch 'a#' ersetzt. Die letzte Kellerspalte enthält also nicht den kompletten Stack, sondern nur die Zeichen, die neu 'eingekellert' werden sollen. Gruß, --89.247.87.117 11:46, 9. Jul. 2009 (CEST)

Gehts auch denglisch?

Stack ist eindeutig ein sprachenübergreifender Fachbegriff. Eine Eindeutschung bringt weder eine bessere Verständlichkeit für nicht-Fachleute noch hat der Begriff Buzzword-Charakter und verschleiert irgendwelche "altmodische" Sachverhalte. Geht es bei dieser Eindeutschung nur ums Prinzip oder dient es wirklich der Lesbarkeit oder der besseren Allgemeinverständlchkeit? -- 62.167.75.78 23:10, 23. Mär. 2010 (CET)

Prinzipiell ist das sicher richtig, aber in diesem Fall geht es um den Kellerautomat, der als solcher auch in der einschlägigen deutschen Literatur bezeichnet wird. Konsequenterweise wird dann auch von Kellerspeicher (oder schlicht Keller) gesprochen um hier nicht mit Synonymen hantieren zu müssen, die nur noch mehr Konfusion stiften würden. --89.247.23.187 12:20, 24. Mär. 2010 (CET)

Bild

Beim Bild ganz oben im Artikel finde ich es unglücklich, dass das Eingabeband keine klaren Grenzen hat. (Der Stack hat eine untere Begrenzung, aber keine obere - das ist richtig.) Das Eingabeband müsste sowohl links als auch rechts begrenzt sein. Kann das jemand ändern? Ich bin nicht der große Bildermaler. -- UKoch 12:37, 27. Jul. 2011 (CEST)

Ich finde das jetzt nicht besonders falsch. Bilder lassen halt Interpretationen zu. Die Eingabe selbst ist auch im Bild endlich. Die Frage ist, wozu man überhaupt ein Band als Eingabe malt. Da hier keine Konfiguration definiert wurde, kann der Leser anhand informeller Beschreibung und Definition der Transitionsfunktion nur spekulieren, dass das Eingabeband nicht verändert wird, selbst wenn das Band im Bild endlich wäre.

Ein endliches Band macht eigentlich gar keinen Sinn, denn dann würde es die maximal mögliche Länge der Eingabe beschränken. --Zahnradzacken 15:24, 27. Jul. 2011 (CEST)

Die Def. der Konfiguration will ich "bei Gelegenheit mal" nachholen; die jetzige Beschreibung der Funktionsweise ist ja nicht so toll (wie jemand weiter oben angemerkt hat).

Hm, das mit der Beschränkung der möglichen Länge der Eingabe stimmt. Aber sobald die konkrete Eingabe feststeht, ist die Länge ja beschränkt. Eigentlich ist es so wie beim LBA, nur dass der PDA keine Begrenzungszeichen hat. -- UKoch 19:09, 27. Jul. 2011 (CEST)

Oh ja, die Beschreibung ist wirklich schlimm und missverständlich. Offenbar haben daraus schon einige Nachtrag: ich falsche Schlüsse gezogen.. Am sinnvollsten fände ich eine Grafik ganz ohne Eingabeband. Manche Autoren verzichten auch darauf, andere nicht, einen Überblick habe ich aber nicht. --Zahnradzacken 20:25, 27. Jul. 2011 (CEST)

Das Bild ist eigentlich in Ordnung und offensichtlich der schematischen Abbildung im Schöning nachempfunden (ich habe hier 4. Auflage). Natürlich sind diese Darstellungen immer eine Geschmacksache, aber wenn man sich schon für eine Abbildung entscheidet sollte die Eingabe imo dabei sein, da sie ja ein wesentlicher Bestandteil der Definition ist. --89.247.29.44 20:54, 28. Jul. 2011 (CEST)

Ja, die Eingabe bleibt sowieso. Nur das Band ist ein wenig irritierend. Da es nicht falsch ist, wäre es unnötiger Aufwand, daran etwas zu ändern. --Zahnradzacken 22:06, 29. Jul. 2011 (CEST)

Funktionsweise

Ich hab's mal gewagt, die Erklärung deutlich zu verbessern -- hoffe ich. -- UKoch 19:15, 3. Nov. 2011 (CET)

Hallo. Ich finde es gut, dass du es gewagt hast, ich finde es aber leider nicht besser – aus folgenden Gründen:

• Zunächst möchte ich kurz die Rechtschreibung ansprechen:
  1. Ich glaube, dass es hier eine Regel gibt (die mindestens ein User auch gelegentlich streng durchsetzt), richtige Wortwahl nicht selektiv durch eine andere zu ersetzen. Da nach der Reform der Reform auch "zugrundeliegend" wieder richtig ist [1] (auch wenn es mein Spell-Checker hier auch gerade hervorhebt), bin ich für Beibehaltung dieser Schreibweise.
  2. In "die zugrundeliegende Idee ist folgende:" sollte man "folgende" nicht substantivieren (in Anlehnung an [2]).
  3. Der Duden empfiehlt sogenannt statt so genannt zu schreiben [3]. Wegen des Arguments aus Punkt 1 sollte das außer dir aber niemand ändern ;)
• Zum Inhalt: Aus der Beschreibung wird nicht klar, was ein "Verarbeitungsschritt" ist. Ein Zeichen kann gelesen werden, oder auch nicht. Der Zustand kann gewechselt werden, oder auch nicht (du schreibst aber missverständlich "neuer Zustand"). Der Keller kann sich ändern, oder auch nicht. Aus deiner Beschreibung bliebe übrig, dass ein Verarbeitungsschritt das Herabnehmen des obersten Zeichens im Keller sei und dann etwas oder nichts wieder oben drauf gelegt wird.
• Ich glaube, mit wenigen Worten ist es schwierig, nichtdeterministisches Verhalten so zu beschreiben, dass es nah an der Definition ist. Mein Vorschlag ist, dass man zunächst auf den Fall, dass die Eingabe nicht gelesen wird, verzichtet. Dann kann man als Nächstes das nichtdeterministische Verhalten in zwei Formen beschreiben: 1. Nach jeder Verarbeitung eines Eingabezeichens sind verschiedene Konfigurationen möglich. 2. Zwischen jeder Verarbeitung kann die Konfiguration auch ohne Lesen der Eingabe geändert werden.

Dabei fällt mir auf, dass die Bedingung für eine deterministische Übergangsfunktion so wohl nicht stimmt, denn wenn $\varepsilon$-Übergänge möglich sind, gibt es zu einer Eingabe durchaus mehrere Abläufe. Überhaupt wird auf deterministische Kellerautomaten viel zu wenig eingegangen. Das Code-Beispiel ist aber ein deterministischer Kellerautomat, ohne dass das erklärt wird.

--Zahnradzacken 02:13, 4. Nov. 2011 (CET)

Danke fürs Feedback.

• Zur Rechtschreibung: OK. Ändere ich gleich.
• Zum Inhalt:
  • Das Wort "Verarbeitungsschritt" ist wahrscheinlich unglücklich. Wäre "Rechenschritt" besser? Den Begriff "Konfiguration" möchte ich hier möglichst vermeiden. Dass in einem Schritt "nichts zu passieren braucht", liegt aber nicht an der Beschreibung, sondern an der Def. des PDA. Das gilt auch, falls der PDA deterministisch ist.
  • Ob aus der Eingabe gelesen wird oder nicht, hat erstmal nichts mit det./nichtdet. zu tun. Auf nichtdet. Verhalten bin ich in der Beschreibung gar nicht eingegangen. Deinen Vorschlag fände ich gut, wenn Du noch auf den Begriff "Konfiguration" verzichten könntest. Vielleicht besser zuerst den Nichtdeterminismus 'rauslassen?
  • Die Bedingung für eine deterministische Übergangsfunktion passt sowohl zu Hopcroft/Ullman als auch zu Erk/Priese. Klar sind dann mehrere Abläufe zu einer Eingabe möglich -- aber der einzige Unterschied ist, dass nach dem Abarbeiten der Eingabe noch Epsilon-Übergänge gemacht werden können. Da dabei sowohl Endzustände als auch Nicht-Endzustände vorkommen können, sollte das natürlich in den Artikel.

-- UKoch 15:16, 4. Nov. 2011 (CET)

Danke für die Hinweise. Nächstes Mal schaue ich lieber erst wieder in die Bücher, bevor ich etwas zu Kellerautomaten sage!

• Zum "Verarbeitungsschritt". Ich finde das Wort nicht unglücklich, aber in dem ganzen Absatz wird nicht klar abgegrenzt, was der eigentliche Schritt ist, und was vor, nach und parallel zu jedem Schritt zu passieren hat. Auf das Wort "Konfiguration" können wir ruhig verzichten, aber irgendwas Griffiges wäre sinnvoll und "Zustand" hat schon eine andere Bedeutung. Richtig, in einem Schritt muss laut Definition nichts passieren, aber dann ist natürlich die Frage, was der Schritt dann ist (intuitiv).
• Zur Eingabe: Ja, da habe ich mich geirrt. Mein Vorschlag war so gemeint, dass man zunächst Nichtdeterminismus "verschweigt" und dann nachträglich erklärt. Also, dass man erst ein verständlicheres "Idealverhalten" beschreibt und dann zu den Knackpunkten kommt. In diese Aufteilung könnte man auch die Epsilon-Schritte einbeziehen, um im ersten Teil eine wirklich leicht verständliche Intuition aufzubauen.
• Zu Epsilon-Schritten: Erneut mein Fehler (bzw. zweimal gleicher Irrtum). Es stimmt nur nicht die Beschreibung. Dennoch müsste den DPDAs mehr Platz eingeräumt werden (oder ein eigener Artikel, wie en:Deterministic pushdown automaton).

--Zahnradzacken 18:02, 4. Nov. 2011 (CET)

Ja, die Kellerautomaten sind schwieriger, als man zuerst denkt. In Erk/Priese werden solche Sachen wie Epsilon-Übergänge, (Nicht-)Det. und die Folgen daraus m.E. schön ausführlich dargestellt; hat mir viel gebracht.

Wir sind uns offenbar einig, dass erstmal der Nichtdeterminismus "verschwiegen" werden soll und dass es ohne das Wort "Konfiguration" gehen müsste. Dann schlag doch eine Formulierung vor; vielleicht sind wir gar nicht weit voneinander entfernt.

Ich habe noch Daniel5Ko Bescheid gesagt; vielleicht hat er ja Interesse, hier mitzudiskutieren.

-- UKoch 15:58, 7. Nov. 2011 (CET)

Neuer Anlauf

Ich hab' mal versucht, Zahnradzackens Anregungen einzuarbeiten und die Erklärung insgesamt "runder" zu machen. Mein neuer Vorschlag:

Ein Kellerautomat dient dazu, zu klären, ob eine Eingabe (d.h. ein Wort aus null, einem oder mehreren Zeichen) zu einer formalen Sprache (d.h. einer Menge von Wörtern) gehört. Dafür arbeitet der Automat eine Eingabe Schritt für Schritt ab und kann dabei eine Reihe von Zuständen annehmen. Zu Anfang ist er im sogenannten Startzustand. Typischerweise wird in jedem Verarbeitungsschritt ein Zeichen aus der Eingabe gelesen; dabei wird die Eingabe von links nach rechts verarbeitet. Außerdem wird in jedem Verarbeitungsschritt das oberste Zeichen vom Keller gelesen, d.h. abgenommen. Abhängig vom aktuellen Zustand, dem gerade gelesenen Eingabezeichen und dem gerade gelesenen Kellerzeichen geht der Automat in einen neuen Zustand über und legt ein Wort auf dem Keller ab. Wenn die Eingabe komplett gelesen wurde und der Keller leer ist, gehört die Eingabe zur vom Automaten erkannten Sprache.

Allgemein sind allerdings mehrere Abweichungen von der obigen Erklärung möglich:

• Die erkannte Sprache kann auch als die Menge der Wörter definiert werden, bei deren Abarbeitung der Kellerautomat einen sogenannten Endzustand erreicht - unabhängig davon, ob dabei der Keller geleert wird.
• Nicht in jedem Verarbeitungsschritt muss ein Zeichen aus der Eingabe gelesen werden. Wenn keins gelesen wurde, wird das gelesene Wort als $\varepsilon$ bezeichnet.
• Für manche Kombinationen von Zustand, Eingabezeichen (oder $\varepsilon$) und Kellerzeichen kann der Kellerautomat die Wahl zwischen mehreren Übergängen (also Kombinationen von Folgezustand und Kellerwort) haben. Die Eingabe gilt in diesem Fall als erkannt, wenn der Keller geleert werden kann bzw. ein Endzustand erreicht werden kann.

Was meint die geneigte Leser(innen)schaft? -- UKoch 18:56, 1. Dez. 2011 (CET)

Ich habe die Erklärung jetzt durch Obiges ersetzt. -- UKoch 18:31, 9. Dez. 2011 (CET)

Geht das hier auch für Nichtinformatiker verständlich??

Keller/Stack - Kellerautomat/-automat, dazu einige Bilder und Formeln... Ist dass, was der Wikidau verstehen soll? Fragender Gruss, 78.52.101.230 20:31, 29. Aug. 2016 (CEST)