Search code examples
lambdaautomatadfanfa

Why Doesn't This NFA Accept Empty String?

We were given the definition of a NFA and told to construct an equivalent DFA using the conversion process. I had no issues, however, our professor kept telling us after the assignment that original NFA didn't accept the empty string. I'm a bit confused as to why it doesn't.

Here is the NFA:

δ(q0, a) = {q0, q1}
δ(q1, b) = {q1, q2}
δ(q2, a) = {q2}
δ(q0, λ) = {q2}

with initial state q0 and final state q2

Why is the empty string not accepted by the NFA or equivalent DFA? The last rule states that if encountering the lambda while in q0, to go to state q2, which is a final state. I was under the impression that if we accepted the empty string, the machine would both stay in state q0 and transition to q2 and since one of those is a final state, it would be accepted.

Solution

  • Assuming λ is an out-of-alphabet symbol appearing at the end of your input string - your automaton does accept the empty string.