Darf ich in den Keller was anderes schreiben, als ich lese?

Question

Hallo,

woaas, jetzt bin ich verwirrt.

Ist folgender Übergang bei Kellerautomaten korrekt: (s0, a, k0) --> (s1, bk0) ?

Also darf ich, wenn ich ein a lese ein b in meinen Keller schreiben?

Wenn ich das dürfte wäre doch die Lösung der Aufgabe mit weniger Unterscheidungen lösbar, oder?

Comments

Es kann sein, dass es eine einfachere Lösung gibt. Machen Sie mal einen Vorschlag - am besten mit XWizard:
http://www.xwizard.de:8080/Wizz?template=pda:#Output

Answer 1

Hallo,
allgemein darf ich alles was im Kelleralphabet steht in den Keller schreiben. Dabei ist es egal ob es mit dem gelesenen Zeichen übereinstimmt.
Viele Grüße,
Janina (Tutorin)

Answer 2

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 $\lambda$ 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 $aSb$ auf den Keller schreibt, also ein Zeichen löscht und drei neue schreibt.