Automat in Aufgabe 41 a) nichtdeterministisch?

Question

Guten Tag,

wieso steht bei Aufgabe 41a) im Übungsbuch, dass der Übergang (s0,y,k0)->(se,k0) nichtdeterministisch sei? 

(s0,y,k0) kommt doch sonst auf keiner linken Seite der Übergangsrelation vor und es ist dementsprechend eindeutig, wie der Übergang auszusehen hat oder?

Bei Aufgabe 44 verstehe ich die Begründung ,,Durch die Übergange (s0,y,k0) gekoppelt mit (s0,a,k0), [...] wird der Automat nichtdeterministisch." ebenso wenig. 

Mit freundlichen Grüßen

uzhrz

Answer 1

Hallo,

da sowohl bei Aufgabe 41, als auch bei Aufgabe 44 ein Lambda-Übergang notwendig ist, um den Automaten vollständig zu definieren, sind beide Automaten damit auch direkt nichtdeterministisch.

Bei einem Lambda-Übergang findet ein Zustandsänderung statt, ohne dass etwas in den Keller geschrieben, bzw. eingelesen wird. Dieser ist immer automatisch ein nichtdeterministischer Schritt, da man theoretisch alternativ auch das nächste Zeichen des abzuarbeitenden Wort "bearbeiten" könnte (Siehe Tut 2).