Zweikellerautomat

Hallo zusammen,

ich würde gerne wissen, wie die Syntax aussieht bei der Verwendung eines zweiten Stacks.

Ich kenne nur den Kellerautomat mit einem Stack und da beschreibe ich
das folgenderweise im Graph, wenn ich da was pushe oder pope.

Eingabe : aktuelles Kellerzeichen -> Neues Kellerzeichen

Frage, wie muss es dann aussehen um zu Entscheiden in welchen Stack ich was
pushen oder popen will?

oenone

Meinst du einen 2-PDA oder einen TPDA?

2-PDA: Der Zweikellerautomat liest von einem Extra-Eingabeband und kann dabei zwei Kellerspeicher zum Speichern und Lesen nutzen.

TPDA: Der Zweikellerautomat bekommt seine Eingabe direkt im Keller: Das erste Zeichen steht dabei oben. Dieses Modell ist das jüngere Modell.

(aus: http://de.wikipedia.org/wiki/Zweikellerautomat).

Danke für die schnelle Antwort,

gesucht habe ich bisher nach einem TPDA, aber nach deiner Erklärung
wäre der "2-PDA" logischerweise idealer für mich.

Hast du dafür evtl. ein kleines Beispiel?

oenone

Das scheint wirklich etwas exotisches zu sein. Wofür willst du sowas denn benutzen?

TPDA scheint äquivalent zu einer Turingmaschine zu sein, der linke Stack ist der Inhalt des linken Teils des Bandes und der rechte Stack der Inhalt des rechten Teils des Bandes.

Brauchst du auch zwei Eingabebänder? Wenn nicht, hätte ich naiverweise jeweils Tuple der beiden Stacks benutzt, z.B. Eingabe: (Stack1, Stack2) -> (NeuStack1, NeuStack2).

Demnächst habe ich eine Klasur und bereite mich vor, und von Studenten höherer Semester habe ich mitbekommen, das der Prof. das gerne in eine Klausur einbaut.

Problem dabei ist, das wir das in der Vorlesung nur kurz angesprochen haben (also nur gesagt bekommen, das es Kellerautomaten mit mehreren Stacks geben kann, und mehr nicht).

Deshalb schaue ich gerade nach Beispielen, welche zwei Stacks verwenden.