Sunday 6 April 2014

Sipser 3.13 : A Turing machine with stay put instead of left

Solution: Because head of TM can't move left, it will behave like a finite automata. Motion of head in right is equivalent to consuming next symbol, and staying at a place is equivalent to consuming an epsilon symbol. When we hit blank symbol check if last state was accept state of TM, if yes then our finite automata accepts. Otherwise automata will reject the input string.

Not giving a formal definition of this TM and finite automata, because it is quite easy to visualise. Comment if doubtful. 

No comments:

Post a Comment