A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A two-way finite automaton (2DFA) can move its read head left or right on the input (unlike standard DFA/NFA, restricted to rightward movement). Remarkably, 2DFA and 2NFA recognize exactly the regular languages—bidirectional movement alone doesn't increase expressiveness. However, 2DFAs may require exponentially more states than equivalent standard DFAs. This separation shows movement power differs from computational power; state complexity, not directionality, determines expressiveness.
A standard DFA reads its input tape strictly left to right — once a symbol is read, the head advances and never returns. A two-way finite automaton (2DFA) relaxes this restriction: at each step, the machine can move its read head one position to the left, one position to the right, or stay in place. The input is bracketed by special endmarkers (⊢ and ⊣) so the machine knows when it has reached either boundary. This means a 2DFA can re-read portions of the input as many times as it likes, scanning back and forth across the tape.
At first glance, this seems like it should be more powerful than a one-way DFA. After all, the machine can revisit earlier parts of the input, potentially gathering information that a one-way machine would have "forgotten." But the key constraint remains: the machine has only a finite number of states and no writable memory. Every time the head crosses a particular position, the machine's behavior depends only on its current state and the symbol at that position. Since there are finitely many states, the head's behavior at any position can only cycle through finitely many patterns. If the head visits the same position in the same state twice, it is in a loop and will never halt from that path.
The proof that 2DFAs recognize exactly the regular languages relies on a clever simulation. For each position in the input, you can characterize the 2DFA's behavior by a crossing sequence — the sequence of states the machine is in each time the head crosses between that position and its neighbor. Since the machine must halt (assuming it always halts), these crossing sequences are finite and bounded by the number of states. A one-way DFA can be constructed that tracks these crossing sequences as its own states. The resulting DFA may have exponentially many states (since crossing sequences can be up to exponential in length), but it is still finite and recognizes the same language.
This result is theoretically illuminating because it separates two intuitions about computational power. Allowing the read head to move freely feels like adding significant capability — and in the context of Turing machines, bidirectional access to a writable tape is essential for universal computation. But for finite automata, where there is no writable tape, bidirectional movement over a read-only input buys nothing in terms of language recognition. The lesson is precise: it is writable memory, not head movement, that separates the regular languages from more complex language classes. The 2DFA model helps clarify exactly what finite-state computation can and cannot do.