2
$\begingroup$

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.

enter image description here

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.

2 Answers 2

5

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

  • 0
    A$h$hhh, finally got it! Thanks2011-02-22
0

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

  • 2
    Since external links can sometimes be not active any longer, e.g. if the youtube-clip is removed, it is advisable to include some of the information from the video in your answer.2013-02-10