« | »

What is a state machine?

Our web site contains several technical notes and papers that discuss some aspects of software engineering associated with the concept of a finite state machine. On introducing our blog we have decided to present you a few topics covered by a group of our documents. We started with the Mealy and Moore models of a finite state machine, honoring the fact that it is a favorite topic according to visitors’ statistics. The topic that we would like to present you today is “What is a state machine”.

The concept of a state machine is old; its definition belongs to the basics of Automata Theory. In principle it seems to be a simple definition and requires understanding of the “state” concept. In spite of its simplicity the concept has been deformed, corrupted, misunderstood and up now the well known misunderstandings about a state machine result in a relatively modest use of the state machine idea in the specification and design of software. In our publications we try to indicate that a state machine is so well defined (see for instance the book or the technical note and the the already mentioned document about Moore and Mealy models) that it does not require re-definitions or (mis-)interpretations, especially that:
- a flow chart is not a state machine
- a Petri net is not a state machine
- a statechart is not a state machine
- there is no need to define an incomplete state machine under a new name (see for instance the technical note)
- it is possible to create a complex control system modeled by a system of state machines
to name only some topics discussed in our documents.
We are convinced that the concept of a finite state machine is one of the strongest ideas in the world of modelling control tasks in general and specifically in the design of a software control flow. A typical implementation of software control flow using the if-then-else and switch like mechanisms supported by numerous flags is a primitive style of development difficult to understand and accept in the 21 century.

Tags: , , , ,

5 Responses to “What is a state machine?”

  1. Joe says:

    I don’t know if this blog is still active or not. I’ve read “state machine misunderstandings”. That clarifies a bit. However, there are some questions here. How to apply state machine into multi-thread computing, especially if synchronization among threads is needed?
    And another question is that if the computer only has only one CPU core, is it possible to merge multiple threads/processes into single process through the use of FSM, since traditionally, each process/thread has its different mission and timing?

  2. ferdinand says:

    We tend to overuse threads. We should use them if we need them but no more. There is no explicit requirement that each state machine has to run in a separate thread.
    A single state machine is seldom a true problem, a system of state machines is a problem. The major challenge is to design a system of state machines which is a solution of a logical control problem and not a source of difficulties that are created by putting each state machine in a separate thread. Any complex control problem requires communication among involved state machines. If we design a set of state machines each solving a partial problem without having in mind from the beginning the entire logical structure we may end in a difficult fight with deadlocks and nondeterministic behavior by implementation.
    Keeping state machines in one thread simplifies a lot. The idea, as realized in StateWORKS run-time system, is then: the behavior represented by a system of state machines is realized by an executor (a kind of decision machine in one thread) while all time consuming data processing input/output actions are moved into threads. This solution guarantees that the system is in its control path very fast as the data processing tasks are not in its scope.
    This concept is of course realized without any difficulties on a single CPU without thread resources. The only difference is that the control path has to wait until its data processing tasks are carried out.

  3. John M says:

    Coincidence!! I was dealing with exactly this earlier today in my system development!
    As in your post indicates, Ferdinand, I concluded that splitting the control logic across multiple asynchronous processes (threads) is more trouble than it’s worth. (Happy to have confirmation!!)
    One still has to deal with issues like deadlocks and loops as in : Master VFSM issues a command to a Slave VFSM that then changes it’s state that the Master detects causing it to issue another Slave command and so on and on. These are much easier to deal with in a single execution engine – even if it is iterative or recursive – than using cross thread messaging!
    In my application I need to backtest control logic using previously captured external timestamped input events (simulating external system reactions to control outputs where needed). The most efficient way to do that is move simulated time from event to event – practically impossible if two asynchronous parts of the control logic can affect each other’s actions per my loop example above. (Don’t worry, Mr Ferdinand, I’m making absolutely sure the control processing itself is *not* event driven – only input changes are handled like that!)

  4. Joe says:

    Mr Ferdinand:
    Thank you very much for your reply though I have not figured out the way to apply state machines to my work. And yes, I am quite in the event-driven ways. But I am tired of many flags and if-else. I really hope the state machine(STATEworks) can really complete whole project/software model before coding, as it is claimed. The idea of not reinveing wheels is what I like most and especially when it can really match a state machine to a software model.
    Desktop computers are now equipped with multi-core CPU but I think fewer processes/threads would be good and even perfect if number of processes or threads equals to the number of CPU cores. But in another way, while developing a software system, I think multiple processes are still needed if more than two developers are involved. Anyway, I would like tobuy some book (from StateWorks) from Amazon before I make wrong statements(Or maybe too late :) ).

  5. ferdinand says:

    I am glad that my comments could help you a bit.
    You write that you are “tired of many flags and if-else”. We are all tired with this jungle of conditions we build into our programs that make them difficult to understand and cost a huge amount of time (and money but normally we do not bother about it until there are institutions that are ready to pay for our exercises). It is interesting that we still believe that we get our software quickly to work with some simple solutions or tricks. I observe it on my behavior. As a rule I try to design my software (using in most cases the concept of a state machine). But sometimes I behave also as a teenager. An example: for test purposes we have in StateWORKS the SWQuickPro monitor that displays all details of RTDB objects and can be used to manipulate objects. Some time ago we decided to extend its functionality by automatic testing features (some informations about it are described in http://www.stateworks.com/technology/TN20-Testing-with-StateWORKS). I was involved in that project and decided just to “expand” the existing software adding “here and there” missing code. The functionality of that monitor part seemed to be simple: read a command file and then execute the commands line by line. In addition, these operations should have been affected by buttons: NEXT, RUN, RUN Continuous and STOP. This simple task appeared soon quite complex if you think about all constrains: missing file, error in command, missing or erroneous operand, etc. The task become quite obscure at the latest when we decided to introduced pseudo-commands: Delay and Wait For Event. Eventually, I got it working but it was a terrible code based on flags and if-then-else. I watched some time this software disaster and when I wanted to change something I found that I did not understand how and why it works. Eventually, I was completely fed up and wrote the software again starting from a state machine model. It took me a month or so but now we have software that I understand and at any time I can change it without fear of side effects. It would be relatively easy for another person to take it over and continue as it is described by a specification which corresponds in 100% to the code.
    The complexity of a problem we are to solve in software is as it is: it is determined by customer requirements. We cannot change/simplify it, we have to fulfill it. As software developers we decide about the complexity of its implementation: we may find a solution that exhibits the complexity of the application but no more. We may produce a software monster which complexity exceeds by far the complexity imposed by the requirements.
    I believe that without modeling and specification it is impossible to develop a good software.
    There is one general problem with any formal or quasi-formal methods: they require some knowledge, they demand learning from us. Normally, we do not have time for such “useless” activity, we just have a project deadline. There are many programmers who believe that their common sense supported by programming skill is all they need to solve any software problem. Sometimes it works but the result is poor.
    Last but not least: Especially in the beginning, supporting the software development by modeling with finite state machines may be as difficult as the fight with flags and if-then-else statements (see my comments about complexity) but the results are better if the software has a sound model based skeleton.

Leave a Reply

You must be logged in to post a comment.