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

Marks: 10M

Year: May 2016

The turing machine will have a^n b^m on its tape initially.

Therefore, it will start with the leftmost a, go on scanning a’s, and moving right keeping them as it is, till it get B(blank), it replaces this b by a, and then again go on scanning a’s and moving right keeping them as it is.

When it gets a B(blank), it moves left, and replaces the rightmost a by B, and halts. Therefore, the moves of the Turing machine are:

Therefore, the turing machine M=({q0, q1, q2, q3}, {a, b}, {a, b, B}, δ, q0, B, {q3}), where δ is given above.

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