World's most popular travel blog for travel bloggers.

How does an NFA use epsilon transitions?

, , 1 comment
Problem Detail: 

In the picture below, I'm trying to figure out what exactly this NFA is accepting.

enter image description here

What's confusing me is the $\epsilon$ jump at $q_0$.

  • If a $0$ is entered, does the system move to both $q_0$ and $q_1$ (the accept state)?

  • If a $1$ is entered, does the system move to both $q_1$ and $q_2$?

  • Does the system only move to $q_1$ (accept state), if no input is given (empty string)?

Asked By : user3472798

Answered By : H_DANILO

Every time you are in a state which has a $\epsilon$ transition, it means you automatically are in BOTH states, to simplify this to you:

If the string is $\epsilon$ then your automata ends both in $q_0$ and $q_1$

If your string is '0' it'll be again in $q_0$ and $q_1$

If your string is '1', it'll be only in $q_2$, because if you look from the point of $q_0$, you have a '1' transition to $q_2$, but you have also to look at case you're in $q_1$(if you were in $q_0$ you always were in $q_1$ also) then there is no '1' transition, so this alternative path just "dies".

Just by looking at these cases its easy to see that your automata accepts $\epsilon$, $0^*$, and going from $q_0$ to $q_1$, the only way to reach $q_2$ is $0^*11^*1$, so, this resumes your automata to $\epsilon$, $0^*$, $0^*11^*1$

Hope this helped you, if you have any further doubts, just ask!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37470

1 comment:

Let us know your responses and feedback