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?

Improve this question
$\endgroup$
1
  • $\begingroup$ @D.W. This sounds like a pretty interesting approach. I have not thought about this. Thank you for sharing! $\endgroup$
    – Michael Wehar
    Commented Mar 22, 2021 at 21:59

1 Answer 1

Reset to default
6
$\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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yes, you are totally right! I somehow didn't think of this. Thank you. :) $\endgroup$
    – Michael Wehar
    Commented Mar 23, 2021 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$
    – Michael Wehar
    Commented Mar 23, 2021 at 0:06
  • 1
    $\begingroup$ Maybe I will ask this as a separate question. What do you think? $\endgroup$
    – Michael Wehar
    Commented Mar 23, 2021 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$
    – Hermann Gruber
    Commented Mar 23, 2021 at 8:06
  • 1
    $\begingroup$ @HermannGruber Thank you very much for your comment! This is a very neat insight. :) $\endgroup$
    – Michael Wehar
    Commented Mar 23, 2021 at 8:31

Your Answer

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

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