1

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

  • A final state is a state that is in the set of final states. The set of final states defines which states are final states. They aren't some kind of different sort of thing. Instead of a set of final states, you can instead imagine that some states are simply labeled as final states. 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". – Derek Elkins Nov 28 '17 at 0:51
  • Note that it's a set of final states. It's entirely allowable for the set of final states to be empty. – zzzzBov Nov 28 '17 at 3:35
  • 1
    WRT your "not allowed" issue - the first time I implemented Hopcrofts minimization algorithm I made a mistake which turned out to be a sometimes-useful variant. Now I have "safe" and "unsafe" minimization, where "unsafe" minimization gives correct behavior if the input sequence is valid but doesn't guarantee to reject invalid input sequences. The benefit being slightly simpler models than "safe" minimization, which always rejects invalid input sequences. – Steve314 Nov 28 '17 at 4:05
  • Anyway, the standard FSM model is a math abstraction (so no recovery etc) - in the real world you adapt if convenient/necessary. – Steve314 Nov 28 '17 at 4:09
  • DEAR down voter/hater, mind explaining what is wrong with my question? – Igor Soloydenko Nov 28 '17 at 5:00
7

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.

4

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

  • "a final state simply says that it is done, no more input processing will be performed" -- makes sense. Is the definition of the state machine redundant then? I mean, it should be possible to INFER the final states just by looking at all the allowed transitions (which may or may not be computationally complex though). Am I wrong? – Igor Soloydenko Nov 28 '17 at 0:53
  • 2
    @IgorSoloydenko In the context of formal languages, reaching a final state does not at all mean nothing more will be consumed. It's possible that every state is a final state for any FSM. You can transition out of a final state. – Derek Elkins Nov 28 '17 at 0:56
  • In the simple case, final states declare no transitions, hence stop consuming input. There are many adaptations of state machines, however. – Erik Eidt Nov 28 '17 at 0:59
  • @DerekElkins ah, I see. That makes more sense now. – Igor Soloydenko Nov 28 '17 at 0:59
  • @DerekElkins, i guess i would have called that an accepting state, rather than a final state (and if I'm wrong I'm wrong!) – Erik Eidt Nov 28 '17 at 1:03
2

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.

  • Right. I was (and still am) trying to figure out that particular distinction. Because "a valid stopping point state" is very different from "the state a machine ended up stopping at". Also, in second case, what does it mean for a machine to stop? What if it receives more input symbols? – Igor Soloydenko Nov 28 '17 at 0:56
  • 1
    @IgorSoloydenko In the context of formal languages the input is usually a finite string and so you "stop" when you've consumed all the input. (You can also "fail" if you have input but no transitions out of the current state match it.) For infinite input, you usually won't have final states. – Derek Elkins Nov 28 '17 at 0:58
  • @IgorSoloydenko To point out something that may not be clear, there are many variations on the notion of a finite state machine that lead to different definitions and different uses. (Though even the same definition can be used in seemingly quite different ways.) The definition you've provided is one that is more common for parsing and is intimately related to regular expressions. Other definitions, for example, might instead accept only infinite streams of input, not have final states but have outputs associated to transitions. – Derek Elkins Nov 28 '17 at 1:04
  • @DerekElkins now -- with your answer below -- I figured that state machine is a term that has many many applications that may very (similar to say graphs, or trees). Thanks! – Igor Soloydenko Nov 28 '17 at 1:06
1

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.

protected by gnat Aug 31 '18 at 12:06

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.