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?
-
$\begingroup$ @D.W. This sounds like a pretty interesting approach. I have not thought about this. Thank you for sharing! $\endgroup$Michael Wehar– Michael Wehar2021年03月22日 21:59:09 +00:00Commented Mar 22, 2021 at 21:59
1 Answer 1
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.
-
$\begingroup$ Yes, you are totally right! I somehow didn't think of this. Thank you. :) $\endgroup$Michael Wehar– Michael Wehar2021年03月23日 00:03:59 +00:00Commented 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– Michael Wehar2021年03月23日 00:06:17 +00:00Commented Mar 23, 2021 at 0:06
-
1$\begingroup$ Maybe I will ask this as a separate question. What do you think? $\endgroup$Michael Wehar– Michael Wehar2021年03月23日 00:07:37 +00:00Commented 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– Hermann Gruber2021年03月23日 08:06:31 +00:00Commented 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– Michael Wehar2021年03月23日 08:31:34 +00:00Commented Mar 23, 2021 at 8:31
Explore related questions
See similar questions with these tags.