StateWORKS: Frequently Asked Questions

  1. What is a Finite State Machine?
  2. So a state is a number?
  3. How does one deal with the design of a state machine?
  4. State transition diagrams look rather like flow charts: is there a difference?
  5. I thought FSM were only used when parsing "regular expressions" or in other words as the front end of a compiler.
  6. How would StateWORKS handle large systems?
  7. 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?
  8. What is StateWORKS?
  9. But suppose that I need to patch the code afterwards?
  10. It sounds as though StateWORKS uses an interpreter. Is it not very inefficient in that case?
  11. I know something about FSM and wonder which Model is used by StateWORKS?
  12. You mentioned UML. Does StateWORKS resemble it?
  13. How easily is StateWORKS ported to various environments?
  14. What about high-availability hot-standby systems?
  15. My telephony application needs thousands of identical, but short-lived, finite state machines. How could StateWORKS cope with that?
  16. Which kind of action should I use?
  17. How should I build a system of state machines?
  18. What is the difference between Moore and Mealy FSM?

Answers:

Q1. What is a Finite State Machine?

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

For a pure mathematician's point of view, see the more detailed explanation in the books [S1][S2][S3].

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, on 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 "1", "2", "3" etc. up to "F". A reset demand would force the counter to go to state "0".

A very important point to understand is that the state of a 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 can not - 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, govern 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.

See also the state machine definition and an example on our web-page.

Q2. So a state is a number?

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

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

A. Most designers prefer to make a diagram, showing each state as a small circle or disc, and with lines indicating all the permitted transitions. The state names are written on the discs, and quite often the conditions which 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 text-book, 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.

Q4. State transition diagrams look rather like flow charts: is there a difference?

A. Yes. A flow chart expresses all the operation of a program, including data treatment algorithms. The various possible paths through the flow chart are determined by various tests which the program makes. In some instances, the structure of the program, as seen in the flow chart, can be expressed as a transition diagram for a finite state machine. But it is better to avoid mixing up any algorithmic procedures in that diagram. Furthermore, a flow chart 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 flow chart and a state machine is the state. The state in FSM represents the history of the system up to this moment. In a flow chart the state is not present explicitly, it is hidden in variables (flags) used to store the 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 flow chart, particularly as the behaviour 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 though 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 though door A (or B, or C)" and 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 in fact dealing with this situation, and a "coded" state machine might in fact do just what the flow diagram example showed as a way of dealing with this situation.

It is usually impossible to prove the correctness of a flow diagram on account of the data manipulations which 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 see also the technical note " A Flowchart is not a State Machine"

Q5. I thought FSM were only used when parsing "regular expressions" or in other words as the front end of a compiler.

A. 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 that one would use for an industrial control system. It is generally fairly simple in structure, even though it will use recursion, and has "final states" which express that some patterns have been found. It is an isolated module, which works like any other procedure in that it accepts an input, and gives a result back. It functions in a cosy 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 FSM should be used, and arranged to operate in a hierarchy.

Q6. How would StateWORKS handle large systems?

A. 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 FSM, each with a clearly-defined task, Why? Just imagine a rather small system using 5 FSM 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 there are 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 Q.17). This permits a complex system to be split up 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, and perhaps to several levels. In many cases, a single state machine design will be used in several incarnations, each with their own properties. Certain error-recovery processes may be designed as specific FSMs, under 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" so as 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 designed already.

Q7. 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 FSM but we have prepared a short course for you, which will equip you to work with them.

Q8. What is StateWORKS?

A. StateWORKS is a tool which 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 which can become hard to manage in a very complex situation. 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 which the project will need, and developed separately. This is done at a more abstract level than the writing of 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 in fact 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 Data Base" which is a part of StateWORKS. The RTDB then supplies what we call "virtual inputs" to influence the behaviour 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 as servers, depending on the mechanisms preferred by the developer, and the facilities specific to the programming languages he wishes 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 the complexity of the system. 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 to other state-diagram based tools, is that, once the state machines are all 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 which 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 then fully implement, the specification.

Q9. But suppose that I need to patch the code afterwards?

A. You must not even think of it. If you use StateWORKS, you can not 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 of very complex code is one of the most dangerous pastimes that we know about, 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 the more unusual situations which you did not test, and these are more easily avoided if you work at the system specification level, and of course do some simulations if you want to check out all the possibilities. The high-level documentation, as expressed by the state diagrams and associated text, will then always correspond to the reality, and this 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 some brilliant programmers. But at what a cost in time slippage, late nights, stress for the "managers", etc.! And 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".

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

A. In a sense you are correct, but the StateWORKS executor has little in common with the 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 efficient execution. The "virtual environment" in which it functions obliges the expressions governing its nature to be made out of 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.

Q11. I know something about FSM and wonder which Model is used by StateWORKS?

A. 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 which depend only on the current state, while the Mealy model generates outputs which are a function of both the current state and the inputs. When implemented in hardware, the Moore model may make the generation of outputs simpler, particularly if the digital embodiment of each state name or code is carefully selected, but they may require more states than the equivalent Mealy machine. In software, the differences become more academic, and in fact StateWORKS combines the features of both models.

Outputs, which are called "actions" in StateWORKS to make them more general in nature, can be generated when a FSM enters a given state (entry action), or alternatively when it leaves a given state (exit action). The first corresponds to the Moore model, while the second is not foreseen in the theoretical models but stems rather form an engineering practise. 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 of some sort, when the FSM is in a specific state, without causing a state transition. This is a classical case of a Mealy model, and in some instances it can 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 done when a transition is performed..

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

Q12. You mentioned UML. Does StateWORKS resemble it?

A. StateWORKS shares the ideas of UML in that it encourages the system architects to work at the level of the system description in state-diagram format. But UML like most other CASE tools, only generate 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 the automatic generation and validation of code.

In the book "Mastering UML with Rational Rose", to take just 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 event from the past. This is the way to ensure that the total system behaviour is captured in FSM models, and not in code. Otherwise we shall have the recurrent problem of re-engineering software from old and generally impenetrable, source code.

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

StateWORKS is a tool, not only for the systems analyst in his ivory tower, but for the guys at the sharp end, who are writing the software. StateWORKS FSM models can, and must, take into account all the tricky details which are never brought out in UML models, but need to be put in the software when it is produced. This means that StateWORKS is used very effectively as a tool to help to understand a specification which is initially unclear, and to develop the real specification of behaviour, to such fine detail that no design decisions are left to be made by "coders".

StateWORKS has much in common with Agile Methods in the way it should be applied.

Q13. How easily is StateWORKS ported to various environments?

A. Although an early version was written in Concurrent Pascal, the current version is in C++. The most highly-developed I.D.E. and run-time environment has been developed for Microsoft Windows 8/7/XP. The run-time system is developed by means of a StateWORKS Library (in C++) and this is also applicable to Linux and other (real-time) Unix-derived operating systems. It is always possible to apply StateWORKS to disc-less embedded target systems.

Perhaps StateWORKS could not be used in the very smallest systems, but major elements have been used on small, embedded control systems, using the Zilog Z280 processor. And there is even an example of a small project, using some 1500 words of program memory in a Microchip PIC 16F873 micro-controller, which was programmed in assembler but used the basic StateWORKS concepts to great advantage.

Q.14 What about high-availability hot-standby systems?

A. The concentration of data defining the state of a system, as the states of all finite state machines which compose it, and the current input-output stimuli, in the form of the Real Time Data Base of StateWORKS, makes the task of shadowing an active system by the potential standby system easy to organise.

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

A. I suppose you are doing something like call set-up for V5. The problem in dealing with that sort of application is the system overhead usually needed to create a new finite state machine, which can limit performance. Well, we looked into that, and a special version of the "executor" has been developed, to deal with the dynamic creation and destruction of large numbers of identical state machines, which exist as parameters in the real-time data base. So StateWORKS can handle that sort of project more efficiently than can current practice in the telecoms industry.

Q.16 Which kind of action should I use?

A. The state machine model used by StateWORKS allows you to use entry, exit and input actions. Using only entry actions means that your state machine model is of the Moore type. Using input actions means that your state machine is of the Mealy type, The most comprehensive state machines are of the Moore type. The mix of Moore and Mealy model minimizes the number of states. So, what is the best solution?

As a general rule based on experience we will suggest the following: try to keep a certain design philosophy in your project. This means that you should think about the behaviour using a certain pattern, like for instance: the state machine enters the state, does something (entry actions) and waits for the reaction of the I/O system or other state machines. This would correspond to the Moore model which should be preferred in most situations. Do not overuse the StateWORKS possibilities by using all possible actions. Avoid exit actions which should be only used for auxiliary activities, like for instance stopping timers. If you use several different actions you may minimize the number of states but maybe you will complicate the problem as the state machine behaviour becomes more difficult to understand.

Q.17 How should I build a system of state machines?

A. One of the most important aspects of StateWORKS is the way in which it helps you deal with this situation, as mentiuone in the anwswer to Q.6 above. We recommend a hierarchical structure for most situations. The StateWORKS interface among state machines supports it: the Master sends commands to the Slaves which "display" their states to the Master. Of course, you can use the interface to build less rigorous systems of cooperating state machines. We are convinced that except in very rare situations (see a case study) there are no reasons to design a non-hierarchical system. A hierarchical system is easier to understand and design as it has a certain organisation. A totally free system where each state machine communicates with any other state machines can not work properly as we are not able to understand what is going on in the system.

Q.18 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 which shall be executed always in case a state is entered. So the execution of the action depends only on the current new state and occurs only after a state transition.
Input Actions:
For each state one or more actions can be defined which shall be executed always in case certain conditions are true. So here no state transition is required. The execution of the action depends on the current state and input.

Moore FSM uses only Entry Actions. This causes a very clear behaviour: any time the FSM changes its state, something can happen and only then.

Mealy FSM uses only Input Actions. The behaviour is not so easy to understand because actions are not necessarily bound to state transitions. Mealy FSM is usually more compact (less states) than Moore.

We recommend working with mixed but Moore based FSM. This means that we design a Moore FSM and use Input Actions only for certain state transition irrelevant things like for instance a log/alarm generation. In such a way we reduce the number of states (in a pure Moore model we would need for each log/alarm a new state).

See also the technical note.

References

There are many books and papers which treat the state machine topic. We could have tried to make an exhaustive list of publications or we could make a list of suggested titles. Internet simplifies the search for publications. So, we do not want to compete with Internet search machines and we have chosen the other approach: just to make few recommendations. The danger is that such references are subjective. But for the first trial it might be better to read the few publications which we recommend, instead of searching for the best one in thousands of titles delivered by search machines. You can always do the search. Consider this list as help in getting started.

General

State machine: [S1] J. Caroll, D. Long, Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall, Englewoods 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 on-line at: http://www.embedded.com/2000/0012/0012feat1.htm)

StateWORKS and VFSM

[SW1] F. Wagner, "VFSM Executable Specification", Proceedings of the IEEE International Conference on Computer System and Software Engineering. The Hague, The Netherlands, 1992, pp.226-231.
[SW2] F. Wagner, The Virtual Finite State Machine: Executable Control Flow Specification. Rosa Fischer-Löw Verlag, Gießen, 1994.
[SW3] A. R. Flora-Holmquist, J.D. O'Grady, M.G. Staskauskas, "Telecommunications Software Design Using Virtual Finite-State Machines", Proceedings of the International Switching Symposium (ISS ,95). Berlin, Germany, 1995, pp. 103-107.
[SW4] A. R. Flora-Holmquist, E. Morton, J.D. O'Grady, M.G. Staskauskas, "The Virtual Finite-State Machine Design and Implementation Paradigm". Bell Labs Technical Journal. Winter 1997, pp. 96-113. (Available on-line at: http://www3.interscience.wiley.com/cgi-bin/abstract/97518916/ABSTRACT)
[SW5] F. Wagner, P.Wolstenholme "Real-Time Software Design Tool: Applying Lessons from LEO", The IEE Computing & Control Engineering, February 2003.
[SW6] F. Wagner, P.Wolstenholme "Modeling and Building Reliable, Re-usable Software", MDA workshop at ECBS'03, Hunstville, April 2003.
[SW7] F. Wagner, P.Wolstenholme "Closing the Gap Between Software Modelling and Code", Engineering of Computer -Based Software at ECBS'04, Brno, April 2004.
[SW8] F. Wagner, P.Wolstenholme "Misunderstandings about state machines", IEE August 2004.