In the picture below, I'm trying to figure out what exactly this NFA is accepting.
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
thank you
ReplyDelete