2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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