Skip to content
StateWORKS

Technical FAQ

See also the General FAQ.

What is a Finite State Machine?

Section titled “What is a Finite State Machine?”

A finite state machine is another name for a finite automaton.

From a pure mathematician’s point of view, see the more detailed explanation in the books [S1][S2][S3] linked in the References.

When a system functions by passing through various situations, known as states, in which the rules for passing from each state to any other are well-defined, then the system can be modelled as a finite state machine (FSM). For each state there will be one or more new states to which the system can pass, under defined conditions. These, in a real-time or embedded control system, will often be stimuli or events from external causes, but that is not always true: perhaps an internal timer has expired, for example.

The simplest sort of finite state machine, if built in hardware, might be something like a 4-bit binary counter. Taking the state as the settings of the 4 bits of the counter, i.e. 4 flip-flops, and assigning hexadecimal codes to them, the initial state might well be 0 and, on receiving an event trigger, the counter will progress to states 0 → 1 → 2 → 3 → ... → F. A reset demand would force the counter to go to state 0.

A very important point to understand is that the state of an FSM depends on its previous history, as only certain paths through the various possible states are permitted, according to the requirements. In software, the FSM cannot—or at least should not—be instructed by other processes to go to a specific state. Instead, the software FSM receives input, which, according to its internal rules, governs the state transitions. You can think of it as an object whose internal data representing the state can only be altered by an associated internal program.

So a state is a number?

Section titled “So a state is a number?”

No, it is given a name. Although states could be referred to by numbers, as in the example of a counter, they are more generally given names by the designer. (If the software then finds it easier to use an array of names when handling states, then each state will be identified by an index, which will be an unsigned integer. But this is, or should be, an internal matter.)

How does one deal with the design of a state machine?

Section titled “How does one deal with the design of a state machine?”

Most designers prefer to make a diagram, showing each state as a small circle or disc, with lines indicating all the permitted transitions. The state names are written on the discs, and quite often the conditions that will trigger transitions between states are marked along those lines. For a mathematician, this is a “graph” where the states are “vertices” and the transition lines are “edges”.

Of course, this can get rather untidy, and an alternative approach is to make a square table, showing “present state” as rows and various stimuli as columns. Any valid transition will be defined by filling in one cell of the table with the name of the next state, and there will be quite a lot of empty cells as a rule. This idea often looks good in the textbook, but in many practical cases it becomes hard to use.

As you will see if you look at the StateWORKS editor, it is possible to combine graphical and tabular methods in a very easy-to-use Integrated Development Environment. The textual form of the data produced by the StateWORKS editor gives a complete description of the FSM, while the graphical version shows the structure as an easily followed diagram.

State transition diagrams look rather like flowcharts: is there a difference?

Section titled “State transition diagrams look rather like flowcharts: is there a difference?”

Yes. A flowchart expresses all the operations of a program, including data treatment algorithms. The various possible paths through the flowchart are determined by various tests that the program makes. In some instances, the structure of the program, as seen in the flowchart, can be expressed as a transition diagram for a finite state machine. But it is better to avoid mixing any algorithmic procedures into that diagram. Furthermore, a flowchart would usually express the operation of a self-contained entity, whereas transitions in a finite state machine are very often caused by external stimuli.

The essential difference between a flowchart and a state machine is the state. The state in a FSM represents the history of the system up to this moment. In a flowchart, the state is not present explicitly; it is hidden in variables (flags) used to store past information.

To take a simple example, a flow diagram might show an element Wait 5 seconds. A finite state machine would have a state named Waiting, and the output transition would be caused by the event 5-second timer expired. At the entry to the Waiting state there could be an instruction to set up the timer to 5 seconds by means of a system call. So it seems that flow diagrams and state transition diagrams can have a lot in common when we deal with a self-contained program. But an embedded system in which there are many external stimuli able to influence the finite state machine will be hard to express as a flowchart, particularly as the behavior of the FSM will be quite complex as it reacts to the environment.

An example of this is a situation where one is waiting to go through one of three doors—whichever opens first. A flow diagram will need to check if door A is open; if Yes, go through it; if No, then check if door B is open, etc., and return in a loop to the starting point if all doors are still closed. So the flow diagram shows a continuous activity. A state diagram will show a single Wait for an open door state, and three possible transitions from it, triggered by the opening of each door, to states marked pass through door A (or B, or C). While one is waiting, nothing seems to be going on. So the state diagram is easier to understand in many complex situations. Of course, it does not say anything specific about how the underlying software is actually dealing with this situation, and a “coded” state machine might in fact do just what the flow diagram example showed as a way of handling it.

It is usually impossible to prove the correctness of a flow diagram because of the data manipulations it contains. A state diagram is amenable to formal analysis and verification.

In conclusion, a finite state machine is a tool for modelling a situation at a more abstract level than a flow diagram.

For more information, refer to the technical note “A Flowchart is not a State Machine”.

I thought FSMs were only used when parsing “regular expressions”, or in other words as the front end of a compiler?

Section titled “I thought FSMs were only used when parsing “regular expressions”, or in other words as the front end of a compiler?”

This is a major application for state machines in software development and is well explained in textbooks about compiler writing. But the state machine for analysis of text is quite differently oriented from one used for an industrial control system. It is generally fairly simple in structure, even though it may use recursion, and has “final states” that express that some patterns have been found. It is an isolated module that works like any other procedure in that it accepts input and gives a result back. It functions in a cozy environment.

A control system, on the other hand, will require quite complex state machines, and these will have to deal with various malfunctions and problems of the real physical world. Error handling causes an increase in the number of states, and in order to deal with large systems, a number of FSMs should be used and arranged to operate in a hierarchy.

How would StateWORKS handle large systems?

Section titled “How would StateWORKS handle large systems?”

You should avoid creating very large state machines to express the state of a complex system. Instead, the system should be designed as a set of FSMs, each with a clearly defined task. Why? Just imagine a rather small system using 5 FSMs with 16 states each. Then suppose the same project is expressed as a single FSM: it could have a million states! Even though, in practice, many will be impossible and perhaps only a few hundred are possible (plus a few hundred more one might reach by accident), it becomes quite impossible to understand and work with so much complexity. One is led to consider only the most obvious possibilities and to neglect obscure error situations.

StateWORKS contains tools for setting up a system of multiple FSMs (see this question). This permits a complex system to be split into a number of simpler systems, each of which can be developed, studied, simulated, and modified on its own. We advise a hierarchical system, with a master controlling a few slaves, possibly over several levels. In many cases, a single state machine design will be used in several instances, each with its own properties. Certain error-recovery processes may be designed as specific FSMs under the control of their immediate master. You may well find that several error-recovery processes are almost identical, and this clarifies and facilitates the implementation of the complete system.

The mechanism for this is to create a “Project” to enable the tools for communication. A “master” can see the states of “slaves” as inputs, and it can also issue commands to them. To set up the individual communication links, you can employ a StateWORKS “Template”. If you decide to do this late in the project, there is a possibility of creating a template from one of the state machines you have already designed.

I read a little about FSM, and the book was full of higher mathematics! Does one have to be a good mathematician to handle these techniques?

Section titled “I read a little about FSM, and the book was full of higher mathematics! Does one have to be a good mathematician to handle these techniques?”

Not at all. You ought to learn a little about FSMs, but we provide instructions that will equip you to work with them.

What is StateWORKS?

Section titled “What is StateWORKS?”

StateWORKS is a tool that can make the development of many types of software more straightforward and more predictable. The essential idea is that coding, in languages such as C++, is an activity that can become hard to manage in very complex situations. The resultant code is often very hard to read, and it is particularly hard to understand how it will behave in unexpected situations.

Using StateWORKS, the flow of control in the program, expressed in the form of state machines, is isolated from all the numeric calculations that the project will need and developed separately. This is done at a more abstract level than writing code in languages such as C++, and if you look at the various examples in the documentation, you will appreciate that this work can be done by the systems analyst and the end user working together, as they are effectively producing a full specification for the system. Some people would classify StateWORKS as a Domain-Specific Language, and although this is true, StateWORKS goes far beyond that concept.

Various manipulations of input data, such as digital and analogue readings from an industrial process, are performed in a separate place, and the results are supplied to a “Real-time Database”, which is a part of StateWORKS. The RTDB then supplies what we call “virtual inputs” to influence the behavior of the various state machines.

Conversely, as the state machines function, they will call for certain outputs to be driven, such as opening a valve or starting a motor. These actions are also handled by the RTDB. StateWORKS has quite a variety of standard input and output mechanisms already programmed, so there is very little work needed in most cases to program this part of a control system.

There are also requirements for complex computations from time to time, and these can be initiated as required by the state machines. They will be coded in the conventional way, as procedures or servers, depending on the mechanisms preferred by the developer and the facilities specific to the programming languages they wish to employ. This topic is dealt with in more detail in the User Manual.

StateWORKS is particularly efficient when used to design very complex systems using a number of state machines and provides a means of mastering system complexity. The strategy of progressively designing the system as a number of state machines arranged in a hierarchy is one of the most important features of StateWORKS.

The final point to make—and this is a crucial difference from other state-diagram-based tools—is that once the state machines are fully specified, the StateWORKS tool does NOT GENERATE CODE. It produces a compressed version of the specifications and then, at run time, this is executed by a standard executor routine. The compressed version is arranged for very fast and efficient implementation of the control flow of the entire system.

The executor is a fixed and highly reliable software module that has functioned in a wide variety of environments for over a decade without needing to be altered. In a sense, it enables the computer to understand and fully implement the specification.

But suppose that I need to patch the code afterwards?

Section titled “But suppose that I need to patch the code afterwards?”

You must not even think of it. If you use StateWORKS, you cannot access the final code because it does not even exist. You must go back to your IDE (StateWORKS Studio Editor) and make the required changes there; it is, after all, quite easy.

Patching very complex code is one of the most dangerous pastimes we know of, and it nearly always gets you into trouble. A small change is made, then tested, and seems to function, but there may be all sorts of obscure side effects caused by incorrect handling of unusual situations that you did not test. These are more easily avoided if you work at the system specification level and, of course, run simulations to check all possibilities. The high-level documentation, as expressed by the state diagrams and associated text, will then always correspond to reality, which will be much appreciated by anyone wishing to make changes at a future date.

Too much coding is bad for the health of your project! The tragedy of the modern software situation is that, even without using the most advanced tools, almost any approach can be made to work if enough effort is put into it by brilliant programmers—but at what cost in time slippage, late nights, stress for managers, etc.? You start measuring productivity in terms of the rate at which you fix bugs at a time when the project should have been completed. A mechanical engineer would not build a bridge or design a diesel engine like that, and neither should a software engineer.

It sounds as though StateWORKS uses an interpreter. Is it not very inefficient in that case?

Section titled “It sounds as though StateWORKS uses an interpreter. Is it not very inefficient in that case?”

In a sense you are correct, but the StateWORKS executor has little in common with interpreters used for languages such as BASIC. It is not working with the text entered by the designer, but on a very compressed and efficient binary file designed for execution. The “virtual environment” in which it functions requires the governing expressions to be made from sets of assertions, which might, for example, be represented as binary digits in an array. So the run-time system just needs to test sets of these, is very fast, and can keep up with other approaches such as coding.

I know something about FSM and wonder which model is used by StateWORKS?

Section titled “I know something about FSM and wonder which model is used by StateWORKS?”

The classical theory of finite state machines refers to two models: the Moore model and the Mealy model. The Moore model state machine generates outputs that depend only on the current state, while the Mealy model generates outputs that are a function of both the current state and the inputs. When implemented in hardware, the Moore model may make output generation simpler, particularly if the digital embodiment of each state name or code is carefully selected, but it may require more states than the equivalent Mealy machine. In software, the differences become more academic, and in fact StateWORKS combines features of both models.

Outputs, called “actions” in StateWORKS to make them more general, can be generated when an FSM enters a given state (entry action), or when it leaves a given state (exit action). The first corresponds to the Moore model, while the second is not foreseen in theoretical models but stems from engineering practice. In a way, it could be derived from the Mealy model as a specific variant of an input action. The true input action, as defined in the Mealy model, is determined in each state by the inputs but not necessarily by the transitions.

A third possibility exists in StateWORKS: an output “action” can be triggered by an input when the FSM is in a specific state, without causing a state transition. This is a classical case of a Mealy model and can sometimes simplify the structure of the FSM.

Another kind of action is imaginable: a so-called transition action, which is again a specific action of a Mealy model. The transition action is performed when a transition occurs.

StateWORKS uses three action types: entry, exit, and input.

You mentioned UML. Does StateWORKS resemble it?

Section titled “You mentioned UML. Does StateWORKS resemble it?”

StateWORKS shares ideas with UML in that it encourages system architects to work at the level of system description in state-diagram format. But UML, like most other CASE tools, generates only a small fraction (typically 2%) of the code and does not allow for automatic validation of the final system. The full notation of UML is over-complex, as it was based on the assumption of manual coding, and certain features preclude automatic generation and validation of code.

In the book “Mastering UML with Rational Rose”, to take one example, one is advised that “state transition diagrams are not created for every class: they are used only for very complex classes.” In StateWORKS, in contrast, one must build a state model for every class where a reaction to any event requires remembering at least one past event. This ensures that the total system behavior is captured in FSM models and not in code. Otherwise, we face the recurring problem of re-engineering software from old and often impenetrable source code.

StateWORKS does not use StateCharts concepts: those were developed for top-down design and have serious conceptual difficulties in implementation. The StateWORKS strategy of constructing the system from a number of components that are individually easy to design and understand is much more powerful.

StateWORKS is a tool not only for the systems analyst but also for developers writing the software. StateWORKS FSM models can—and must—take into account all the tricky details that are often omitted in UML models but must be implemented in code. This means that StateWORKS is used effectively to clarify initially unclear specifications and to develop a precise behavioral specification, leaving no design decisions to be made by “coders”.

StateWORKS has much in common with Agile methods in how it should be applied.

How easily is StateWORKS ported to various environments?

Section titled “How easily is StateWORKS ported to various environments?”

Although an early version was written in Concurrent Pascal, the current version is in C++. The most highly developed IDE and run-time environment has been created for Microsoft Windows. The run-time system is developed as a StateWORKS Library (in C++) and is also applicable to Linux and other (real-time) Unix-derived operating systems. It is always possible to apply StateWORKS to diskless embedded target systems.

StateWORKS may not be suitable for the very smallest systems, but major elements have been used on small embedded control systems using the Zilog Z280 ↗ processor. There is even an example of a small project using some 1500 words of program memory in a Microchip PIC16F873 ↗ microcontroller, programmed in assembler but using basic StateWORKS concepts to great advantage.

What about high-availability hot-standby systems?

Section titled “What about high-availability hot-standby systems?”

The concentration of data defining the state of a system—as the states of all finite state machines that compose it, along with current input-output stimuli in the real-time database of StateWORKS—makes it easy to organize the shadowing of an active system by a standby system.

My telephony application needs thousands of identical, but short-lived, finite state machines. How could StateWORKS cope with that?

Section titled “My telephony application needs thousands of identical, but short-lived, finite state machines. How could StateWORKS cope with that?”

You are probably dealing with something like call setup for V5. The problem in such applications is the system overhead required to create a new finite state machine, which can limit performance. A special version of the executor has been developed to handle the dynamic creation and destruction of large numbers of identical state machines, which exist as parameters in the real-time database. So StateWORKS can handle such projects more efficiently than current practice in the telecoms industry.

Which kind of action should I use?

Section titled “Which kind of action should I use?”

The state machine model used by StateWORKS allows entry, exit, and input actions. Using only entry actions means your model is of the Moore type. Using input actions means your model is of the Mealy type. Moore-type state machines are generally more comprehensive, while a mix of Moore and Mealy models minimizes the number of states.

As a general rule based on experience, we suggest maintaining a consistent design philosophy. For example, the state machine enters a state, performs actions (entry actions), and waits for reactions from the I/O system or other state machines. This corresponds to the Moore model and should be preferred in most situations. Avoid overusing all available action types that StateWORKS provides. Exit actions should be used sparingly, mainly for auxiliary activities such as stopping timers. While mixing actions can reduce the number of states, it may also make the system harder to understand.

How should I build a system of state machines?

Section titled “How should I build a system of state machines?”

One of the most important aspects of StateWORKS is how it helps manage this situation, as mentioned in the answer to this question. We recommend a hierarchical structure. The StateWORKS interface supports this: the master sends commands to slaves, which “display” their states to the master. While less structured communication is possible, we believe that, except in very rare cases, non-hierarchical systems should be avoided. A hierarchical system is easier to understand and design, while a fully interconnected system quickly becomes too complex to manage.

What is the difference between Moore and Mealy FSM?

Section titled “What is the difference between Moore and Mealy FSM?”

To understand the difference between Moore and Mealy, the concept of actions must be clear. Here, only Entry Actions and Input Actions are of interest:

  • Entry Actions:
    For each state, one or more actions can be defined that are executed whenever the state is entered. The execution depends only on the new state and occurs after a transition.
  • Input Actions:
    For each state, one or more actions can be defined that are executed when certain conditions are true. No state transition is required. The execution depends on both the current state and input.

Moore FSM uses only Entry Actions, resulting in very clear behavior: actions occur only when the state changes.

Mealy FSM uses only Input Actions. The behavior is less intuitive because actions are not necessarily tied to state transitions. However, Mealy FSMs are usually more compact (fewer states).

We recommend using a mixed approach, but primarily Moore-based FSMs. Input actions should be used only for secondary tasks such as logging or alarms. This reduces the number of states without sacrificing clarity.

For more information, refer to the technical note Moore or Mealy model?

References

Section titled “References”

There are many books and papers covering state machine topics. Rather than providing an exhaustive list, we offer a few recommendations. The danger is that such references are subjective, but for beginners it may be more helpful to read a small number of recommended works than to search through thousands of results. Consider the list below as a starting point.

General

State machine:

  • [S1] J. Caroll, D. Long, Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall, Englewood Cliffs, N.J., 1989.
  • [S2] S. Sjoholm & L. Lindh, VHDL for Designers. Prentice Hall, 1997.
  • [S3] Z. Kohavi, Switching and Finite Automata Theory. McGraw-Hill, 1978.
  • [S4] F. Wagner, Modeling Software with Finite State Machines: A Practical Approach, Auerbach, 2006.

Engineering:

  • [E1] M. Gomez, “Embedded State Machine Implementation”, Embedded Systems, Vol. 13, Nr. 13, December 2000. (Available in archive: Embedded System Programming ↗)
StateWORKS and VFSM