World's most popular travel blog for travel bloggers.

Why does this automation accept the empty string?

, , No Comments
Problem Detail: 

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?

Asked By : tanmoy

Answered By : jmite

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.

Best Answer from StackOverflow

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

0 comments:

Post a Comment

Let us know your responses and feedback