# 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.

-

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

-
Thanks by your answer. Only after reading what you say I realise that what is causing me havoc is understanding how to convert NDFAs to DFAs, I guess my initial intuition about $\epsilon$ transitions was not wrong, after all. How would one handle the conversion of the starting DFA state S13 for a and b, for instance? –  devoured elysium Feb 22 '11 at 7:06
There are no arrows from either $1$ or $3$ to $a$, so on input $A$, $\{1,3\}$ should go to $\varnothing$, which is a "dead" state (you get stuck there). The other case is handled in the text. –  Yuval Filmus Feb 22 '11 at 15:55
Ahhhh, finally got it! Thanks –  devoured elysium Feb 22 '11 at 22:38

An intuitive way of converting DFA to NDFA is shown in: