Inverting Finite State Machines (FSM)


This page focus on

  1. a very simple form of specify transitions for an FSM
  2. the ability to Invert a (server) FSM to get a (client) FSM interacting with each other
  3. elaborate examples (poor Bob and his rich aunt Alice, DHCP server, rebuffering and your own? FSM in a set of interactive Usecases

Introduction to FSM and inverting

The FSM is a very established form of specification and implementation of technical solutions for hardware and software especially in the state full environments.

This page will focus on a new aspect: How to generate FSM peers. Or partners. Or complements. Or mirrors. Or inverters. Or conjugates. To my knowledge there is not any names for one FSM talking to another which is a formally inherited FSM.



If a protocol, a speech act, is specified using FSM for the behavior of one part then, of course, the other part could also use an FSM to describe its behavior. And then came the idea up if it was possible to use the formal FSM for the server to create an inverted FSM for the client. You get two talkative FSM's from one FSM specification!

This mechanism how to programmatically create an inverted FSM to "main" FSM is the very issue on this site


This page walk you through what's required to invert an FSM and there is also an we page with Usecases Fore more background on FSM look into Wikipedia or similar sources.

Examples of FSM usage

Definitions for the FSM

We need to make some definition. Most of them are classic


One need language to specify a protocol. It must also be possible to verify a solution towards a specification. And that must be declarative as much as possible and contained in one manageable source.

I prefer to use the first normal form like the CSV format. Both early in the process but also as a robust - but not always sufficient documentation





A minimal example could look like as CSV

    State, Event,      NextEvent
    Init,  FirstEvent, Wait4
    Wait4, StopEvent,  Final
    Wait4, Work,       Wait4
    Final, anyevent,   Final


There are a lot of ways to visualize an FSM. But why must it bee pleasant for the eye? I think that by emulating a use case towards a running FSM you can decide whether it will conform to the desired function. There are several profession involved in communication and they have different demands during the development and support. It is important to be able to utilize just one source for each visual drawing.

-tty cvs source json?

out matrix of different kind also generic


Here we focus on proper and correct specification and behavior but leaving most aspects on implementation in different run time environment like threading, asynch, synch

Extending a bit


First we extend our specification. We must have the possibility to check events and make some decision like what do answer when a certain resource is fully utilized like the amount of available IP addresses in a DCHP server etc. This mechanism is called guard in UML and many other domains

Here we introduce guard as a function to be called and giving a result back to the machine. Depending on the outcome the machine rolls on

    State Event      GuardResult     NextEvent
    Init  FirstEvent Full            Final
    Init  FirstEvent NotFull         Wait4
    Wait4 StopEvent  OK              Final
    Wait4 StopEvent  BuffersNotEmpty Wait4
    Wait4 Work       AlWaysOk        Wait4
    Final anyevent   OK              Final


This page is about Speech Acts so the FSM must listen on Event and talk through Output. So we add another (Output) column like following

    State Event      GuardResult     Output    NextEvent
    Init  FirstEvent Full            FULL      Final
    Init  FirstEvent NotFull         OK        Wait4
    Wait4 StopEvent  OK              OK        Final
    Wait4 StopEvent  BuffersNotEmpty NotEmpty  Wait4
    Wait4 Work       AlWaysOk        OK        Wait4
    Final anyevent   OK              nooutput  Final

The Output value can be 'nooutput'. This is required when we have a communication which is not of ping-pong kind but when one peer will send a set of messages before getting an answer from the other peer.


FSM are often used in communication system where components are sharing external resources. An invocation is often not a single call path in the cpu. Therefore responses might be delayed. However one want's to restrict the delay time. But also limit the usage of certain resources for a certain time

Local event injection

In order to get something done then the client FSM has a user or program must invoking it. It is not a closed box. Than it's meaningless. So we must be able to specify external call-in.

Initial State

Final State

Client reduction and Usecase

The inverting process

This function will take an existing (server) FSM and produce a new (client) FSM which will be able to communicate with the (server) FSM. Why specify the server FSM as a base? That is because a server must be able to service all scenarios but a client might use a subset scenarios.

The use of inverted might not be the most obvious. Perhaps complement, mirror, conjugate, peer, opposite, match could be used. It is all about conversation machine-machine following rules.


  1. Ensure there is one initial state in the FSM. That is one state which will never be reached through a transition. (That state is not in the nextstate column).

  2. Ensure there is one final state in the FSM. That state has no transitions to another state but only to itself. It will probably accept transitions with any events.

  3. Specify the FSM through a set of rows each containing

  4. Paste this specification into XXX and hit the Invert button