Finite state automata: final states

Question

In our programming language concepts course, our instructor claimed that it's okay for a final state to lead to another state in a finite state diagram.

But this seems to be a fundamentally contradictory concept. Because a final state by definition is one that terminates transitions, i.e., that once you reach it, there's nothing else left to do.

And yet he presented a slide such as this one, where final states are represented by two circles... How is it possible for B, D, E, and H to be final states when they're so clearly not?

Answer 1

You seem to have a misunderstanding of generative models v.s. "recognizing" models.

The grammar you have on the right generates words by applying rules, starting from the initial variable, and stopping after there are no more variables.

Automata, however, recognize a language as follows: you feed the automaton a word, letter by letter, and the automaton takes transitions based on the letters given to it.

If, after reading all the letters, the automaton ends up in an accepting (a.k.a final) state, then we say that the automaton accepts the word.

So it's better to think of those as "accepting" states, rather than "final" states, although both terms are commonly used.

Answer 2

a final state by definition is one that terminates transitions, i.e., that once you reach it, there's nothing else left to do.

The source of your confusion is that this isn't the definition. "Final state" is a poor choice of name, and most authors seem to prefer "accepting state". The definition is that the automaton accepts if its run ends in a final/accepting state and rejects otherwise.

Answer 3

Indeed, it is confusing! To solve your problem, call them "accepting" states instead of "final" states. Because that is what they really are, just a marker that tells us that at this moment the string processed belongs to the language.

Answer 4

"a final state by definition is one that terminates transitions, i.e., that once you reach it, there's nothing else left to do."

In the traditional convention of working with acceptors (that is, finite state automata which tell you whether a given string belongs/doesn't belong to a language), a final state is one that, when reached with an empty string (the input was consumed entirely) signifies that the initial string is accepted, i.e. it is part of the automaton's language.

Answer 5

As you can see. The grammar given says A -> a. Therefore the automatom accepts to terminate on the string "a". But it also allows A -> aB -> abD -> abc, so the string "abc" is also accepted. If we finish the string at this point, we will be standing in a final state and so the string was accepted. But we might still want the string "ab" to be accepted. So we need to make sure that {"a", "ab", "abc"} are all accepted by the automaton. Do no the see final states as a state such that if we enter it we may never leave it, see it as a state to tell us if our current string is accepted or not.