-1
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ questions asking for mere implementation in some specific language are off topic here. $\endgroup$ – sashas Apr 29 '16 at 14:38
  • $\begingroup$ what topic should I add? but logically the epsilon transition I have to read it after reading the letter 'a' or before reading the letter 'b'? thank you very much $\endgroup$ – stella Apr 29 '16 at 14:51
  • $\begingroup$ You do the epsilon transition without having read any input $\endgroup$ – NaCl Apr 29 '16 at 18:22
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank's for your answer. My question is the transition δ(q1,ϵ)={q2} It must be made before the reading 'b' or after reading 'a'? Thank for all $\endgroup$ – stella May 2 '16 at 11:14
  • $\begingroup$ @stella. In your example, you can regard the two as identical. $\endgroup$ – Rick Decker May 2 '16 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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