Question

create a deterministic turing machine which takes two words w1, w2 ∈ {a, b, c, d}* , separated by a # symbol in the form Bw1#w2B and determines whether string w2 is a substring of w1

Answer 1

To explain this we have taken a string composed of only a,b and rest alphabets are not appear as it is given any combination of the alphabet will be accepted by the Turing machine. The figure below shows the example.

In the figure dotted lines means all the unused alphabets from { a,b,c,d}^* are sent to the reject state. As we can see that w2 must be a substring of w1 , otherwise the letter # will not be paired and finally the string will be rejected. In other words,the length of w2 must be less than the length of w1.