# How does an NFA use epsilon transitions?

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)?

• Go back to the definitions: an NFA accepts a word if any computation on it accepts. NFAs are not, per se, "algorithms" in the sense DFA are.
– Raphael
Jan 22, 2015 at 12:23

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!

• "it means you automatically are in BOTH states" -- I don't think that that is a helpful intuition, i.e. it represents non-determinism in a wrong way.
– Raphael
Jan 22, 2015 at 12:22
• Why does it represent it wrong? Well, by the definition of delta on non-determinism, you get a set of state instead of only 1 correctly? This can means only that you are in both states. Jan 22, 2015 at 14:57
• It promotes the idea that non-deterministic machines "try all solutions in parallel". That is not what happens, algorithmically speaking. Nondeterminism is a descriptive formalism, not an algorithmic technique.
– Raphael
Jan 22, 2015 at 16:14
• I tried to put it in an understandable way since hes struggling to understand the principles of nondeterminism in a theoric way Jan 22, 2015 at 18:58
• @Raphael What would be a more helpful intuition, in your opinion? Apr 18, 2018 at 3:32

In state $q_0$ without reading any input the NFA both stays in $q_0$ and (in an alternative universe, if you will) it also moves to state $q_1$. This is similar to what would happen in an NFA which had two transitions to different states on an input of a character. In particular, your NFA accepts the empty string, since on no input it can make a transition to the accept state $q_1$.

Continuing your example, from state $q_0$ seeing input $0$, it would consume that symbol, stay in state $q_0$ (the loop) and also go to state $q_1$, thereby accepting input $0$. In state $q_0$ reading input $1$, the NFA would go to state $q_2$. It might also not consume the $1$, change to state $q_1$ in another universe and get stuck there (and not accept, since it hadn't read all the input), since there's no transition from $q_1$ on a $1$.

See if you can convince yourself that the language accepted by this machine is denoted by the regular expression $0^*+0^*11^*1$, i.e., any string consisting of zero or more $0$s followed by either nothing at all or two or more $1$s.

By the way, there's an algorithm which takes an NFA with $\epsilon$-moves and produces an equivalent NFA without $\epsilon$-moves, which I expect you'll learn shortly.

I tried construct DFA for this NFA

$\sum$ - alphabet set

$Q$ -states set

$\sigma(Q\times (\sum \cup {\epsilon} )) \to P(Q)$ state func

$q_0 = q_0$

$F \subseteq Q, F = \{q_0\}$

Because every NFA has equal DFA lets construct DFA $M'$ for this given NFA.

alphabet - the same

$Q' = P(Q)$ - states

Current state is $R \in P(Q)$

$E(R)$ - epsilon closure return set of states reachable over zero or more $\epsilon$ - connections for every $r \in R$

$\sigma'(R,a) = \bigcup_{r \in R} E(\sigma(r,a))$ -transitions

$q'_{0} = E(\{q_0\})$

$F' = P(Q) \div F$

Some compute on this FSM

$1.$ $\epsilon$ on input: $q'_{0} = E(\{q0\}) = \{q_0, q_1\}$ initial state include $q_1$ so FSM accept $\epsilon$

$2.$ $0*$ on input: $\sigma'(\{q_0, q_1\}, 0) = E(\sigma(q_0,0)) \cup E(\sigma(q_1,0)) = \{q_0, q_1\} \cup \{ \} = \{q_0, q_1\}$ so FSM accept $0*$

at least $\{\epsilon, 0* \} \subset L (M')$

Thanks to David Richerby

• Thanks for thanking me but I don't really see how this answers the question. You haven't established what language the machine accepts and you haven't addressed any of the three bulletted questions. Sep 9, 2016 at 12:19
• 1) when input is $\epsilon$ (empty string) , FSM state is $\{q_0, q_1\}$ 2) when input is $0$ or even $0*$ FSM state is $\{q_0, q_1\}$ both of those subjects of initial questions, is not it? Sep 9, 2016 at 13:23