Question

Design a nondeterministic Turing Machine to accept the {ww | w ∈ {0,1}*} . Draw the transition diagram of the machine.

Answer 1

Non-deterministic turing machine

Consider the string "abaaba". this process have 2 stages . 1st stage is to find midpoint.2nd stage is to check whether the string is acceptable or not.

The below turing machine will accept a string in the form of "ww". for example consider the string "101101".

1st stage:

This TM will convert 0 into X and 1 into Y.

TM will scan the input string from left to right. when see the 1st '1' which will be converted into 'Y' and it will move to right upto the end of the string and the last '1' also be converted into 'Y'. now the string will look like Y0110Y. then it will move to Left most side and convert '0' into 'X' then move to right most side and convert last '0' into 'X'. now the string is YX11XY. it will do the similar action for the remaining string also. finally it will look like " YXYYXY ".

2nd stage :

After completing this conversion we have found the midpoint of the string. next step is to convert left part of the string into 0's and 1's. now the string in the form of 101YXY. after this again we need a conversion to check the string is acceptable or not. for that move to left and convert '1' into Y and move right convert Y into Blank (B). now the string is Y01BXY. then move to left and convert 0 into 'X' and move right convert X into B. do the same step for the entire string. now the string will be like YXYBBB. left part is in the form of X and Y and right part is in the form of B. here the string is accepted. in case any of the symbol is left unchanged in left or right part, the string will not be accepted by the turing machine. for example after the conversion if the string is like "YXY1BBB". here the string will be rejected.

Transition diagram:

**************END**************PLS GIVE ME UPVOTE*******************************