Question

(a) Give a high level description of a single-tape deterministic Turing machine that decides the language L = {w#x#y | w ∈ {0, 1} ∗ , x ∈ {0, 1} ∗ , y ∈ {0, 1} ∗ , and |w| > |x| > |y|}, where the input alphabet is Σ = {0, 1}. (b) What is the running time (order notation) of your Turing machine? Justify your answer.

Answer 1

The idea behind the design is if all symbols in y get crossed or blanked, we check if there is any symbol left in X,

if yes then cross or make blank all symbols in w corresponding the symbols in y. And now check if any symbol left in w

if yes, halt in accepting state

else halt in rejecting state

(a)

Here the language given is L = { w#x#y | w {0,1}* , x {0,1}*, y {0,1}* and |w| > |x| >|y|}

So let us design the Turing machine M for L as below:

1. start from state q0 and read the string from the left end.
2. getting either 0 or 1 at state q0, puts B (blank symbol), changes to q1 and moves right.
3. at q1 getting 0 or 1, puts the same symbol, stays at q1 and moves right.
4. at q1 getting # puts #, changes state to q2 and moves right.
5. getting either 0 or 1 at state q2, puts B (blank symbol), changes to q3 and moves right.
6. at q3 getting 0 or 1, puts the same symbol, stays at q3 and moves right.
7. at q3 getting # puts #, changes state to q4 and moves right.
8. getting either 0 or 1 at state q4 puts B (blank symbol), changes to q5 and moves right.
9. getting either 0 or 1 q5 puts the same symbol, changes to q6 and moves left.
10. getting # at q6 puts #, changes state to q7 and moves left
11. at state q7 getting 0,1 puts the same symbol, stays at q7 and moves left
12. getting # at q7 puts #, changes state to q8 and moves left.
13. at state q8 getting 0,1 puts the same symbol, stays at q7 and moves left.
14. getting B at q7 puts B, changes state to q0 and moves right. and so on it will make the string y of B's
15. Now at q5 when it sees B, then it will check whether there are any 0 or 1 left in x. q5 will put blank and change state to q9.
16. q9 looking 0,1,# puts the same symbol, stays at q9 and moves left. but getting B it puts B and changes state to q3 and moves right.
17. if there are any 0 or 1 left, (if q3 sees 0 or 1, it puts the same symbol, changes state to q6 and moves left) then
18. it will transform corresponding 0 or 1 to B in w.
19. now if in x all are blank symbols (if q3 sees a B, puts B, changes state to q10 and moves left)
20. q10 staying at q10 moves left getting 0,1,#. getting B changes state to q1 and moves right.
21. if there are some 0 or 1 left in w, i.e if q1 sees 0 or 1.
22. then halt in accepting state.
23. else halt in rejecting state (if q1 sees a B)
24. else halt in rejecting state.

For example :