Understanding $\epsilon$ transitions on NFA

Question

I can't understand why $\epsilon$ is accepted. I thought if $\epsilon$ is inputed then it would go from $q_1$ to $q_3$. $a$ is also accepted, but I though if $a$ is inputed then then the NFA would die, because in $q_1$ there's no where to go.

I read on another post about $\epsilon$ being at two states at the same time, but couldn't get it. What exactly is happening when $\epsilon$ is entered and when $a$ is entered (two different strings)?

              q1
epsilon---------------------
           q1    q3

I think the above is the correct tree when $\epsilon$ is inputed, but makes no sense to me.

Answer 1

$\epsilon$ is an empty string just like "". It is not a symbol of the alphabet. It simply means (in the NFA in your picture) that if you are on state $q_1$, without consuming any symbol you can move to state $q_3$ but you are not obliged to do so. but if you are on $q_1$ and you read $b$, then you must go to $q_2$.

Note that a word is accepted in a NFA if there exists a path from the initial state to an accepting state labelled by the symbols of this words. if should be rejected if no such a path exists.

When $a$ is entered then the possible path is move to $q_3$ without consuming anything and then consume $a$. This lead to the accepting state $q_1$.

Answer 2

$\varepsilon$ is not a letter in the alphabet, it rather denotes the empty word, the string of length $0$, etc. Thus, when an automata reads $\varepsilon$, then it is in its starting state - since nothing has been read. Since the starting state of the sample automaton is accepting, this automaton accepts $\varepsilon$.

In a non-deterministic automata, $\varepsilon$-transitions make sense. These do not read any letter, but rather can be taken "for free" at any time. Thing of strings of length $0$ being optionally present between any two letters.

Now if the automaton receives input "a", it can immediately go from $q_1$ to $q_3$ - reading the empty string at the beginning. Only then it reads $a$, and moves back to $q_1$, and thus accepts.

Of course it could have attempted to read $a$ at the beginning and died, but since a non-deterministic automaton accepts if it can somehow reach an accepting state, this does not matter.