Auch mit deterministischem KA lösbar?

Question

Könnte man die Aufgabe auch mit einem deterministischen KA lösen?

Mein Ansatz ist folgender:

Ich schreibe immer nur die Einsen in den Keller (dabei gehe ich in einen Zustand s1, der nicht EZ ist). Wenn eine (erste) Null kommt, gehe ich in einen Zustand s2. Lese ich in s2 noch eine Null, wird eine Eins aus dem Keller gelöscht und ich gehe wieder in s1.
Lese ich in s2 eine Null und sehe k0, dann schreibe ich diese Null in den Keller. Bin ich in s1, lese eine Eins und sehe eine Null im Keller, so lösche ich diese Null und bleibe in s1. Sehe ich in s1 das k0 im Keller, so mache ich einen lambda-Übergang nach s0, was auch gleichzeitig mein EZ ist.

Und noch eine allgemeine Frage: Auf Folie 3-5 steht bei der Definition der partiellen Überführungsfunktion, dass man auch mehrere Zeichen auf einmal in den Keller schreiben kann (... -> S x K*) - stimmt das? Und wenn ja - wie werden diese dann ausgelesen? Als eine "Kette", oder einzeln nacheinander?

Viele Grüße!

Answer 1

Am zweiten Teil deines Ansatzes muss man glaube ich noch arbeiten. So realisierst du nicht, dass zwei einsen folgen müssen, nachdem eine 0 eingelesen wurde, wenn man nur ko im Keller hat. Ist aber ohne konkrete Übergänge schwer zu sagen.

Beachte aber, dass dein KA durch den lambda-Übergang nicht deterministisch wird.

Ja, man kann auch mehrere Zeichen auf einmal in den Keller schreiben. Nachdem sie in den Keller eingetragen wurden, wird der Lese-/Schreibkopf für den Keller auf das oberste Kellerzeichen gesetzt. Das heißt nach dem Eintragen mehrerer Zeichen auf einmal weiß der KA nicht mehr, dass er dies einmal getan hat. Es wird dann immer nur das oberste Kellerzeichen betrachtet.

Viele Grüße,

Sven (Tutor)

 

Comments

Okay, erstmal danke - hab ich mir schon fast gedacht, dass es schwierig ist ohne Übergänge, aber ich wollte die nicht unbedingt alle abtippen ;)