I am reading "Introduction to the Theory of Computation" (2ed) by Michael Sipser. In Example 1.35, it says the NFA accepts $\epsilon$, which I understand, since the state can stay at $q_1$ upon input of $\epsilon$: enter image description here

But in Example 1.38, it shows to be an empty set for $q_1$, $q_3$, and $q_4$:

enter image description here

I thought it should be $\delta(q_1, \epsilon)=\{q_1\}$ at least, for instance. I always assume there is an "implicit self-$\epsilon$-transition" at every state, but why it is $\emptyset$ now? I also noticed the lack of a "self-$\epsilon$-transition" in the proof of Theorem 1.45 (no staying at $q_0$ upon the input of $\epsilon$). Have I missed something important?


1 Answer 1


I think you're making a good point. It's just that since an $\epsilon$-transition from a state to itself must always be there in some sense (we can read nothing from the input stream and stay in the same state) it's more economical to make the convention that we don't consider such "transitions" to be transitions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.