0
$\begingroup$

I have chosen an example task to see if I understood DFA and NFA correctly.

So let's say we have that task:

Given alphabet $\Sigma = \{0,1\}$ and the language $L = \{w \mid w \text{ includes two consecutive zeroes}\}$. Create a DFA and a NFA for the language with as less as possible states.

The following description is just a rough one (there are much more attitudes a DFA / NFA has). Please tell me if it's correct anyway because these are the ones I'm not sure about.

For this example, each state of the DFA needs at least two outgoing arrows. So each state needs at least one outgoing arrow $0$ and one outgoing arrow $1$ because we have $\Sigma = \{0,1\}$. We do not really need to care about incoming arrows, there can be any number of incoming arrows.

For the NFA, however, we do not need to care how many outgoing / incoming arrows we use for each state.

So here I made a DFA and a NFA where the words include two consecutive zeroes. Did I do it correctly?

enter image description here

$\endgroup$
1
$\begingroup$

The difference of DFA and NFA is in the transition map (or "outgoing arrows" as you describe) and has nothing to do with "incoming arrows". Namely, if $\Sigma$ is the input alphabet then the transition function of the DFA must be uniquely defined for each state and input symbol pair

$$\delta(q,a) = p, \text { for } q,p \in Q, a\in \Sigma$$

In case of the NFA the transition function maps each pair $(q,a)$ to a subset of states $Q$ $$\delta(q,a) = Q' = \{p_1, p_2, \dots, p_n\}, \text { for } Q' \subseteq Q, a\in \Sigma$$

In simply words, for DFA for each input symbol a state must have exactly one outgoing arrow, but in the case NFA for each input symbol a state may have more than one outgoing arrows or no outgoing arrow.

In your example $\Sigma=\{0,1\}$ and thus the DFA must have exactly two outgoing arrows for each state, but the NFA may have no outgoing arrow or up to $|Q|$ outgoing arrows.

$\endgroup$
  • $\begingroup$ Thanks for your answer. If I look at the example I solved, it seems to satisfy every point you mentioned. Can you confirm if it's correct? $\endgroup$ – cnmesr Oct 21 '17 at 22:06

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.