0
$\begingroup$

I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 )

Let's use this E-NFA as an example

enter image description here

My question is, do we transition along "epsilon transition" before reading any input or after reading any input?

assume input is "a"

Case 1: Before reading any input, in that case the machine would start in two states q1 and q3. Then it would read the input "a", q1 would transition to trap state and q3 would transition to q1 state, which is an accept state

enter image description here

Case 2: After reading any input, in that case the machine would start in state q1, it would read "a" and move to trap state + branch into 2 different states of epsilon transition i.e q1 and q3

I understand the fact that an "epsilon transition" just implies existence at both the states at the same time, but is that before reading the input or after reading the input?

enter image description here

Due to this, i am facing issues in the section "equivalence of DFAs and NFAs" in the same book.

Can someone explain me which is the correct case?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

In the case of the E-NFA shown in the first diagram, the epsilon transitions are taken before reading any input. This is because epsilon transitions do not consume any input and are taken automatically when the machine is in a state that has an epsilon transition.

Therefore, in the example you provided, the correct case would be Case 1, where the machine starts in states q1 and q3, takes the epsilon transitions to q1 and q3, respectively, and then reads the input "a". This results in the machine transitioning to the accept state q1 and the trap state, respectively.

On the other hand, in Case 2, the epsilon transitions are taken after reading the input "a", which is not how epsilon transitions work in an E-NFA.

The reason why the machine does not "split" into multiple states after reading "a" is because the machine is not literally splitting into multiple copies of itself. Instead, the machine is simply transitioning to another state based on the input it has received and the transitions defined in the machine.

In an E-NFA, the epsilon transition is a special type of transition that does not consume an input symbol. Instead, it allows the machine to transition to another state without reading an input symbol. This means that the machine can make multiple transitions without consuming any input, which can result in the machine being in multiple states simultaneously.

Improve this answer
$\endgroup$
9
  • $\begingroup$ That cleared my doubt, but have another small doubt. Let's say input is "ab" -> we start in states q1 and q3 -> then we read in "a" -> q1 end's up visiting the trap state whilst q3 ends up visting q1. Whilst we are in state q1 just before we read in the next input, do we split q1 again into q1 and q3 and then process "b"? or we don't split q1? $\endgroup$
    – Pratik Hadawale
    Commented Dec 17, 2022 at 16:59
  • $\begingroup$ In the case of the E-NFA shown in the first diagram, when the machine is in state q1 after reading the input "a", it will not split into multiple states. Instead, it will continue to process the next input "b" as a single state. This means that in the case of the input "ab", the machine will start in states q1 and q3, take the epsilon transitions to q1 and q3, respectively, and then read the input "a". This will result in the machine transitioning to the trap state and q1. The machine will then read the next input "b" and transition to the accept state and the trap state, respectively. $\endgroup$
    – user155509
    Commented Dec 17, 2022 at 17:04
  • $\begingroup$ So I have a question about your first statement about "q1 will not split into multiple states after reading 'a'". Your logic matches to that written in michael sipser's book. My question is why would it not split, q1 should split into 2 states after reading the input because q1 has epsilon arrow and then we would have 2 machines q1 and q3 processing "b". This is the only part that i am stuck on $\endgroup$
    – Pratik Hadawale
    Commented Dec 17, 2022 at 17:15
  • $\begingroup$ check the edit. $\endgroup$
    – user155509
    Commented Dec 17, 2022 at 17:19
  • $\begingroup$ I think the major obstacle i am facing is of "before" and "after" reading input, intuitively machine splitting into multiple copies of itself makes sense but when converting from NFA to DFA sipser splits machines "after" reading the input which makes sense too. Hence I am thinking from the stand point of if i am at q3 and read in "a" then i will visit q1 but at that point sipser calculates epsilon closure which then basically splits q1 to q1 and q3 and then it will read the next input. So, you see, the splitting does happen after reading "a". I am still confused feelfreetosuggestresources $\endgroup$
    – Pratik Hadawale
    Commented Dec 18, 2022 at 5:37

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.