zusätzliche Regeln erforderlich?

Question

Hallo,

müsste in der Lösung nicht stehen: (s3,1,b) -> (s3,1b) anstatt (s3,b1)?

Und wenn man das Testwort 100 betrachtet, fehlt dann nicht bei s3 noch ein (lambda,1,lambda) Übergang, damit die 1 im Keller gelöscht wird und man im Endzustand s0 landet?

Answer 1

Hallo,

Zur ersten Frage: So, wie es in der Musterlösung angegeben ist, funktioniert der Kellerautomat in jedem Fall. Mit dem betrachteten Übergang von (s3, 1, b) --> (s3,b1) wird der "Übertrag" also die gemerkte 0 dann bereits früher abgearbeitet, indem das b gelöscht wird.  Hier lohnt es sich Aufgabenteil b) genauer zu betrachten. Ich denke, deine Lösung würde dennoch auch funktionieren.

Zur zweiten Frage, hier die entsprechende Ableitung des Testworts 100. 

(s0, 100, k0) ⊢ (s3, 00, 1k0) ⊢ (s3, 0, bk0) ⊢ (s3, λ, k0) ⊢ (s0, k0)

Dabei ist zu beachten, dass die 1, die in den Keller geschrieben wird in Zustand s3 beim Lesen der 0 bereits durch das b überschrieben wird und somit nicht mehr im Keller steht. Daher muss sie nicht mehr gelöscht werden.

Viele Grüße,

Dominik (Tutor)

Comments

Alles klar vielen Dank, ich bin fälschlicherweise davon ausgegangen, dass das b in der Notation der Regeln in dem Fall bedeutet, dass es auf die 1 geschrieben wird. Jetzt ist es klar :)