Kellerautomat - Mehr als ein Zeichen auf den Stack legen

Question

Hallo,

Ich hätte folgende Frage: Sind Übergänge gemäß der Art (S,a,ak0) -->(S, ,aaak0) bei Kellerautomaten erlaubt? Darf man auf den Stack mehr als ein Zeichen pro Übergang drauflegen? Das würde z.B Aufgabe 45 sehr viel leichter machen.

LG,

uzpth

Answer 1

https://info2.aifb.kit.edu/qa/index.php?qa=3539&qa_1=darf-ich-in-den-keller-was-anderes-schreiben-als-ich-lese&show=3539#q3539

Zitat Lukas König: "Vielleicht noch zur Ergänzung: Man darf nicht nur jedes Zeichen auf den Keller schreiben, das im Kelleralphabet steht, sondern auch beliebige Kombinationen von Zeichen aus dem Kelleralphabet. Man darf also sowohl 

λλ auf den Keller schreiben, als auch ein einzelnes Kellerzeichen als auch belibig lange Ketten von Kellerzeichen. Gelesen wird dabei aber immer nur ein einziges Zeichen, das oberste, und dieses wird vor dem Schreiben aus dem Keller gelöscht.

Schauen Sie sich als Bespiel für Kellerautomaten, die mehr als ein Zeichen auf den Keller schreiben, ruhig mal das Verfahren an, um aus einer kontextfreien Grammatik einen Kellerautomaten zu machen. 

Auch der XWizard kann das, klicken Sie bei dieser Grammatik mal auf die Konversions-Methode "Kellerautomat":

http://www.xwizard.de:8080/Wizz?template=ID-12630#Output

Es kommt ein Automat heraus, der an einer Stelle aSbaSb auf den Keller schreibt, also ein Zeichen löscht und drei neue schreibt."

Comments

https://info2.aifb.kit.edu/qa/index.php?qa=4840&qa_1=s3-1-b-s3-b1-kann-man-kellerzeichen-im-keller-tauschen&show=4840#q4840
Zitat Tutor:"Man kann nur das oberste Kellerzeichen lesen und dann durch ein beliebiges Wort

∈K∗∈K∗ ersetzen.

Bei (s3,1,b)→(s3,b1)(s3,1,b)→(s3,b1) werden nicht die obersten zwei Kellerzeichen getauscht, sondern nur das oberste Kellerzeichen bb durch b1b1 ersetzt. Diese Überführung ist also erlaubt und somit ist auch die Ableitung des Testwortes korrekt.

Viele Grüße

Philipp (Tutor)"

https://info2.aifb.kit.edu/qa/index.php?qa=5992&qa_1=mehrere-kellerzeichen-gleichzeitig-löschen
Zitat Tutor:"Schauen wir uns hierfür ein Teil der Definition aus dem Lehrbuch an (S.49-50):

"Wenn sich der Kellerautomat in Zustand s ∈ S befindet und auf dem Eingabeband e gelesen wird und das oberste Kellerzeichen k ∈ K ist, dann wird k im Keller durch das ganze Wort v ∈ K* ersetzt, indem dieses von hinten nach vorne zeichenweise auf den Keller gepusht wird".

Desweiteren gilt für die Zustandsüberführungsfunktion folgendes:

δ∶ S × (E ∪ {λ}) × K → S × K*

Da der Lese/Schreibe-Kopf des Kellers immer auf dem obersten Kellerzeichensteht und nur dieses liest, sind nur Zustandsübergänge folgender Form erlaubt:

δ(s, e, k) = (s ′ , v)    mit s, s' ∈ S, e ∈ E, k ∈ K und v ∈ K*.

k besitzt daher nur ein Element aus K (und nicht wie du es angeben wolltest zwei Elemente (00).

Zusammenfassend können wir also sagen, dass pro Rechenschritt jeweils nur das oberste Zeichen des Kellers überschrieben bzw. gelöscht werden kann."