1
$\begingroup$

Let's say we have a NFA as follows:

enter image description here

It has 3 states, q1 - q2 - q3 and can make transition from q1 to q2 on 0 or epsilon and from q2 to q3 on 1 or epsilon

My question is do we take epsilon transition before reading input or after reading input and after reading the input, if we reach a state where we have epsilon transition do we take that transition? if the latter part is correct then we can conclude that: we can take epsilon transition without consuming input at any point in time i.e before or after reading the input

Let's try processing some input string, so you can better understand my problem, input is "0"

Case 1: We split ( not literally ) the NFA before reading anything. So, since there's an epsilon transition from the start state q1, we start in q1 and q2 but there's also an epsilon transition from q2 to q3. Meaning that we are going to start in q1, q2, q3 ( consider 3 branches )

Then we read in our input which is 0:

  • from q1 the machine would visit q2, now before reading the next input we can take the epsilon arrow and split q2 into q2 and q3. Meaning the next symbol would be processed in these two states

Note: Above once we split before reading 0, then changed state and then again took the epsilon from the new state, is it legal to take epsilon from q2 since it would technically be "after" reading 0 but "before" reading the next input

  • from q2 the machine would go to a trap state and hence reject
  • from q3 the machine would go to a trap state and hence reject

Case 2: We split ( not literally ) the NFA after reading anything. In this case we start in just q1, read in the input 0 and move to state q2. And after reading the 0, we realise that we are on a state that has an epsilon transition to q3, so we split q2 to q2 and q3

There can be a 2b case: where instead of taking the epsilon from the new state, we first read in the input - take the epsilon transitions and then move on to the new resultant state, in this case after processing the current input, we would have q1, q2 and q3 as the final states

We can clearly see that in case 1 ( splitting before reading ) and case 2 ( spliting after reading ) we landed in the same set of final states, does this mean it does not matter if we split before or after?

This is important concept, because it's used in NFA to DFA, PDA and turing machine. Please help me!

Improve this question
$\endgroup$
4
  • $\begingroup$ I believe this is the same as your question $\endgroup$
    – Russel
    Dec 24, 2022 at 7:43
  • $\begingroup$ Not only that, but you asked two very similar questions 6 days ago: 1, 2. $\endgroup$
    – reinierpost
    Dec 24, 2022 at 11:29
  • $\begingroup$ Does this answer your question? How does an NFA use epsilon transitions? $\endgroup$
    – Nathaniel
    Dec 24, 2022 at 17:38
  • $\begingroup$ @Nathaniel I updated the question title - so it won't seem duplicate and no that linked question does not solve my question. Also, i deleted my past duplicate post $\endgroup$
    – Pratik Hadawale
    Dec 24, 2022 at 17:46

1 Answer 1

Reset to default
2
$\begingroup$

It happens both before and after.

Remember this is a non-deterministic automaton. Any time there is an epsilon transition, the automaton can either take that transition, or not take it -- it's a free choice. The automaton has the choice to do so before reading anything, and after, and in between reading every symbol. In fact, it can take as many epsilon transitions as it wants, at any time.

This is non-deterministic, so even though you have only a single input, there are many possible paths that might be taken through the automaton. The input is accepted if at least one of those paths is an accepting path.

See also How does an NFA use epsilon transitions?.

Also, your textbook undoubtedly has a formal mathematical definition. Try working through that definition, for the specific example you gave. You will discover what happens.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Inthelink: say, we are on q0 and the input is "1". My question is: could it be the case that, we choose to process"1" on state q0, meaning there's nothing left in input, and then take the empty transition ( because we can take emtpy transition without reading any symbol ), now we are on q1 which is the accept state and there's nothing left in in input hence we will accept "1". But I realised that it is illegal, what i said implies that after processing "1" we are still on q0 but according to transition function we should have moved to new state and there's no valid transition to stay on q0 $\endgroup$
    – Pratik Hadawale
    Dec 24, 2022 at 9:24
  • $\begingroup$ Yes, I am using Michael Sisper's book. I am only facing issues with epsilon definition and hence with the NFA to DFA conversion. $\endgroup$
    – Pratik Hadawale
    Dec 24, 2022 at 9:28
  • $\begingroup$ @PratikHadawale, I don't understand your question, as there is no q0 in your picture. You can take the epsilon transition at any point. You can also not take the epsilon transition. Again, the input is accepted if at least one of the possible paths ends in an accepting state. There might be some other paths that don't end in the accepting state; that is OK. If you are confused, I suggest you refer to the precise mathematical definition using the next-state transition relation (any good textbook should have one). $\endgroup$
    – D.W. ♦
    Dec 25, 2022 at 0:44
  • $\begingroup$ My question in the comment was regarding the diagram you linked in your answer, but yes i realised that the scenario i mentioned would be illegal because i was waiting to take the epsilon transition and changing it between the transition of current state into new state which made the new state accept next input but in the case of epsilon we are supposed to be processing the same input for epsilon reachable states. That's what i was trying to say in my last comment $\endgroup$
    – Pratik Hadawale
    Dec 25, 2022 at 4:39

Your Answer

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

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