alternativer Lösungsvorschlag: auch deterministisch?

Question

Ist die folgende Lösung auch nicht deterministisch bzw falsch?

 

(s0,1,k0)->(s0,1k0)

(s0,0,k0)->(s0,0k0)

 

(s0,0,0)->(s0,00)

(s0,1,1)->(s0,11)

 

(s0,1,0)->(s0,lambda)

(s0,0,1)->(s0,lambda)

 

(s0,lambda,ko)->(se,k0)

 

Wobei se einziger gültiger Endzustand ist.

Grüße, Patrick.

Answer 1

Hallo Patrick,

der Kellerautomat ist leider auch nicht deterministisch.

Das liegt an folgenden Übergängen:

(s0,1,k0)->(s0,1k0)

(s0,0,k0)->(s0,0k0)

und

(s0,lambda,ko)->(se,k0)

Das Problem liegt darin, dass du dich in dem Fall "Zustand s0 und k0 oberstes Zeichen im Keller" zwischen mehreren Alternativen entscheiden kannst. Deshalb ist der Automat eben nicht deterministisch.

Allgemein kannst du einen Lambdaübergang nur dann bei einem deterministischen Automaten aufstellen, wenn sonst niemals die gleiche Kombination aus Zustand und obersten Symbol im Keller vorkommt.

Viele Grüße

Lukas (Tutor)

Comments

Hallo Lukas,

jetzt bin ich völlig verwirrt

(s0,1,k0)->(s0,1k0)

(s0,0,k0)->(s0,0k0)


ist also nicht deterministisch, weil s0,k0 zweimal vorkommt und er deswegen nicht sicher sagen kann wohin er geht.

[Hängt das nicht auch von der Eingabe 1 oder 0 ab?]


In der Musterlösung gibt es aber folgende Zeile:

(s0,1,k0)->(s1,1k0)

(s0,0,k0)->(s1,0k0)


warum ist diese denn deterministisch?

---

Der Automat in der Musterlösung ist detetministisch, weil er eben immer genau weiß, welchen Übergang er in Abhängigkeit von dem nächsten Symbol der Eingabe wählen muss. Hier gibt es keinen Lambda-Übergang, den er alternativ auswählen könnte.

Wenn du allerdings einen Lambda-Übergang dabei hast (bei der gleichen Kombination von Zustand und oberstem Zeichen im Keller!!!), kannst du dich entscheiden, ob du eben diesen Lambda-Übergang, oder einen der anderen Übergänge auswählst.

Viele Grüße

Lukas (Tutor)

Answer 2

Hallo,

nein, der Automat ist nichtdeterministisch, da neben diesen Übergängen noch ein Lambda-Übergang von s0, k0 existiert. Man kann sich das so vorstellen, dass der Automat nicht "weiß" , ob er direkt weitermacht (lambda), oder auf die Eingabe von 0 oder 1 wartet.

Viele Grüße

Philippe (Tutor)