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

<p>$$\{a,b\}^* \cdot b \cdot \{a,b\}^n \cdot c$$</p>

<p>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.</p>

<p>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.</p>

<p>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).</p>

CC BY-SA 3.0
2013-12-06T01:20:34.873Z
@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.
CC BY-SA 3.0
2013-12-06T15:44:06.250Z
You're right. I missed an $\varepsilon$ in the concatenation.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2013-12-05T19:23:23.967Z
2013-12-05T19:23:23.967Z
DCTLib
<p>The tight bound is $ n(n^n -(n-1)^n) $, which was given in <a href="http://link.springer.com/chapter/10.1007/11549345_47" rel="noreferrer">Removing Bidirectionality from Nondeterministic Finite Automata</a> by Christos Kapoutsis (2005).</p>

<p>I am also putting a figure from this paper giving a clear picture:
<img src="https://i.sstatic.net/X8nJU.png" alt=""></p>

<p>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: <a href="http://www.informatik.uni-trier.de/~ley/pers/hy/k/Kapoutsis:Christos_A=.html" rel="noreferrer">dblp: Christos A. Kapoutsis</a>.</p>

CC BY-SA 3.0
2013-12-06T11:19:33.010Z
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
CC BY-SA 3.0
2013-12-06T09:38:14.017Z
2013-12-06T09:38:14.017Z
Abuzer Yakaryilmaz
<blockquote>
  <p>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?</p>
</blockquote>

<p>A <a href="https://en.wikipedia.org/wiki/Two-way_deterministic_finite_automaton">two-way DFA (2DFA)</a> 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.</p>

<p>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.</p>

<p>I am asking whether any (families of) 2DFAs are known that <em>require</em> 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?</p>

<ul>
<li>Moshe Y. Vardi, <em>A Note on the Reduction of Two-Way Automata to One-Way Automata</em>, IPL <strong>30</strong> 261–264, 1989.  doi:<a href="http://dx.doi.org/10.1016/0020-0190%2889%2990205-6">10.1016/0020-0190(89)90205-6</a> (<a href="http://www.cs.rice.edu/~vardi/papers/ipl88rj.ps.gz">preprint</a>)</li>
</ul>

<automata-theory><lower-bounds>
2DFA that requires many states in equivalent DFA?
András Salamon
# 2DFA that requires many states in equivalent DFA?

(Asked by: username_0 on 2013-12-05)

> 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)](https://en.wikipedia.org/wiki/Two-way_deterministic_finite_automaton) 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?

* Moshe Y. Vardi, *A Note on the Reduction of Two-Way Automata to One-Way Automata*, IPL **30** 261–264, 1989. doi:[10.1016/0020-0190(89)90205-6](http://dx.doi.org/10.1016/0020-0190%2889%2990205-6) ([preprint](http://www.cs.rice.edu/~vardi/papers/ipl88rj.ps.gz))

**Tags:** automata-theory, lower-bounds

---

## 2 answers

### Answer by username_4 on 2013-12-06. Score: 9 | Accepted answer

The tight bound is $ n(n^n -(n-1)^n) $, which was given in [Removing Bidirectionality from Nondeterministic Finite Automata](http://link.springer.com/chapter/10.1007/11549345_47) by Christos Kapoutsis (2005).

I am also putting a figure from this paper giving a clear picture:
![](https://i.sstatic.net/X8nJU.png)

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](http://www.informatik.uni-trier.de/~ley/pers/hy/k/Kapoutsis:Christos_A=.html).

> **Comments:**
> **username_0**: Perfect, thanks!  In comparison with the $2^{O(n^2)}$ upper bound of Vardi, this shows a bound of $2^{\Theta(n \log n)}$.  

---

### Answer by username_1 on 2013-12-05. Score: 5

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).

> **Comments:**
> **username_2**: @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)?  
> **username_3**: You're right. I missed an $\varepsilon$ in the concatenation.  

---

