1
$\begingroup$

enter image description here

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.

$\endgroup$
3
$\begingroup$

$\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$.

$\endgroup$
1
$\begingroup$

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.