patternModerate
How does an NFA use epsilon transitions?
Viewed 0 times
transitionsnfaepsilondoeshowuse
Problem
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)?
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)?
Solution
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!
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!
Context
StackExchange Computer Science Q#37470, answer score: 14
Revisions (0)
No revisions yet.