# 2DFA that requires many states in equivalent DFA?

Is there a 2DFA with $n$ states (where $n$ is nontrivial, say at least 4) that requires at least $2^n$ states to simulate using any DFA?

A two-way DFA (2DFA) is a deterministic finite-state automaton that is allowed to move back and forth on its read-only input tape, unlike finite-state automata that may only move the input head in one direction.

It is well-known that 2DFAs recognize precisely the same class of languages as DFAs, in other words the regular languages. Less well-understood is the question of how efficient the simulation is. The original constructions from the late 1950s by Rabin/Scott and Shepherdson used a notion of crossing sequences and are quite hard to analyse. Moshe Vardi published another construction that shows an upper bound of $2^{O(n^2)}$ states, but this bound may have some slack.

I am asking whether any (families of) 2DFAs are known that require many states in any DFA simulating them, even after Myhill-Nerode minimization of the DFA. Moreover, would there be any interesting consequences of knowing such 2DFAs?

The tight bound is $n(n^n -(n-1)^n)$, which was given in Removing Bidirectionality from Nondeterministic Finite Automata by Christos Kapoutsis (2005).

I am also putting a figure from this paper giving a clear picture: To get more, I think this paper is a good starting point. To check the related recent developments, I can also recommend to check the papers listed here: dblp: Christos A. Kapoutsis.

• Perfect, thanks! In comparison with the $2^{O(n^2)}$ upper bound of Vardi, this shows a bound of $2^{\Theta(n \log n)}$. – András Salamon Dec 6 '13 at 11:19

Consider the following language for an alphabet $\Sigma = \{a,b,c\}$:

$$\{a,b\}^* \cdot b \cdot \{a,b\}^n \cdot c$$

In words, this is the set of words that contain precisely one $c$ and for which $n+1$ characters before the $c$, a letter $b$ can be found.

The language can be seen to be accepted by a 2-way DFA of size $n+c$ for some constant $c$, but we need more than $2^n$ states in the DFA in order to keep track of the last $n$ characters from the prefix input stream $\{a,b\}$. The 2-DFA would start by cycling in the initial state and would reverse direction upon reading a $c$. Then, it waits $n$ steps (by following a chain of $n$ transitions) and finally checks that a $b$ is read.

While this is not precisely a formal proof, it should be no problem to make one from it. Note that the dual language can be shown to need more than $2^n$ states for every NFA, whereas the 2-DFA stays to be of size $n+c$ (possibly +1).

• @MateusdeOliveiraOliveira, I don't think so. How do you know when to move from $(a+b)^*$ to $b \cdot (a+b)^n \cdot c$? How would the DFA tell where the transition should be (without being able to look ahead $n$ symbols)? – D.W. Dec 6 '13 at 1:20
• You're right. I missed an $\varepsilon$ in the concatenation. – Mateus de Oliveira Oliveira Dec 6 '13 at 15:44