Undefinierte Zustände im Kellerautomat

Question

Wenn für einen Kellerautomaten eine Konfiguration nicht definiert ist, aber diese auftritt, weil z.B. das Wort nicht zulässig ist, wie wird das behandelt?

Stoppt der Kellerautomat einfach im aktuellen Zustand, weil die Eingabe nicht definiert ist oder lehnt der Kellerautomat das Wort automatisch ab, weil es keine definierte Konfiguration dafür gibt?

Falls ersteres der Fall sein sollte, dürfte der Kellerautomat bei einem unzulässigen Wort sich nicht in einem Endzustand befinden - oder?

Comments

Wenn wir bspw. 2012-N-03 a) betrachten:
Wenn wir das Wort 110 haben, ist das ja nicht zulässig, aber der Kellerautomat befindet sich nach 11 in se aber für (se,0,k0) ist ja kein Zustand definiert.

---

weil soweit ich weiß, hält ja eine Turingmaschine für eine nicht definierte Konfiguration im aktuellen Zustand; das ist glaube ich auch ein Unterschied zum Kellerautomaten oder?

Answer 1

Hi,

allgemein ist es so, dass Wörter nur als angenommen gelten wenn der Kellerautomat/Endliche Automat/Touringmaschine in einem Endzustand stoppt.

Also würde der Kellerautomat wenn er vorher stoppen muss, da keine Folgekonfiguration vorhanden ist das Wort ablehnen.

Grüße

Constantin

(Tutor)

Comments

Aber wie verhält sich das, wenn ich z.B. s0 als Anfangs- und Endzustand habe und keine Konfigurationsfolge von dort aus?
Dann wird jedes Wort nie eingelesen, aber der KA/EA/TM befindet sich trotzdem in einem Endzustand. Wird dann das Wort trotzdem akzeptiert?