# Can we efficiently convert from NFA to smallest equivalent DFA?

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?

• @D.W. This sounds like a pretty interesting approach. I have not thought about this. Thank you for sharing! – Michael Wehar Mar 22 at 21:59

• 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. – Michael Wehar Mar 23 at 0:06