Question

1. (TM descriptions) (a) Give the sequence of configurations that the following TM M enters when given as input strings 1##1 and 0#0. Please use the same representation for your configurations as we did in lecture 10. The reject state and transitions to the reject state are not shown. Whenever the TM encounters a character for which there is no explicit transition that means that the TM goes to the reject state. We say that the head moves right in each of these transitions to the reject state.

Answer 1

The execution of the above Turing machine can be simulated using this table-

Here Bold character indicated the position of machine on string.

1##1 -

Curr. State	Curr. string	Curr. Character	Move(L/R)	New character	New state	Changed string
q1	1##1	1	R	x	q3	x##1
q3	x##1	#	R	-	q5	x##1
q5	x##1	#	R	-	REJECTED

Now the transition is not defined for symbol # in state q5. So it rejects the string 1##1.

It can be written as-

[q1]1##1 -> x[q3]##1 -> x#[q5]#1 -> REJECT

------------------------------------------------------------------------------------------------------------

0#0-

So the string is accepted.

It can be written as-

[q1]0#0 -> x[q2]#0 -> x#[q4]0 -> x[q6]#x -> [q7]x#x -> x[q1]#x -> x#[q8]x -> x#x[q8] -> ACCEPT

Please note that that the table was there just for explanation, the lines in bold were the actual notation used for turing machines.

I hope it helps. For any doubt, feel free to ask in comments, and give upvote if u get the answer.