So what exactly is a final state of a finite state machine?

Question

I am playing around the state machine concept trying to better understand the best areas of their application. The formal definition of an FSM contains the following elements:

• finite non-empty set of allowed states;
• an initial state;
• an alphabet ("allowed input symbols");
• state-transition function;
• and a set of final states.

I looked at a few online sources on this topic and noticed that all of them are focusing on the transition (state + input = new state) aspect of FSM. However, very little is said specifically about the final states of a machine.

---

So what I'd like to know is:

• either [the definition of] what exactly is the a final state;
• or what is the purpose of the final state (including practical applications).

That may let me infer the answers to a whole bunch of other related questions I have. E.g., what should happen if the state machine receives an input symbol that's not allowed; if that is an error then what's the way to recover; should an FSM-based system ready for a possibility of never reaching a final state; what if the setup of a machine makes it impossible to reach a final state in the first place; should an error state be a first class object of a FSM or not, whether the state machine should or should not store the input symbol sequence in real life systems...

Answer 1

There are several variations of the definition of a finite state machine. The one you give is common in CS classes, particularly in regards to formal languages and the theory of parsing. In this context, the FSM is often directly related to a regular expression, and the goal is feed strings into the FSM to see if they match a regular expression.

The set of final states defines which states are final states. They aren't a different sort of thing. Instead of a set of final states, you can instead imagine that some states are simply labeled as final states. Indeed, the having a set of final states is isomorphic to adding a bit to each state indicating whether it is final or not.

The purpose of knowing which states are final is that a string is matched (or accepted) by the state machine if we are in a final state when we reach the end of the string. Without distinguishing final states, every prefix of the input would also be "matched". For example, for a FSM like

1 -a-> 2 -b-> 3,

if 3 is a final state (and the others are not), then it will (only) match the string "ab". If all are final states then it would match the strings "", "a", and "ab".

Beyond parsing, many problems can fit in this mold especially when we consider variations such as allowing infinite streams of input and adding output to states and/or transitions. This move allows FSMs to do more than just match things, but even matching can be more powerful than you might think (e.g. see model checking). Examples include describing protocols, communicating processes, game logic, fraud detection, business processes, and also doing model checking, hardware synthesis, and orchestration. Physical systems may also be partially modeled by finite state machines.

Answer 2

From a technical perspective a final state simply says that it is done, no more input processing will be performed.

From a practical point, for example, you might have a finite state machine that recognizes keywords, from an input stream of characters. The final state would tell you whether a particular input (character stream) represents a recognized keyword, and if so, which one.

You are correct in supposing that the final state can tell you if no particular keyword is recognized. There might be just one such final state, or there could be multiple "error" states (arbitrarily, or, to indicate particular kinds of failures, for example). Error final states are not necessarily distinguished from other final states (as far as the FSM is concerned) except by the application consuming/using the FSM.

Whether or not an FSM has final states, there can be linkage with external software and/or devices (e.g. change a signal light from red to green), such that some code or action is triggered on entering a state, or else that the state is observable (can be queried) in between inputs.

The FSM is not required to have a final state; it might be designed run indefinitely. Let's say that an FSM recognizes keywords, or no keyword, but we want it to continue on after. We might set it up so that states that were previously described as final now transition to consume input waiting for a separator (like space). Some application would have to be linked to the FSM observing it getting to certain (key but not final) states to capture as output the recognized keywords (or errors).

Answer 3

There are a couple of ways to look at it. The above two answers say, essentially, "if it gets here, the machine stops, as it has finished its job." That's by far the most common use case.

Another way to look at it, if the FSM is specifically being used to recognize a sequence of inputs, is to say "This is a legal stopping point as opposed to an illegal stopping point." End of input is detected "some other way", and the FSM's manager looks to see if it stopped in (one of) the legal stopping state(s). If it did, everything is good. If it didn't, red lights flash, sirens wail, Bad Stuff Happens.

Answer 4

According to the definitions in the UML standard:

FinalState is a special kind of State signifying that the enclosing Region has completed. Thus, a Transition to a FinalState represents the completion of the behaviors of the Region containing the FinalState.

You can imagine having some endless state machine, such as for example a light switch that you can turn on and off, the events only allow to transition between non final states. For such examples, the final state is not relevant.

However, in many cases, the state machine has an end. A typical example is a parser, that will change state (recognized grammar rule) depending on the tokens received (events). And some events will end the parser processing, such as for example when the parser encounters and EOF. So the EOF event would transition to the final state.