Rabin has proved 1,2 that 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.
No takes yet. Share an insight, caveat, or question.
J. C. Shepherdson (1959) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: