Are Nondeterministic Finite Automata not allowed 'sink-states'?

Question

By definition are Nondeterministic Finite Automata not allowed a 'sink-state' (non-accepting state we don't get out of)? I can see us having them for NFA but not necessary but do not see how they are against the rules of a NFSA/NFA or should not be allowed. My teacher said they are not allowed in a NFA/NFSA, but even if you have a 'sink state' in a NFA/NFSA I can see the diagram working and meeting the conditions. Can someone please clarify about this.

Answer 1

Well, your teacher is wrong. In fact, we have a term for finite automata which the always have a transition for each symbol: they are "complete". You could not have complete DFAs or NFAs which accept all regular languages if you did not have "sink states", as you call them.

(By the way, I don't think there's a standard term for states like this, by the way, but I like "sink state".)

A string is accepted by a NFA if there is some path that ends in an accepting state, even if there is a path for the same string which ends up in a "sink state". By the way, it's not a "state we don't get out of" in the sense that we loop forever, because the input to a DFA or NFA is finite.

Now of course these states are inefficient. If you're writing a lexical analyser, for example, you don't want to consume the rest of an input program if a lexical syntax error is detectable early. But there's no theoretical problem with them.

It's also worth noting that NFA and DFA construction algorithms based on Brzozowski derivatives often naturally generate these sink states. See, for example, figure 2 in this tech report. Rather than detect them directly (which isn't difficult), you can remove these states with DFA minimisation if you were going to perform that step anyway. In fact, you can add a known sink state with no incoming transitions $q_\mathrm{sink}$ to the non-minimised DFA, perform minimisation, and then any state merged with $q_\mathrm{sink}$ must also be a sink state and can be safely removed.