1
$\begingroup$

Why is the input $\epsilon$ accepted by the nondeterministic finite automaton shown below? Does it not leave $q_1$ and go to $q_3$?

Markov chain

$\endgroup$
0
5
$\begingroup$

You're confusing the concept of the empty string $\varepsilon$ with the concept of an $\varepsilon$-transition.

The empty string $\varepsilon$ is just the string with no characters. The presence of a $b$-transition from $q_1$ to $q_2$ means that the automaton can move between those two states by reading character $b$ but the presence of an $\varepsilon$-transition from $q_1$ to $q_3$ doesn't mean that it moves by reading the character $\varepsilon$. Rather, it means that the automaton can (but is not forced to) move from $q_1$ to $q_3$ without reading any input at all.

So, when this automaton has no input, it can either remain in state $q_1$, which is accepting, or move to $q_3$, which isn't. Since it can reach an accepting state, it accepts.

$\endgroup$
3
$\begingroup$

I think you are asking why the input string $\epsilon$ (the empty string) is accepted by the given NFA. If so, you need to create a set of all states reached by the given string (in this case it is $S=\{q_1, q_3\}$) and see if an accepting state belongs to this set (in this case - yes: $q_1 \in S$).

$\endgroup$
2
$\begingroup$

To expand on Denis's answer, the given automata is non-deterministic because it has $\epsilon$-transitions. Because it's non-deterministic, given an input of the empty string $\epsilon$, we don't have to follow the transition from $q_1$ to $q_3$; we can just stay in $q_1$, which accepts the string.

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