NFA with epsilon transition

Question

I need to understand the epsilon transition for NFA, for example I have an NFA with four states q0, q1, q2 and q3 the latter is an accepted state.

In particular the transition function is:

{q0, a}= {q1}
{q1, eps}= {q2}
{q2, b}= {q3}

I would implementing this behavior in java.

I have the string 'ab' and I have to see if it is accepted. I begin reading the character 'a' and arrival in the state q1, the next character is 'b' but the state q1 don't have transition for 'b'.

I have to run the epsilon transition as I read the character 'a'? I do not know how to do this in my application, can you help me?

Thanks

Answer 1

You seem to be misconstruing what an $\epsilon$-transition is. If we have, say, a transition rule $\delta(q_1,\epsilon)=\{q_2\}$ it means that the FA can switch from state $q_1$ to $q_2$ without reading any input. In your example, on input $ab$ the FA reads the $a$ and so passes from $q_0$ to $q_1$. It can then (in one reality) stay in $q_1$ or (in another), pass to state $q_2$. Then, on seeing the $b$, there is indeed no move from $q_1$ (in one reality) but there is a move (in another reality) to $q_3$, so since the NFA reaches a final state in one reality, the input $ab$ is accepted by the NFA.