<p>See here:
<a href="https://cs.stackexchange.com/questions/61113/does-a-given-e-nfa-accepts-all-the-strings">https://cs.stackexchange.com/questions/61113/does-a-given-e-nfa-accepts-all-the-strings</a>
&quot;checking whether an NFA accepts all strings is PSPACE-complete&quot;.</p>
<p>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.</p>

CC BY-SA 4.0
2021-03-23T00:03:59.593Z
Yes, you are totally right!  I somehow didn't think of this.  Thank you.  :)
Michael Wehar
CC BY-SA 4.0
2021-03-23T00:06:17.273Z
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
CC BY-SA 4.0
2021-03-23T00:07:37.487Z
Maybe I will ask this as a separate question.  What do you think?
Michael Wehar
CC BY-SA 4.0
2021-03-23T07:55:39.723Z
Sure, great question. I’ll need to think about it...
Aryeh
CC BY-SA 4.0
2021-03-23T08:06:31.277Z
@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.)
Hermann Gruber
CC BY-SA 4.0
2021-03-23T08:31:34.387Z
@HermannGruber Thank you very much for your comment!  This is a very neat insight.  :)
Michael Wehar
CC BY-SA 4.0
2021-03-22T22:07:46.553Z
2021-03-22T22:07:46.553Z
Aryeh
<p><strong>Definitions</strong></p>
<p>For any automaton <span class="math-container">$X$</span>, let <span class="math-container">$L(X)$</span> denote the language recognized by <span class="math-container">$X$</span>.</p>
<p>For any language <span class="math-container">$L$</span>, let <span class="math-container">$sc(L)$</span> denote the number of states in the smallest DFA <span class="math-container">$X$</span> such that <span class="math-container">$L = L(X)$</span>.</p>
<hr />
<p><strong>Conversion Problem: NFA to smallest equivalent DFA</strong></p>
<p>Input: A nondeterministic finite automaton <span class="math-container">$A$</span>.</p>
<p>Output: A smallest possible deterministic finite automaton <span class="math-container">$B$</span> such that <span class="math-container">$L(A) = L(B)$</span>.</p>
<hr />
<p>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.</p>
<p>In particular, it seems that this could run for <span class="math-container">$O(2^{sc(L)})$</span> time where <span class="math-container">$L = L(A)$</span> if the powerset construction gives us a suboptimal DFA.</p>
<hr />
<p><strong>Question:</strong> 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 <span class="math-container">$O(n + sc(L))$</span> time where <span class="math-container">$n$</span> is the size of <span class="math-container">$A$</span> and <span class="math-container">$L = L(A)$</span>?  What about <span class="math-container">$poly(n + sc(L))$</span> time?</p>

CC BY-SA 4.0
2021-03-22T21:59:09.757Z
@D.W. This sounds like a pretty interesting approach.  I have not thought about this.  Thank you for sharing!
Michael Wehar
<cc.complexity-theory><ds.algorithms><fl.formal-languages><automata-theory><minimization>
Can we efficiently convert from NFA to smallest equivalent DFA?
Michael Wehar
# Can we efficiently convert from NFA to smallest equivalent DFA?

(Asked by: username_0 on 2021-03-22)

**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?

**Tags:** cc.complexity-theory, ds.algorithms, fl.formal-languages, automata-theory, minimization
> **Comments:**
> **username_0**: @D.W. This sounds like a pretty interesting approach.  I have not thought about this.  Thank you for sharing!  

---

## 1 answers

### Answer by username_1 on 2021-03-22. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: Yes, you are totally right!  I somehow didn't think of this.  Thank you.  :)  
> **username_0**: 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.  
> **username_0**: Maybe I will ask this as a separate question.  What do you think?  
> **username_1**: Sure, great question. I’ll need to think about it...  
> **username_2**: @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.)  
> **username_0**: @HermannGruber Thank you very much for your comment!  This is a very neat insight.  :)  

---

