In general, there exists NFAs of size n whose smallest equivalent DFA requires 2^n states.

But if we restrict ourselves to NFAs whose graph is eulerian, is it possible to turn any such NFA of size n into a DFA of size at most O(n) ?

If so, does it hold also for a NFAs whose graph is strongly connected ?

I would appreciate some counter example, proof or any reference to research papers dealing with this problem.

Many thanks, Luz


I don't think so.

Suppose you could. Then you can also do this:

  • Take any NFA $\mathcal A$ with alphabet $\Sigma$, states $Q$, transitions $\Delta$, initial states $I$ and final / acception states $F$.
  • Add transitions to make the graph eulerian in the following way. Take any enumeration of the transition $p_i\overset{a_i}{\to}q_i$. For each $i$, add a transition $q_i\overset{b_i}{\to}p_{i+1}$ where $b_i$ is a new letter (and the indices are modulo the number of transitions). Note that you add $|\Delta|$ letters and transitions so this transformation is linear.
  • Add transitions to make the graph strongly connected in the following way. Take any enumeration of the states $s_j$. Add a new letter $c$. For each $j$, add a transition $s_i\overset{c}{\to}s_{i+1}$. In other words, add a Hamiltonian cycle using only the new letter $c$. Note that this transformation adds $1$ letter and $|Q|$ transitions so it's linear.
  • Use your magic procedure to build a new deterministic automaton $\mathcal B'$ so that it recognizes the same language as $\mathcal A'$ (the modified automaton) and $|\mathcal B'|=O(|\mathcal A|)$.
  • Remove added letters ($b_i$ for each $i$ and $c$) and all transitions using them. Call the new automaton $\mathcal B$.

Since $\mathcal L (\mathcal A) = \mathcal L (\mathcal A')\cap \Sigma^* $ (because if you don't use the new letters, then you're taking a path that already existed), and similarly $\mathcal L (\mathcal B) = \mathcal L (\mathcal B')\cap \Sigma^* $, we have $\mathcal L (\mathcal A) = \mathcal L (\mathcal A')\cap \Sigma^*=\mathcal L (\mathcal B')\cap \Sigma^*=\mathcal L (\mathcal B)$ with $\mathcal B$ a DFA so that $|\mathcal B|=O(|\mathcal A|)$.

But this can not be because of the usual counterexample where the size of the corresponding DFA is of exponential size. To get an explicit counterexample, you can apply the procedure to that counterexample.

| cite | improve this answer | |
  • $\begingroup$ Thank you for your fast reply. So your point is that if it is possible to compute a linear size DFA from an eulerian (or strongly connected) NFA then it would be possible for any NFA (after adding transitions to the input NFA as you told and removing them from the resulting DFA). And this is impossible because we get a contradiction with the fact that there exist NFAs whose smallest equivalent DFA are exponential in size. Am I correct ? $\endgroup$ – Luz Jan 16 '17 at 13:24
  • $\begingroup$ @Luz: Yes :-) ${}{}$ $\endgroup$ – xavierm02 Jan 16 '17 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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