The Reduction of Two-Way Automata to One-Way Automata
John C. Shepherdson · IBM Journal of Research and Development · 1959
Rabin has proved1,2that two-way finite automata, which are allowed to move in both directions along their input tape, are equivalent to one-way automata as far as the classification of input tapes is concerned. Rabin's proof is rather complicated and consists in giving a method for the successive elimination of loops in the motion of the machine. The purposeo f this note is to give a short, direct proof of the result.