Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
1  
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. –  Julian Kuelshammer Feb 10 '13 at 15:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.