Problem statement: Produce an NFA that accepts the strings 0* and 1*. So 000 and 11 would be accepted, while 101 would not be.

I'm a bit concerned about my idea because not all combinations of the alphabet are producible in it. Is this NFA legitimate?

My idea (updated to include the empty string):

enter image description here

  • $\begingroup$ You don’t need us to look at the definition of NFA. $\endgroup$ Sep 15 '19 at 22:12
  • $\begingroup$ You can’t expect your textbook to contain all possible automata... $\endgroup$ Sep 15 '19 at 22:22
  • $\begingroup$ So far, all of them have been able to produce every combination of the alphabet. I thought, if there was a possibility of that not being a property of the machine, they would have discussed it. But they haven't, and I'm new to this, so I'm asking you for help. $\endgroup$
    – Firkamon
    Sep 15 '19 at 22:23
  • $\begingroup$ Find a better textbook. $\endgroup$ Sep 15 '19 at 22:24
  • 2
    $\begingroup$ I'm voting to close this question as off-topic because it is a request to check an answer to an exercise with no questions asked about that answer. $\endgroup$ Sep 15 '19 at 22:41

In a nondeterministic automaton, a given string may have multiple possible paths through the automaton, since the path may include $\varepsilon$-transitions and may reach nodes where there is more than one possible non-$\varepsilon$-transition. A given string may also have no possible path if all the ways to traverse the automaton reach a point where there is no outgoing transition with the correct letter. If there's no possible path through the automaton, the string is rejected, just as if there are paths but none of them reach an accepting state. To determine whether a string is accepted, what matters is only whether there is a way to reach an accepting state, not what happens on paths that don't lead to an accepting state.

You can add a sink state to your automata: add a state $q_s$ which has outgoing transitions to itself (and only to itself) on all letters ($q_s \xrightarrow{0} q_s$, $q_s \xrightarrow{1} q_s$) and add transitions from other states wherever a letter is missing ($q_0 \xrightarrow{0} q_s$, $q_0 \xrightarrow{1} q_s$, $q_1 \xrightarrow{1} q_s$, $q_2 \xrightarrow{0} q_s$). Since there is no way to reach an accepting state via $q_s$, adding this state and these transitions doesn't change the language that the automaton recognizes.

“Completing” the automaton in this way isn't very useful for a nondeterministic automaton. It lets you ensure that every string has at least one path, but note that some strings now have more paths — for example the string $0$ used to only have the path $(q_0, q_1, q_1)$ but now also has $(q_0, q_s)$. The situation is different with deterministic automata. A deterministic automaton must have a transition at every state for every letter. There's a convention to allow some transitions to be missing. Such an incomplete automaton (with missing transitions, i.e. the “transition function” is only a partial function) is equivalent to a complete automaton (where the transition function is a function) which has one extra state, called a sink state, with the missing transitions leading to it and outgoing transitions only to itself. This is a useful convention with deterministic automata, where it's useful to draw automata without “useless” transitions but easier to reason on complete automata where all transitions are present. With nondeterministic automata, since a string doesn't have a unique path through the automaton, making an explicit sink state isn't particularly useful.


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.