12
$\begingroup$

In the picture below, I'm trying to figure out what exactly this NFA is accepting.

enter image description here

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Jan 22 '15 at 12:23
9
$\begingroup$

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!

$\endgroup$
  • 6
    $\begingroup$ "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. $\endgroup$ – Raphael Jan 22 '15 at 12:22
  • $\begingroup$ 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. $\endgroup$ – H_DANILO Jan 22 '15 at 14:57
  • $\begingroup$ 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. $\endgroup$ – Raphael Jan 22 '15 at 16:14
  • $\begingroup$ I tried to put it in an understandable way since hes struggling to understand the principles of nondeterminism in a theoric way $\endgroup$ – H_DANILO Jan 22 '15 at 18:58
  • $\begingroup$ @Raphael What would be a more helpful intuition, in your opinion? $\endgroup$ – Andrey Portnoy Apr 18 '18 at 3:32
4
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Sep 9 '16 at 12:19
  • $\begingroup$ 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? $\endgroup$ – OrangeFish Sep 9 '16 at 13:23

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.