Cheap and Secure Web Hosting Provider : See Now

[Solved]: Number of states in minimal Non Deterministic Finite Automata

, , No Comments
Problem Detail: 

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?

Asked By : Romy

Answered By : Anton Trunov

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51066

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback