Kellerautomat Zustandsüberführungsfunktion

Question

laut Definition aus dem Buch heißt es für die KA Zustandsüberführungsfunktion:

entweder $\delta(s, e, k) = (s', v)$ oder $\delta(s, \lambda, k) = (s', v)$ mit $e \in E$, $s,s' \in S$, $k \in K$, $v \in K^\star$.

$v$ stellt hier eine Zeichenkette dar, die beliebig lang sein kann ( also auch $\lambda$). Hab ich das richtig verstanden? Mir ist nicht ganz klar wann es sich anbietet $|v| > 1$ zu verwenden? Kann mir jemand eine Beispielsprache nennen? Vor allem da ich eigentlich verinnerlicht hatte, dass nur EIN Zeichen aus dem Keller gelöscht und EIN Zeichen reingeschrieben werden kann. Bezieht sich $v$ hier etwa auf den gesamten Kellerinhalt?

Comments

Es heißt LAMBDA!

Answer 1

Die Zeichenkette $v$ bezeichnet die Zeichen, die oben auf den Keller abgelegt werden. Das ist oft das leere Wort $\lambda$ oder eine Kette aus zwei Zeichen. Im ersten Fall wird das oberste Zeichen aus dem Keller entfernt und danach $\lambda$ hineingeschrieben, effektiv wird also das oberste Zeichen gelöscht.

Der zweite Fall ist, dass das oberste Zeichen gelöscht wird und stattdessen zwei Zeichen hineingeschrieben werden, der Keller wächst also um ein Zeichen an. Oft ist dabei das untere der beiden hineingeschriebenen Zeichen dasselbe, das zuvor schon im Keller stand, sodass effektiv nach dem Rechenschritt ein Zeichen auf den Keller oben abgelegt wurde.

Eher selten (im Kontext der Vorlesung), aber genauso möglich sind Fälle, wo ein Zeichen in den Keller geschrieben wird, das bedeutet, dass das oberste Zeichen also einfach nur ersetzt wird, sowie Fälle, wo mehr als zwei Zeichen in den Keller geschrieben werden. Um die Sprachmächtigkeit des Kellerautomaten zu erhalten, ist es wichtig, dass beliebig lange Zeichenketten für $v$ zugelassen werden. Einen Anwendungsfall dafür sehen Sie etwa im Buch auf Seite 179 (oder auf den Folien ab 3-24), wo ein Algorithmus zur Konstruktion eines Kellerautomaten zu einer beliebigen Kontextfreien Grammatik präsentiert wird.

Comments

Vielen Dank!