A computer scientist claims their 2DFA can recognize the language {aⁿbⁿ | n ≥ 1} — all strings of n a's followed by n b's — because it can reread the input to count. Is this claim correct?
AYes — by scanning back and forth, the 2DFA can match each 'a' with a 'b' and accept the correct strings
BNo — {aⁿbⁿ} is a context-free but non-regular language, which no finite automaton can recognize regardless of head movement
CYes — 2DFAs are strictly more powerful than DFAs, so they can recognize some context-free languages
DNo — 2DFAs cannot scan backwards; only 2NFAs can move the head in both directions
{aⁿbⁿ} requires counting, which requires unbounded memory. A 2DFA can re-examine its input but has only finitely many states — it cannot count to an arbitrarily large n. No matter how many times it rescans the string, it must eventually enter a repeated state in the same head position, creating a loop. The expressive power of finite automata is determined by memory (states), not head movement. 2DFAs recognize exactly the regular languages, just like standard DFAs.
Question 2 Multiple Choice
A 2DFA with 8 states recognizes a certain regular language. What can be said about the minimum number of states a standard 1DFA needs to recognize the same language?
AExactly 8 states — equivalent models always require the same number of states
BAt most 8 states — standard DFAs are always at least as succinct as 2DFAs
CPotentially exponentially more than 8 states — converting a 2DFA to a 1DFA can cause an exponential state blowup
DExactly 2⁸ = 256 states — the crossing-sequence construction always produces 2ⁿ states
The simulation of a 2DFA by a 1DFA works via crossing sequences — the sequence of states in which the head crosses each input position. These sequences can be up to exponential in length, so the resulting 1DFA may have exponentially many states. This is the key complexity separation: 2DFAs and 1DFAs recognize the same languages (equal expressive power) but 2DFAs can be exponentially more succinct. More states doesn't mean more computational power here — it just means the 1DFA needs more 'memory encoded in structure' to simulate the 2DFA's back-and-forth traversal.
Question 3 True / False
A two-way finite automaton is strictly more powerful than a standard DFA because it can re-read its input.
TTrue
FFalse
Answer: False
2DFAs and standard DFAs recognize exactly the same class of languages — the regular languages. Bidirectional head movement does not increase expressive power. The reason is that a 2DFA still has only finitely many states and no writable memory. Every behavior the head can exhibit at any tape position is captured by finitely many crossing sequences, and a 1DFA can be constructed that tracks these sequences. The key insight is that computational power comes from writable memory (as in Turing machines), not from head movement over a read-only tape.
Question 4 True / False
The reason 2DFAs cannot recognize non-regular languages has nothing to do with head movement direction — it is entirely due to the lack of writable memory.
TTrue
FFalse
Answer: True
This is the precise lesson of the 2DFA equivalence result. Compare: a Turing machine with bidirectional access to a *writable* tape achieves universal computation. A 2DFA with bidirectional access to a *read-only* tape is still stuck in the regular languages. The writable tape is what enables counting, matching, and other operations that escape regularity. Head movement direction alone, over a fixed read-only input, cannot substitute for memory. The 2DFA result cleanly isolates which feature — writable storage — is actually responsible for increased expressiveness.
Question 5 Short Answer
Explain why a two-way finite automaton cannot recognize a language like {aⁿbⁿ}, even though it can scan back and forth over its input as many times as it likes.
Think about your answer, then reveal below.
Model answer: A 2DFA has only finitely many states and no writable storage. Recognizing {aⁿbⁿ} requires counting to an arbitrary n, which requires memory proportional to n. No matter how many times the 2DFA rescans, its behavior at any tape position depends only on its current state. Since there are finitely many states, the machine must eventually revisit the same state at the same position — entering a loop. The finite state space is the hard ceiling, and bidirectional movement cannot raise it.
The core insight is that rescanning the input is not the same as remembering. A 2DFA can gather information by moving back and forth, but everything it 'knows' must fit in its state register, which has fixed size. To match the n-th 'a' with the n-th 'b' for arbitrarily large n requires a counter that grows without bound — and no finite state machine (one-way or two-way) has that.