enter image description here

is the string epsilon(empty string) accepted by this NFA ?

  • 3
    $\begingroup$ This is immediate from any description of how NFAs work. If you don't understand how NFAs work, you should ask a question about the part you don't understand, rather than asking if a specific automaton accepts a specific string and then, presumably, trying to generalize the answer to all NFAs and all strings. $\endgroup$ – David Richerby May 31 '18 at 15:51
  • $\begingroup$ Your NFA uses lambda ($\lambda$) as the empty string rather than epsilon ($\epsilon$). Just saying. $\endgroup$ – Seankala Jun 1 '18 at 8:21
  • 1
    $\begingroup$ Possible duplicate of Why does this automation accept the empty string? $\endgroup$ – Seankala Jun 1 '18 at 8:31

I think this question could be much better worded if you asked

"If the starting state $q_0$ is also an accepting state, is the empty string $\lambda$ also accepted if it leads to a non-accepting state $q_2$?"

But regardless, the short answer is yes, as greatly explained by Mr. Draconis above.

One of the fundamental differences between DFA's and NFA's is the transition function $\delta$.

Remember that for DFA's, $$\delta : Q \times \Sigma \rightarrow Q$$

This means that the transition function takes an internal state and an input alphabet as arguments, and returns an internal state.

But for NFA's, $$\delta : Q \times (\Sigma \cup \{\lambda\}) \rightarrow \{Q\}$$

Notice that the differences are the curly brackets around the returned $Q$ and the union of the set containing the empty string $\lambda$ with $\Sigma$. This is the same as the DFA's $\delta$, but this time the function accepts the empty string as input and returns a set of internal states rather than a single state.

So as Mr. Draconis mentioned, the empty string is also accepted by the given NFA because it leads to $\{q_0, q_2\}$ with $q_0 \in F$.


The short answer is, yes.

To process an NFA, you start with an initial state set $Q_0 = \{q_0\}$. Then, for each step, you take one character of input, then form the next state set by following all possible transitions from all states in the previous set.

In this case, your initial state set is $\{q_0\}$, and after reading no input your state set is $\{q_0, q_2\}$. There is an accepting state in this state set, so the NFA accepts the empty string.


A DFA is defined as a tuple $⟨Σ,Q,δ,q_0,F⟩$. The state $q_0$ is your initial state, and also an element in your set of accepting states $F$. If you process the empty string, you will make no transition, and you will still be standing in an accepting state. Therefore the DFA accepts the empty word.

  • 1
    $\begingroup$ But this isn't a DFA. $\endgroup$ – David Richerby May 31 '18 at 15:52
  • $\begingroup$ @david you are of course correct, bad information from me, even though The answer remains $\endgroup$ – JohEker May 31 '18 at 20:40

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.