I am currently reading Introduction to the Theory of Computation (Sipser), and after introducing epsilon labeled transition arrows, the book shows the following NFA:

enter image description here

I was following it until I read the following :

Practice with it to satisfy yourself that it accepts the strings ϵ, a, baba and baa...

What does an input string of ϵ mean?

  • 4
    $\begingroup$ It's the empty string, so a string of length zero. I'm sure the text explains it, just read it carefully. $\endgroup$
    – Juho
    Mar 3 '14 at 18:19
  • $\begingroup$ @Juho - You're right - it is explained... Just a little hidden away, took me quite a while to find it - thanks $\endgroup$
    – jcw
    Mar 3 '14 at 18:37

In the context of NFAs, $\epsilon$ marks state transitions that do not consume input. These transitions thus express the non-determinism of the automaton.

When discussing the acceptance of $\epsilon$, the symbol marks the empty string (this is equivalent to the condition that an accepting state is reachable by a sequence of $\epsilon$-transitions from the start state). to avoid confusion, some authors use a different symbol for the empty string (often $\lambda$).


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.