0
$\begingroup$

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: enter image description here

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 )

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Russel
    Commented Dec 25, 2022 at 7:32
  • $\begingroup$ @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 $\endgroup$ Commented Dec 25, 2022 at 7:37
  • $\begingroup$ @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? $\endgroup$ Commented Dec 25, 2022 at 7:45
  • $\begingroup$ 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. $\endgroup$
    – Russel
    Commented Dec 25, 2022 at 7:50
  • $\begingroup$ 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 ) $\endgroup$ Commented Dec 25, 2022 at 7:59

1 Answer 1

0
$\begingroup$

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.

Personally, I cannot remember seeing that comment of him in his text prior to your question. Possibly I missed or simply ignored that.

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.

$\endgroup$
10
  • $\begingroup$ Yes!! That's my doubt! I am still a bit confused but what i am gonna do is go ahead take a rest and try again after reading your answer with a clear mind. I'll come back in a few hours and either ask you a question or tell you that i succeeded in understanding $\endgroup$ Commented Dec 25, 2022 at 8:05
  • $\begingroup$ Now that you understood my doubt, let's go to my example in original post. You see how when we read in "1" when on state 1 and applied case 1 and case 2 ( as separate examples ) we ended up with different final states ( which was obvious ) but according to sipser, it shouldn't matter if we take epsilon closure before or after. But we didn't get same final states? I like to use case 2, because that's how i think intuitively that is "if i find a state with epsilon, i will create a list of options instantly and then process input on each new state". I intuitively fail to understand case 1 $\endgroup$ Commented Dec 25, 2022 at 8:55
  • $\begingroup$ can you help me understand how case 1 would produce the correct DFA $\endgroup$ Commented Dec 25, 2022 at 8:55
  • $\begingroup$ You do not have 1 as transition in your example, only a, b, and $\varepsilon$ $\endgroup$
    – Russel
    Commented Dec 25, 2022 at 9:05
  • $\begingroup$ Oh god my bad, i am sorry i meant when we read in "b". Also as i said in the original post imagine that we have a loop from state 3 to state 3 on "b" $\endgroup$ Commented Dec 25, 2022 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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