patternMinor
What does an input string of epsilon mean?
Viewed 0 times
whatepsilonmeaninputdoesstring
Problem
I am currently reading Introduction to the Theory of Computation (Sipser), and after introducing epsilon labeled transition arrows, the book shows the following NFA:
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?
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?
Solution
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$).
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$).
Context
StackExchange Computer Science Q#22227, answer score: 5
Revisions (0)
No revisions yet.