-2
$\begingroup$

I am new to Automata Theory. I am studying the book thoroughly and understanding it well. I have got a confusion regarding NFA. Why does this automaton accept the empty string λ?

NFA

What I think is that: implicitly δ(q,λ)=q for all states q. But here also explicitly defined δ(q0,λ)=q2. As there is a walk to the final state using δ(q0,λ)=q0, so δ(q0,λ)=q2 will not be followed. Am I correct?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Are you familiar with what it means for an automaton to accept a string? $\endgroup$ – David Richerby Jan 31 '14 at 8:59
  • $\begingroup$ @DavidRicherby: YES $\endgroup$ – tanmoy Jan 31 '14 at 17:24
  • 1
    $\begingroup$ I suggest you check the definition again. A nondeterministic automaton accepts a string if, and only if, there is a path from the starting state to some accepting state where each transition is labelled either with $\lambda$ or the next character from the input. In particular, this means that an automaton accepts the empty word if, and only if, the initial state is accepting or there is some sequence of $\lambda$-transitions from the initial state to some accepting state. $\endgroup$ – David Richerby Feb 1 '14 at 0:12
  • $\begingroup$ @DavidRicherby: thanks for the clarification. $\endgroup$ – tanmoy Feb 2 '14 at 13:34
  • 3
    $\begingroup$ Possible duplicate of is an empty string accepted by this NFA accepters $\endgroup$ – Seankala Jun 1 '18 at 8:30
7
$\begingroup$

An automaton accepts $\lambda$, the empty string, if and only if the starting state is a final state, or there is some final state in the empty-string-closure of the starting state (in the non-deterministic case).

You don't need to walk from the start state, since it is already final. The fact that you have the option to doesn't mean you are obligated to.

| cite | improve 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.