Question

7. (Exercise 8.5.1) Simulating a Turing machine. Here is a description of a Turing machine. The input alphabet is {a, b}. The state set is: {90, 91, 92, 93, 94, qacc, Cre; } The transition function is given in the table below: 90 9 42 93 94 a (qı, a, R) (qı, a, R) (q2, a, R) (qace, a, R) (qej, a, R) b (q2, b, R) (qı, b, R) (qı, b, R) (qrej, b, R) (qace, b, R) ** (queje *, R) (93, *, L) (q, *, L) (Grej*, R) (qrej *, R) (d) Describe in words the conditions under which the Turing machine accepts the input string.

Answer 1

The initial state is q0. If there is no input string on input tape, it gets into rejected state. Therefore, the string length should of at least 1.

If the first symbol is a, it goes to state q1, else if it is b, it goes to q2.

From q1, on both a and b, state will not be changed. But on completion of reading the string, it goes to state q3. q3 goes to accept state only if the last symbol is a, else the string is rejected. Therefore, if the string starts with a and end with a, it gets accepted.

Similarly from state q2, on completion of reading the string, it goes to q4. And then further, it gets accepted only if the last symbol is b, else rejected. Therefore, if the string starts with b, then it has to ended with b to get accepted.

By combining above both conclusions, we can conclude that the turing machine accepts the strings that starts and end with same symbol with length greater than 1.