7
$\begingroup$

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.

$\endgroup$
4
14
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ Can't we design a big DFA that only one final state that has equal functionality with the multiple ones? $\endgroup$
    – kelalaka
    Apr 10 '20 at 17:38
  • 5
    $\begingroup$ @kelalaka No that is not possible. In this example there is no way to have only one final state because the states for ho and hoho need to be different. $\endgroup$
    – 6005
    Apr 10 '20 at 19:05
  • 11
    $\begingroup$ However, the longer answer is that designing such a DFA would be possible if you assume that all input strings are terminated with a special "end of input" symbol, like null-terminated strings. But in the usual definition of a DFA, this representation of strings is not used. $\endgroup$
    – 6005
    Apr 10 '20 at 19:06
  • 6
    $\begingroup$ In this case it's very easy to prove that two different accepting states are needed: hoho and hohoho must both end in an accepting state. And they can't end in the same state, because processing ho from the state of hoho must end in an accepting state (because hohoho is in the language), but processing ho from the state of hohoho must end in a rejecting state (because hohohoho is not in the language. So we have two inputs that must end in different accepting states. $\endgroup$
    – gnasher729
    Apr 11 '20 at 15:00
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ There seems to be an error in the proposition: $ab^*a$ is accepted by a DFA with one final state, but is not of the given form. More generally any language with a "visible" end of string will be accepted by a DFA with one final state: e.g. $\# L \#$ for any regular language $L$ over $\Sigma \setminus \{\#\}$. $\endgroup$
    – 6005
    Apr 11 '20 at 15:41
  • $\begingroup$ Right. That's what happens when a proof is not spelled out... Hopefully the current version is correct. I replaced "finite" with "regular". $\endgroup$ Apr 11 '20 at 15:53
  • $\begingroup$ +1. Just one other thing: I think the assumption $\epsilon \in B$ is not what you want, since that implies that $B = \{\epsilon\}$. I think you want $\epsilon \notin B$ instead (edited to fix). $\endgroup$
    – 6005
    Apr 11 '20 at 16:27
  • $\begingroup$ I guess there is another edge case where $L$ is empty. Then $A$ must be empty but there are many possible choices for $B$. The case $L$ finite and nonempty corresponds to $B = \varnothing$, so that is OK. $\endgroup$
    – 6005
    Apr 11 '20 at 16:29
  • $\begingroup$ Since $S^* = (S \cup \{\epsilon\})^*$, the exact status of $\epsilon \in B$ doesn't matter. $\endgroup$ Apr 11 '20 at 16:39

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.