HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaModerate

Why does a DFA have multiple final states?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whydfastatesfinalmultipledoeshave

Problem

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.

Solution

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.

Code Snippets

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

Context

StackExchange Computer Science Q#123907, answer score: 14

Revisions (0)

No revisions yet.