4
$\begingroup$

Definitions

For any automaton $X$, let $L(X)$ denote the language recognized by $X$.

For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$.


Conversion Problem: NFA to smallest equivalent DFA

Input: A nondeterministic finite automaton $A$.

Output: A smallest possible deterministic finite automaton $B$ such that $L(A) = L(B)$.


We can solve this problem by converting from NFA to DFA using the powerset construction and then minimizing the resulting DFA. However, this seems inefficient.

In particular, it seems that this could run for $O(2^{sc(L)})$ time where $L = L(A)$ if the powerset construction gives us a suboptimal DFA.


Question: Is there an algorithm for this problem that runs in linear time in terms of the state complexity? By this, I mean that it runs in $O(n + sc(L))$ time where $n$ is the size of $A$ and $L = L(A)$? What about $poly(n + sc(L))$ time?

$\endgroup$
1
  • $\begingroup$ @D.W. This sounds like a pretty interesting approach. I have not thought about this. Thank you for sharing! $\endgroup$ Mar 22 at 21:59
4
$\begingroup$

See here: https://cs.stackexchange.com/questions/61113/does-a-given-e-nfa-accepts-all-the-strings "checking whether an NFA accepts all strings is PSPACE-complete".

In particular, if an NFA accepts all strings then its smallest equivalent DFA has size 1, and so a positive answer to your question would imply P=PSPACE.

$\endgroup$
6
  • $\begingroup$ Yes, you are totally right! I somehow didn't think of this. Thank you. :) $\endgroup$ Mar 23 at 0:03
  • $\begingroup$ I guess my follow-up question is, what if $A$ is known to be a minimum NFA? Maybe the powerset construction does produce a minimum DFA in this case? I am not quite sure. $\endgroup$ Mar 23 at 0:06
  • 1
    $\begingroup$ Maybe I will ask this as a separate question. What do you think? $\endgroup$ Mar 23 at 0:07
  • 1
    $\begingroup$ @Michael Wehar nice question. Well, my gut feeling tells me that your followup approach shares the same doom. On the positive side, your idea works in the case where the NFA in your hands is the reverse minimum DFA for L^R. (Why? Brzozowski's algorithm.) $\endgroup$ Mar 23 at 8:06
  • 1
    $\begingroup$ @HermannGruber Thank you very much for your comment! This is a very neat insight. :) $\endgroup$ Mar 23 at 8:31

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.