Given an NFA that accepts the regular language L, will its equivalent DFA which accepts the same language L always have unreachable states. If it does, why?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
No, there aren't always unreachable states. Consider the NFA with one state, $q$, and no transitions. (It accepts the language $\{\epsilon\}$ if $q$ is accepting, and accepts $\emptyset$, otherwise.)
If you determinize this automaton, you end up with a two-state DFA with a transition from the start state $\{q\}$ to the other state, $\emptyset$, so both states are reachable.
answered Jun 25, 2019 at 14:38
$\begingroup$
$\endgroup$
The powerset construction shows that for every NFA with $n$ states there is an equivalent DFA with $2^n$ states. Every example in which this is tight – that is, the minimal DFA has $2^n$ states – is a counterexample to your claim. You can find such an example, for arbitrary $n$ and over a binary alphabet, in this answer.
answered Jun 25, 2019 at 23:18