Question

4. (6 pts) Give an implementation-level description (describe how you would move the tape head, what you write on the tape, etc) of a Turing machine that decides the language (w w contains an even number of Is) over the alphabet (0,1)

Answer 1

4)Language : {w|w contains an even number of 1's }over the alphabet {0,1}
Implementation level description of Turing machine:
1)on state q0 if 0 comes in input then don't write anything just move head right, stay on q0 only
2)on state q0 if 1 comes in input then move to state q1, and don't write anything just move head right
3)on state q1 if 0 comes in input then don't write anything just move head right, stay on q1 only
4)on state q1 if 1 comes in input then move to state q0, and don't write anything just move head right
5)on state q0 if input is empty, then move to final state qf