The Reduction of Two-Way Automata to One-Way Automata

Abstract

Rabin has proved <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1,2</sup> 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.