TestBook Test Series: Theory Of Computation - Finite Automata

Question

Only way NFA of 6 states can be reduced to DFA of one state if all remaining 5 states of NFA are useless (Unreachable etc) & THere are no Dead State. In any normal NFA without useless states, I think we need at least same no of states in DFA (Think about NFA which is just DFA with minimal states. !) I do not agree to 1 , as it means that all states other than start state in NFA was useless.

Comments

https://gateoverflow.in/34006/can-we-find-out-minimum-numbers-of-states-dfa-if-nfa-has-states

Answer 1

Consider an NFA for $\Sigma^*$, one which has $6$ states. Every state is an accepting state, and every state is reachable. The organisation of the transitions is irrelevant.

Now, there are 5 redundant (but reachable) states in this NFA.

The corresponding DFA will have just 1 state.

---

Regarding "Why would someone have an NFA with $5$ redundant states?", that is a different question, the answer to which doesn't affect the fact that there can be a DFA of $1$ state for an NFA of $6$ states.

Consider a person who is trying to convert a complicated regex into an NFA. It might not be obvious from the regex that it is reducible to $\Sigma^*$, and it might not be obvious from the NFA either. So, that makes a valid usecase for an NFA with $6$ states with majority of them being redundant.