How does an NFA use epsilon transitions?

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

One thought on “How does an NFA use epsilon transitions?”

Leave a Reply