Let's say we have a NFA as follows:
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!