« | »

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.

Tags: , ,

4 Responses to “What is a state machine, again?”

  1. Joe says:

    Dear sir:

    So may I say a state machine here is to connects the relations from a series of input(s) to a series of output(s)? This sounds like to centralize all/major decision logic(s) into a state machine?

    It’s not easy for me to grab the state machine idea when facing real software development. For example, if I have a TV card without hardware codec and I have a schedule recording software to record my favorite TV programs, the “scheduling” part might belongs to the state machine, the “video capture” part belongs to input system. and then the “video compression and recording” part belongs to output system?

    And not to mention sometimes UI could also be very complex and interact between real system function layer and user inputs. So in this case, the logic of UI behavior can be centralized into the state machine also?

  2. ferdinand says:

    Joe,

    Yes, a state machine concept is used to express logical decisions in the form of an understandable model.

    In general, software processes data. In simple cases the process is more or less straightforward: if you push a key 1/x the calculator is to calculate the reciprocal of the displayed value x. There are not too many decisions to be taken: a simple “if ( y != 0)” statement does probably the job. If you have a calculator with the cash register functions (compare the standard calculator available under Window) pushing the “=” key results in a different behavior depending on previous operations, i.e. the result is not uniquely defined by the input. How to define such behavior? Verbal explanations are imprecise and may be sufficient for trivial cases. Non-trivial problems require formal models: a state machine is such a model.

    Of course a single state machine can model a relatively simple case. A complex problem is best described by a system of state machines. If well constructed such a system is understandable for very large systems built of hundredths of state machines.

    Telecommunication has a tradition of specifying protocols by use of state machines. The reason is that a protocol must be completely and precisely defined; otherwise a chance to connect to a system built by another company would be null. Therefore nobody discusses there the sense of using formal definitions. In contrary to telecommunication nobody cares about the reliability of UI; we assume that the communication between a user and a machine may be defined less strictly. The result is that we are often unhappy with unreliable and from the ergonomics point of view failed UI.

    As you say, in practice software is complex. A use of state machines cannot reduce the complexity but may increase the understandability. If you work as a programmer in a team that writes a large software package you know the the quality of the programs. How easy are the programs to maintain? How well are they documented? Can they be revised, changed by other people? How dependent are the solutions on their authors? Is it possible to continue software development if a key programmer leaves the company? Positive answers to these questions depends on the software design. If the software comes into being during coding only, the answer cannot be positive: there is no way to document it thereafter. If the software development starts with a serious specification and design phases there is a chance to know at least its general structure. If the development environment forces programmers (like StateWORKS does) to introduce changes going back to the specification it produces understandable software without features hidden in the code that “discovery” requires long digging in the code.

    In your example with TV card and accompanying software the partition into state machine, inputs and outputs is probably not good. Each part you have mentioned manifests some behavior. So a design of such a system would mean to define the control path for each module in a form of state machine(s) and the entire control will be a system of interconnected state machines. Each state machine will have inputs and outputs, whereas outputs (states) of some state machines will be inputs of another state machine(s). It may sound not very clear if the state machine concept is foreign for you (as for any new, unknown thing) but if you just code it you have to built the sequential control problems into your code. Effectively, you have the implemented (invisible) state machines in your code. There are no miracles: you cannot bypass complexity, in the discussed topic the sequential nature of a control for any non-trivial software. You may only make it visible defining it formally using state machines or you just hide it in the code.

    Ferdinand

  3. Joe says:

    My question and example were not good at all but you have a good soul and tried to answer my questions. Thank you.

    How is the state machine paradigm compared to object oriented paradigm? Or can they be compared? Can the state machine paradigm helps achieve “reuse” property that programmers want, and also helps lower the impact to software development when adding new features to our software?

    Or please name some books which I should read before keeping shooting questions in the dark? Thanks again.

  4. ferdinand says:

    Comparing the state machine concept with the object oriented paradigm would not not make sense: they are different sorts. In object oriented design the class contains object data and its behavior. Of course, the behavior may be implemented in a form of a state machine. The weak point of the object oriented approach is a missing concept of the entire control system. How should the objects’ state machine communicate? How to organize the communication without ending in chaos? Therefore, object oriented design works well for software with dominating data flow but it fails to realize a complex control flow.

    An answer to that difficulty could be the separation between a control and a data flow. Then, the control flow is specified on a higher level without thinking about its coded implementation. Such systems can be coded using object oriented language. Or as we do it in StateWORKS using a ready run-time system for the control flow completed by output functions that realize the data processing and I/O handler for input/output interfacing.

    The separation of control flow and data flow increases the reuse of software. It is easier to define an abstract model of a control and it is easy to have a reusable control-less data processing module. Their re-usability stems from the uniqueness of the pure control models as well as the pure data processing modules. To have a reusable software piece that covers both data and control flow is more difficult to achieve.

    Software for which the control skeleton is built using state machines is easy to change by adding or replacing state machines. It is also easy in such system to change a data processing module without touching the control part.

    To use state machines in practice you have to understand:
    - What is a state.
    - The philosophy behind the different sort of actions (outputs).
    - How to determine control values (inputs) that condition the state transitions and input actions.
    - What problems may be encountered during specification of state machines and especially by a system of state machines (especially: deadlocks, infinite loops, unreachable states, dead states).

    It sounds simple but it is not that simple. For practical use there is no need for theoretical considerations and mathematical notations. Any theoretical discussions make sense if they:
    - Give answers to some general problems or tendencies, in that case for instance: how to get a minimal number of states, how to avoid deadlock, etc.
    - Produce results that can be used in a practice.

    For state machines, trials to get some useful results from theoretical discussions failed. Obviously, the state machine model is so simple that it is immune to any theoretical extensions. So, the major challenge is the proper design of the system of state machines and the specification of the state machines. And these activities depend on the programmer’s skill and experience.

    There are several books considering the state machine concept. Of course, I propose you our book that we recommend on our web site. I think our book is a fairly down-to-earth presentation of the concept based on years of practical use. Looking for books and papers try to avoid ones which in spite of theoretical notations and discussions cannot supply solutions for trivial problems. In addition, try to select books that say at least something useful about a system of state machines. Do not be deceived by a state hierarchy in statecharts which is a different thing than a system of state machines (apart from the fact that a statechart is not equivalent to a state machine but for marketing reason is “sold” as such and increases the confusion around that topic).

Leave a Reply

You must be logged in to post a comment.