Two-way finite automaton

Summary

A two-way finite automaton is a finite automaton whose reading head can move both left and right on the input word. The input lies between two end markers. Despite this freedom, two-way deterministic automata accept exactly the regular languages, a result of Rabin and Scott and of Shepherdson. They can be much smaller than equivalent one-way deterministic finite automata. The question of how many states are needed to remove nondeterminism from two-way automata is a well-known open problem.