Understanding $\epsilon$ transitions in a finite state automaton I am trying to understand how $\epsilon$ transitions work.
From what I've read, when you "go" to a state S that has arrows pointing outwards with $\epsilon$'s in it, you automatically go to those states too. That is, in the following diagram, when you are about to give the first digit as input to this FSA, you must consider you are not just in state S1 but in S1 AND S2.

Is this correct? Following this reasoning, when converting this NDFA to a DFA, one should have as first state S13.
The $\delta (S13, b) = S123$, as


*

*if I consider the path starting at
S1, I will instantly go to S3

*if I consider the path starting at S3,
as the input is b, this path dies

*if I consider the path starting at S1 with a b as input,
I will get to S2.


I have a vague impression my understanding of $\epsilon$ transitions is wrong, as in some exercises I seem to get it done right, while in others wrong.
 A: $\epsilon$ transitions are optional - you can always take them, but you don't have to. That's why the starting state of the automaton in question is indeed $\{1,3\}$. On input $b$, you mention correctly that from state $1$ you go to $2$, whereas from state $3$ there is no arrow labeled $b$. Therefore the automaton goes to state $\{2\}$.
In general, there can be more than one output arrow having the same label: for example, if the automaton reads $a$ while in state $\{2\}$, it goes to state $\{2,3\}$.
Finally, $\epsilon$ transitions can be taken in chain. There's no such opportunity in the automaton in question, but supposing that there was one more state $4$ connected to $3$ via an $\epsilon$ transition, the starting state would be $\{1,3,4\}$ - you can take as many $\epsilon$ transitions as you want (but never have to take one).
A: An intuitive way of converting DFA to NDFA is shown in:
www.youtube.com/watch?v=taClnxU-nao
Learn to convert a nondeterministic finite state automaton (NFA) to a deterministic finite state ..
it is explained quite well
