How does an NFA use epsilon transitions?

Question

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

Answer 1

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!

Answer 2

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.

Answer 3

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