Except for isomorphisms, the minimal DFA of a regular language is unique. However, is it possible that an equivalent NFA has less states than the minimal DFA? If so, what is the reasoning behind this? Due to the conversion of an NFA to DFA (which produces $2^Q$ states) it seems to me that a NFA can indeed have less states than a minimal DFA, but I'm not quite sure of this. Thanks in advance.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ It seems to me that you've answered your own question, and any textbook (that proves the WC-running-time of the determinisation procedure) should contain a proof; see also here. So I don't quite know what you are asking. $\endgroup$– RaphaelCommented Jun 9, 2016 at 9:54
-
$\begingroup$ Community votes, please: duplicate? $\endgroup$– RaphaelCommented Jun 9, 2016 at 9:55
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
For every $n$ there is a language over $\{a,b\}$ which is accepted by an NFA having $n$ states, but its minimal DFA has $2^n$ states.
Unfortunately I don't remember the reference, but here is how to get almost this result. Let $L_n$ be the language of all words over $\{a_1,\ldots,a_n\}$ that don't contain all letters. Then $L_n$ can be accepted by an NFA with multiple initial states having $n$ states (or with a normal NFA with $n+1$ states), but its minimal DFA has $2^n$ states. Take it as an exercise to prove these statements (for the latter one, use Myhill-Nerode theory).
answered Jun 9, 2016 at 8:11
-
4$\begingroup$ An easier example with the constant size alphabet $\{ a , b \}$ is the family of languages $L_n$ of words where the $n$th letter from the back is a $b$. There's an NFA accepting it with $n+1$ states, but every DFA requires at least $2^n$ states - intuitively because you have to remember the last $n$ symbols read. $\endgroup$ Commented Jun 9, 2016 at 9:07
-
$\begingroup$
$\endgroup$
0
Number of states in DFA is greater or equal to number of states in NFA.
Now, minimal DFA is a kind of DFA. (Minimal DFA is a subset of DFA.) As NFA need not to show transition for all the input symbols it has lesser (or equal) number of states compare to DFA. Additionally, NFA has not dead states in transition diagram, unlike DFA.
So it may possible that minimal DFA and NFA has equal numbers of states but minimal DFA never has less number of states compare to minimal NFA.
That is why when we concern for minimum states in FA-Finite Automata, we go for NFA rather than DFA.
EXAMPLE:
Set of all strings start with 'a' over input symbols {a,b}.
DFA of above language has 3 states. NFA of above language has only 2 states.
