I'm currently studying formal methods in software engineering related to state machines, specifically Mealy machines. This made me wonder how relevant Mealy machines really are for practical applications. I realize that a lot of applications are based on state machines which can at some level be modelled as Mealy machines. For example, network protocols like TCP or SSH. However, these usually contain semantic aspects not covered by Mealy machines. Most commonly in network applications, this includes their sensitivity to message timings. To model such applications with a Mealy machine, timing would need to be semantically abstracted (e.g. by adding timeouts as special inputs). I'm searching for examples of applications which can be modelled as Mealy machines without such semantic trickery. Are there any prominent applications of actual Mealy machines in the real world, or are they merely useful abstractions from which to advance into more complex modelling semantics?

  • 1
    $\begingroup$ You probably want to read Mealy’s paper "A Method for Synthesizing Sequential Circuits". $\endgroup$ Jun 14, 2023 at 22:28
  • 1
    $\begingroup$ One that you probably use every day without realising it is instruction decoding and predecoding in CPUs. You can think of, for example, instruction start/end detection as a finite state transducer on the instruction byte stream. $\endgroup$
    – Pseudonym
    Jun 15, 2023 at 2:24
  • $\begingroup$ Thanks for the suggestions. I know there's many use cases for Mealy machines in the context of hardware design. But I'm looking specifically for software applications. $\endgroup$ Jun 17, 2023 at 14:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.