I was looking through some papers online on the equivalence of 2-way DFA and 1-way DFA and I couldn't find a simpler explanation on why 2DFAs are no more powerful than ordinary DFA. I wanted to write a simpler explanation of why this is the case so anyone who is new to the topic could understand without much trouble.
It would be helpful if someone could point me to some resources on the topic that are simple to understand
The intuitive explanation why two-way DFA and NFA are not more powerful than DFA is that all these variations have finite memory. A non-deterministic or two-way automaton has more memory per state than a basic DFA, but as long as there's only a finite amount of memory, a fancy automaton is no more powerful than a DFA with perhaps more states.
A two-way DFA can retrace its steps, but it has no memory of it. When the automaton is at a certain position in the input, the only thing that encodes how it got there is the state, and it's taken from a finite state. So there's no way for the automaton to behave differently based on the position or the movement history.
Let's look a bit more precisely at how a DFA can simulate a two-way DFA, i.e. how the memory of a two-way DFA can be represented in a DFA. The states of a DFA represent all that is known about the input after reading a prefix of the input. Reading a word $uv$ can be decomposed into 1. reading $u$ from the initial state and 2. reading $v$ from the state reached after reading $u$. The information about the partial input $u$ that the DFA remembers is simply the state reached after reading $u$.
Before studying this for a 2DFA, let's do it for an NFA. An NFA reads its input sequentially from left to right like a DFA, but at each stage, any set of states of the NFA may potentially be reached. Thus, the information about a partial input that the NFA remembers is the set of reached states. There are at most $2^n$ sets of states in a world with $n$ states, and therefore an NFA with $n$ states can be simulated by a DFA with at most $2^n$ states. This is in fact a tight bound.
In an NFA with $n$ states, the amount of information in the system is encoded in the set of reachable states. Each new input character triggers a transition from a set of states to a new set of states. Since there are $2^n$ sets of states, an NFA can be converted to a DFA that recognizes the same language and that has at most $2^n$ states.
Let's now turn to a two-way DFA with $n$ states. After reading some input $u$, the 2DFA remembers what state it has reached. In addition, after reading more input, the 2DFA may backtrack into $u$ and, perhaps, come back out. We want to abstract $u$ away completely, so we need to count all the ways to backtrack into $u$ and come back. If the 2DFA ever backtracks into $u$, it may do so from any state $q$ amongst its $n$ states. When it comes back out, it will have reached some other state $q'$ (perhaps the same, it doesn't matter). The state $q'$ depends on $q$ and $u$, but it doesn't depend on what comes after $u$, since by definition $q'$ is the state reached after working through $u$ in a deterministic automaton. Therefore each prefix $u$ defines a mapping from $q$ to $q'$. The information stored in the 2DFA after processing $u$ consists of the initial exit state (which state is reached immediately after reaching the end of $u$) and the mapping from reentry state to subsequent exit state. (I don't claim that all mappings are possible.) There are $n$ initial exit states, and $n^n$ mappings of state to state. Thus the information in a 2DFA after processing some prefix consists of at most $n \times n^n$ different possibilities. This means that a 2DFA can be simulated by a DFA with at most $n \times n^n = n^{n+1}$ states.
The tight bound is in fact $n \times (n^n - (n-1)^n)$. I don't have an intuition for the second term.
