# Number of states in minimal Non Deterministic Finite Automata

What will be the number of states in minimal NFA that can be designed to accept the language $L = \left \{ \epsilon \right \}$ having a non empty alphabet set?

My friends are saying that this can be done using $1$ state, make the only state start state & final state without any transitions.

But will not this NFA accept every string over the alphabet set?
Because for every input string we are already in accepting state.
So every string will be accepted.
My claim is that at least $2$ states will be required so that we can get away from that default accepting state (start state) on any non empty string and the minimal NFA will be exactly same as the minimal DFA accepting $L$.

Am I correct?

But will not this NFA accept every string over the alphabet set?

It will not accept any strings except the empty one. Since there are no transitions, the transition function $\delta(q_0,a) = \emptyset$ for all symbols $a$ of the input alphabet $\Sigma$, thus the extended transition function $\hat{\delta}(q_0,s) = \emptyset$ for all non-empty strings over $\Sigma$.

The set of accepting states $\{q_0\}$ and $\hat{\delta}(q_0,s)$ for all non-empty strings $s$ are disjoint, hence the NFA doesn't accept any non-empty strings.

As you already know this NFA accepts the empty string, and we just showed that it accepts only the empty string.

Remark: if it was a deterministic automaton you'd need 2 states to do the same thing. You could "cheat" and not show the 'dead state', but still it would be a 2 state DFA. With NFAs rules are a little bit different, since instead of states you use sets of states and having your NFA in no state at all (the empty set of states) is perfectly normal abstraction.

Your friend is right. FA whether deterministic or non accepts a string only if it can reach to final state while consuming all of string. Its NFA has no transition so you can not consume every non empty string to its end.

New contributor
m.farokhian is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.