Why does a DFA have multiple final states?

Question

I am taking a course on programming language design and we got to the DFA part. It is known to be formally defined by a 5-tupple but they did not make it very clear to us why a DFA can have multiple final states. I know that the languages ​​that it can accept are involved, but nothing else.

Answer 1

A DFA is a machine that reads in its input left to right, and, while reading, keeps track of its internal state. At the end, it has to decide whether to "accept" or "reject" the input based only on whatever internal state it has at the end. The final states are used to indicate which internal states should inform the machine to accept.

The reason we need to have multiple final states, then, is because we might want to accept the input in multiple different scenarios. Here is a simple example. Suppose we want to design a machine that accepts if the input is either ho, hoho, or hohoho (so we want to accept, in total, three possible input strings). Then the "state" of the machine can keep track of what letters we have seen so far: we have 7 states for [nothing], h, ho, hoh, hoho, hohoh, hohoho. If we get a letter that isn't going to be one of these strings (like if the input is haha or asdf), we need a different state to remember that the input was bad, and we can call that state [bad input]. So in total we have 8 states.

Now in this example, we want to accept three different strings: ho, hoho, and hohoho, so we need all three of those states to be final. It turns out that it would be impossible to accept these three strings if we have to have only one final state.

All states (8): [nothing], h, ho, hoh, hoho, hohoh, hohoho, [bad input]
Final states (3): ho, hoho, hohoho

In summary, multiple final states gives us the ability to accept multiple different possible patterns in the input. The above is one example of that, but there are many other examples where it is useful.

Answer 2

Consider an arbitrary nondeterministic finite automaton.

If it has multiple final states, you can create an epsilon transition from all of the final states to one common final state, remove the "final state" mark from all of the previously final states so that you have only one final state. So, a nondeterministic finite automaton can very well work with just one final state.

However, if you explode a nondeterministic finite automaton into a deterministic finite automaton, you'll find that you no longer can have epsilon transitions. The states of the exploded deterministic finite automaton correspond to sets of states in the nondeterministic finite automaton.

You will find that you need to mark a state as "final state" if at least one of the NFA states in the set is the final state. There may be multiple such states.

So, in summary: an NFA can very well work with just one final state. A DFA can't, unless you want to restrict DFAs arbitrarily. By arbitrarily restricting DFAs, you are creating a situation where there are NFAs that cannot be converted to DFAs, and that there are regular expressions that cannot be accepted by any DFA.

Answer 3

Let me provide a characterization of what languages DFAs with a single accepting state can accept.

Proposition. A language $L$ over $\Sigma$ is accepted by a DFA with a single accepting state if there exist two regular prefix codes $A,B$ such that $L = AB^*$. Furthermore, this representation is unique, assuming $L \neq \emptyset$ and $\epsilon \notin B$.

(A prefix code is a set of words, none of which is a prefix of another one. It is regular if as a language it is regular.)

Proof. Let $A$ be the language of words which move the DFA from its initial state to its final state without transitioning through the final state (if the initial state is also final, $A = \{\epsilon\}$), and let $B$ be the language of non-empty words which move the DFA from its final state back to itself, again without transitioning through the final state.

The languages $A,B$ are clearly regular. To see that they are prefix-free, suppose to the contrary that $x,y \in A$, and $x$ is a proper prefix of $y$. Thus when reading $y$, the DFA passes through the accepting state upon reaching $x$. The case of $B$ is similar.

In the other direction, consider a minimal DFA for $A$. All words in $A$ are equivalent with respect to the Myhill–Nerode relation. Indeed, if $x,y \in A$ then $x\epsilon,y\epsilon \in A$ by $xz,yz \notin A$ for $z \neq \epsilon$ since $A$ is prefix-free. Thus the minimal DFA contains a unique accepting state. Similarly, the minimal DFA for $B$ contains a unique accepting state. Merging the accepting state of the former DFA with the initial DFA, we get the desired DFA.

Finally, let us show that the decomposition is unique. Given $L = AB^*$, we an extract $A$ as the set of words in $L$ which have no proper prefix in $L$. Taking any $w \in L$, we can extract $B$ as the set of words in $w^{-1} L$ which have no proper non-empty prefix in $w^{-1} L$. (This step fails if $A = \emptyset$.) $\square$

---

In particular, if $L$ contains two words $x \neq y$ such that $x$ is a prefix of $y$ then $L$ is infinite (since $B$ must contain a word other than $\epsilon$). This shows that $\{ho,hoho,hohoho\}$ requires more than one accepting state.

From Myhill–Nerode theory, it is known that the minimal number of accepting states equals the number of Myhill–Nerode equivalence classes of words in the language. In the example $\{ho,hoho,hohoho\}$, each word is in its own equivalence class, so exactly three accepting states are needed. (With some work, it should be possible to identify a combinatorial parameter which determines the minimal number of accepting states in any finite language.)