What is a state machine, again?
For many years we have been trying to popularize the correct concept of a finite state machine. In fact, we do not invent anything, we just present a state machine as defined ca. 60 years ago. In the beginning it had been applied to a design of hardware systems as software did not exist at that time. But the concept of a finite state machine is not bound in any way to the hardware; it is just a notation to describe a behavior and as such it is not bound to the physical implementation.
Unfortunately, the state machine concept in software has been firstly used for theoretical purposes in the mathematical foundation of computer science where obviously only the event driven parser model is useful. This model assumes that a state machine is triggered by an event to do something and possibly change a state. This model applied to application software where a control systems are modeled is totally useless: in our book (Wagner F. et al.: Modeling Software with Finite State Machines) we discussed in details the limitations of that model, especially the problem of state number explosion.
A recent email has provoked us to show the solution of a traffic light controller in the Solution page on our web site. This email shows again the damage that is produced by tools which use the UML syntax for specifying state machines. The base is a statecharts idea that assumes the above mentioned parser model.
I do not want to repeat here any extracts from the book or numerous technical notes and case studies available on our web site. I would limit my comments only to two topics that are the essence of all the misunderstandings that surround the state machine concept.
1. An event is a signal that triggers the state machine to work: to do something and change a state (I do not want to go now into the different models with input action, entry actions, etc. as these are secondary issues). The conditions that determine what to do and whether to change a state is not the event itself but the value of one or more state machine inputs (see for instance Chapter 7 in the book). In the Traffic Light example the transition condition from the state Hgreen_FRed to the state HYellow_FRed is Vehicle_DETECTED & Ti_Green_OVER, i.e. the transition condition is an AND operation of two input values: Vehicle_DETECTED and Ti_Green_OVER. If you try to do it using only the event as a condition you end up in a lunatic world with a state machine inside a state, flags in a state machine, inventing “guards” on transitions, concurrencies, and so on.
2. There is very rarely a need for concurrent state machines. First of all a system of concurrent state machines makes sense only if you have a true multiprocessor system and you are able to partition the (multiple) state machine execution onto several processors. Secondly, you need to have a reason to do it. In reality you normally need three levels of parallelism: the system of state machines, the input handling system and the output handling system. The input handling system processes the inputs, makes them available to the state machines and generates events to trigger state machines if any input changes. The output handling system performs action as ordered by state machines. If those two time-consuming tasks run concurrently to the system of state machines this system is just a decision machine, to order the output handling system what to do on the basis of the actual input conditions and a state, and is very fast in operation. In such a model it is difficult to discover any motive for requiring concurrency of state machines.
Any comments will be appreciated.
4 Responses to “What is a state machine, again?”
Leave a Reply
You must be logged in to post a comment.