3
$\begingroup$

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?

$\endgroup$
2
  • 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, 2014 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, 2014 at 18:37

1 Answer 1

5
$\begingroup$

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$).

$\endgroup$

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.