Alternativer Lösungsvorschlag

Question

Wäre etwas an diesem KA falsch:  

1) Schreibe bei Eingabe 0 eine 0, bei Eingabe 1 zwei 11 in den Keller, wechsel in Zustand s1

(so,0,ko) -> (s1,0ko)

(so,1,ko) -> (s1,11ko)

(s1,0,0) -> (s1,00)

(s1,1,1) -> (s1,111) (zwei Einser vor die letzte schreiben)

(s1, 0,1) -> (s1, Y)    Y=lambda

(s1,1,0) -> (s1,Y)

(s1,0,ko) -> (s1, 0ko)

(s1,1ko) -> (s1,11ko)

(s1,Y,ko) -> (so, ko)

 

?

Comments

habe bei meiner Lösung die folgenden 2 Übergänge vergessen:

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

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

Answer 1

Hallo,

deine Ergänzung kam leider erst, als ich schon angefangen hatte zu schreiben. Mit dieser Ergänzung müsste dieser Automat in der Tat funktionieren.

Beste Grüße

Fabian (Tutor)

 

Comments

Hi Fabian,

erstmal danke für die schnelle antwort! Die zwei fehlenden Übergänge hatte ich nachträglich noch angefügt!

Da in meinem Zustand s1 nur (s1, Y, 1) -> (s0, 11) definiert ist, wäre mein KA also immer noch deterministisch! Und ergänzt um die genannten Übergänge damit auch eine korrekte Lösung der Aufgabe oder nicht?

---

Hallo,

dein Automat ist nicht-deterministisch, da du einen Übergang (s0, lambda, k0) und einen Übergang (s0, 1, k0) definierst. Da in der Aufgabe aber keine Aussage über deterministisch/nicht-deterministisch gemacht ist, wäre die Lösung vermutlich ok.

Beste Grüße

Fabian (Tutor)

Answer 2

Hallo,

dass Sie zwei Zeichen bei einem Übergang in den Keller schreiben bei (s1,1,1) -> (s1,111) , ist zwar, laut Definition im Skript, nicht ausgeschlossen, aber sehr unüblich.
Bei folgendem Übergang (s1,1ko) -> (s1,11ko) sollten Sie das k0 streichen. Der Automat kennt immer nur das oberste Kellerzeichen.

Viele Grüße
Friederike Pfeiffer