alternativer Lösungsvorschlag

Question

Moin moin,

wäre die Touringmaschine so auch in Ordnung:               

	0	1	$	*
S0	(S1,1,R)	(S1,1,R)	(S0,1,R)	(Sd,0,L)
S1	(S1,1,R)	(S1,1,R)	(S2,1,R)	(Se,*,L)
S2	(Sdd,0,R)	(Sdd,0,R)	(S2,1,R)	(Se,*,L)
Sd	(Sd,0,L)	(Sd,0,L)	(Sd,0,L)	(Sf,*,R)
Sdd	(Sdd,0,R)	(Sdd,0,R)	(Sdd,0,R)	(Sd,*,L)
Sf
Se

 

mit Anfangszustand So und den beiden Endzuständen Sf und Se?

Vielen Dank :)

 

Answer 1

Im wesentlichen ja allerdings kannst du die beiden Endzustände zu einem zusammenfassen. Wenn man deiner TM das leere Wort eingibt, überschreibt sie einen Stern (der nicht zur Eingabe gehört) mit einer 0. Das ist in der Aufgabenstellung nicht explizit verboten, aber auch nicht verlangt. Die Musterlösung lässt in diesem Fall das Band leer. Daher wäre es vielleicht besser, wenn du den Übergang  (s0, *) -> (sd, 0, L) auf (s0, *) -> (sd, *, L) änderst.

Tobias (Tutor)