Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 10M

Year: Dec 2016

The turing machine will have 0^m 10^n on its tape initially.

Therefore, it will start with the leftmost 0, go on scanning 0’s, and moving right keeping them as it is, till it get 1, it replaces this 1 by 0, and then again go on scanning 0’s and moving right keeping them as it is. When it gets a B(blank), it moves left, and replaces the rightmost 0 by B, and halts, thereby leaving finally m+n 0’s on the tape. Therefore, the moves of the Turing machine are:

Therefore, the Turing machine M=({q0, q1, q2, q3}, {0, 1}, {0, 1, B}, ????, q0, B, {q3}), where ???? is given above.

The transition diagram corresponding to the above table is shown in figure below