11
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

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.

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

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ @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)? $\endgroup$
    – D.W.
    Dec 6, 2013 at 1:20
  • $\begingroup$ You're right. I missed an $\varepsilon$ in the concatenation. $\endgroup$
    – Mateus de Oliveira Oliveira
    Dec 6, 2013 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.