Question

each one of the following languages defined over {0,1}, give the transition diagram of a deterministic, single tape Turing Machine.

{0³ⁱ 1 0²ⁱ 1 0ⁱ | i > 0}

Answer 1

We will start processing string from left to right, where in each scan from left to right, we will convert three 0s in leftmost substring before 1 into symbol XXX, then we convert two 0s in middle substring into XX and we covert one 0 in last substring to X. Thus if string is in the form of 0³ⁱ10²ⁱ10ⁱ then accept else reject.

Till now we have converted three 0s of leftmost substring to X

Now we will convert two 0s to XX

Now we have come to rightmost substring, where we replace one 0 by X

//Now start moving left

So one scan from left to right is completed, now we move back to left input position

//Now we are in rightmost position of leftmost substring

//If there is still 0, it means some more portion of string are yet to process

//Now repeat the task of scanning from left to right

//This means entire leftmost substring has been processed and hence we need to verify whether all other substring has been processed

//simply pass over the processed inputs

Now we are in rightmost substring

//simply pass over the processed input

//B indicate blank

Hence above Turing machine will enter into state q_accept if and only if input is in the form of 0³ⁱ10²ⁱ10ⁱ where i > 0.

Please comment for any clarification.