# Conversion of epsilon NFA to DFA, handling epsilon transitions

I am reading Michael Sipser's "Introduction to theory of computation" 3rd edition, page 55 - 56, the topic "equivalence of DFAs and NFAs"

1. Case 0: Michael Sipser asks us to handle the transition function of "non epsilon NFAs" as follows: δ'( R, a ) = $$\bigcup_{_{r \epsilon R}}^{}δ(r, a)$$

2. Case 1: Michael Sipser, then, introduces us to the transition function of "epsilon NFAs" as follows: $$δ'( R, a ) = \{ q \,\,\epsilon \,\, Q | q \,\,\epsilon \,\,E(δ( r, a )) \,\,for \,\, some \,\, r \,\,\epsilon \,\, R\}$$

3. Case 2: This is how I like to think intuitevly, that is taking epsilon arrows as soon as we see one, $$δ'( R, a ) = \{ q \,\,\epsilon \,\, Q | q \,\,\epsilon \,\,δ( E(r), a )) \,\,for \,\, some \,\, r \,\,\epsilon \,\, R\}$$

Look at the position of Transition function and epsilon function! in case 2 and 3

Where function E() implies "Epsilon Closure" of a state. But, here if you realize Michael Sipser asks us to take epsilon closure after reading the input + transitioning to a new state. Basically it's like saying, if we are on a state then we don't have to take the epsilon transition immediately and we need to first process the input - move to a new state - and then take the epsilon transition from the new state ( if it exists ). He also modifies the start state of the resultant DFA to be E(start state)

Later he implies that taking epsilon before or after ( after as i mentioned above ) reading is the same! Basically case 2 and 3, mentioned above should produce same states but that isn't the case

Let's look at an example of NFA:

NOTE: Also, imagine we had a loop from state 3 to state 3 on input "b"

Now, DFA would have $$2^{number of states}n$$, one of the states of DFA would be "1". If we consider the transition function for state 1 in DFA on input "b", we would end up with following two cases:

1. Using case 1 transition function, from above, we would end up with { 2 }
2. Using case 2 transition function, from above, we would end up with { 2, 3 }

Where as, he implies case 1 and case 2 should produce same results

So, where am i wrong? I fail to understand how case 1 would be same as case 2

EDIT: Removed an accidental apostrophe EDIT 2: Tweaked example a little, by adding a loop ( did not re-draw the diagram )

• Where did you get case 2? I don't seem to find that in the text. And also please check that in case 2 it must be $q \in E(\delta(r, a))$. In the proof shown by Sipser, he first presented the conversion of an NFA without $\varepsilon$ transition. On the later part he showed how to modify the conversion if the NFA has $\varepsilon$ transition. So if your NFA has no $\varepsilon$ transition, use the first conversion, otherwise use the modified. Commented Dec 25, 2022 at 7:32
• @Russel Case 2 does not exist in his text, but if you look on page 57, he mentions on 2nd to last paragram that "An alternative procedure based on following the e arrows before reading each input symbol works equally well". So, i myself created that method. But the point is, if he said that case 1 and case 2 ( mentioned here ) equally well, does that imply both of the cases should produce same output for a particular state? or does he mean that we will end up with same DFA irrespective of case 1 or case 2 but just with different labellings Commented Dec 25, 2022 at 7:37
• @Russel Also, in case 2 ~ you suggested that it should be q∈E(δ(r,a)) but wouldn't that be the same as first case. When we say we take epsilon transitions before reading the symbol. It means we calculate epsilon closure of 'r' first meaning we are at all the states connected by epsilon and then we process the input. Right? Commented Dec 25, 2022 at 7:45
• The correction I mentioned is based on the book itself, you can verify that. It will not be the same as the first case if you apply that to an NFA with $\varepsilon$ transition, as you would first compute all new states from some state after reading an input using the transition for NFA without $\varepsilon$, then you compute the epsilon closure for each new state. Commented Dec 25, 2022 at 7:50
• I am sorry but can you answer this for me: If you look at the page 57, second to last paragraph, he says "an alternative procedure based on following the e arrows before reading each input symbol works equally well, but that method is not illustrated in this example". Would you like to show me how the transition function were to look like if we followed e arrows before reading input ( That's why my case 2 transition function looks like that, you do epsilon closure before reading the input ) Commented Dec 25, 2022 at 7:59

I think your confusion is with Sipser's comment that you can convert an NFA with $$\varepsilon$$ to a DFA by either reading an input first then you compute the epsilon closure or by computing the epsilon closure first before reading an input. To clarify that, yes you can do both. However, Sipser might have not mentioned that if you compute the epsilon closure before reading an input, there is no need to modify the start state. However, you must compute the epsilon closure after reading the entire input. You can verify these using the NFA you gave as an example.
Note: Your case 2 is not enough so to capture Sipser's comment that $$\varepsilon$$ can be processed before reading an input since as I have mentioned, there must be an epsilon closure after reading the entire input. This I think will be a little cumbersome to express since Sipser's transition function is defined only for reading a single input and not an entire word/string.
• You do not have 1 as transition in your example, only a, b, and $\varepsilon$ Commented Dec 25, 2022 at 9:05