Mealy vs. Moore… You decide.

(Frame is a new Domain Specific Language (DSL) focused on enabling developers to easily create programs using automata. See the Frame documentation as well as Getting Started With Frame to find tools and other resources to explore the Frame language.)

This article is part of a series I will be writing to explore (and remind myself of) fundamental computer science concepts from the perspective of automata. The reason for this particular (and peculiar) lens is to publicize the Frame System Design language, a new language focused on enabling developers to easily create programs using automata. See Getting Started With Frame to find tools and other resources to explore the Frame language.

La Machines

Mealy and Moore Finite State Machines are two classes of state machine transducers. Mealy machines generate output as a byproduct of a transition between two states while Moore machines generate output strictly based upon the state they are in.

My examples for this article will come from a tutorial article on the subject and will show the implementation of these examples in Frame language. Another good resource is this video explaining the concepts from an electronics, rather than theoretical, perspective.

Let us examine Frame implementations of these two types of machines.

Mealy Machines

As previously mentioned, Mealy machines generate output during a transition between two states. In Frame we can implement this by calling a “setOutput(x)” action before performing the transition to the new state:

$Q0
      |i_0| 
           setOutput(0) 
           -> "0/0" $Q1 ^

Above, when the machine is in the $Q0 state and recieves an i_0 event (standing for input 0), the event handler will set the output to be 0 and then transition to state $Q1. The “0/0” is the label for the transition (see diagram below).

Below we can see the full Frame system specification of a Mealy machine corresponding to the article’s example:

fn main {

    var machine:# = #MealyMachine()

    machine.i_0()
    machine.i_0()
    machine.i_1()
}

#MealyMachine

    -interface-

    i_0
    i_1

    -machine-

    $Q0
        |i_0| 
            setOutput(0)
            -> "0/0" $Q1 ^
        |i_1| 
            setOutput(0) 
            -> "1/0" $Q2 ^

    $Q1
        |i_0|
            setOutput(0) 
            -> "0/0" $Q1 ^
        |i_1| 
            setOutput(1) 
            -> "1/1" $Q2 ^

    $Q2 
       |i_0|
            setOutput(1) 
            -> "0/1" $Q1 ^
        |i_1| 
            setOutput(0) 
            -> "1/0" $Q2 ^

    -actions-

    setOutput [value] {
        print(value)
    }
##

Here is the state machine diagram corresponding to (and generated from) the code above:

You can run the program here and can view the full code listing here.

Moore Machine

In contrast to Mealy machines, Moore machines emits output when entering a state, not when transitioning between states.

$Q0
        |>| 
            setOutput(0) ^
        |i_0| 
            -> "0" $Q1 ^
        |i_1| 
            -> "1" $Q2 ^

Above we can see that the enter event handler sets the output and that the two transitions do not.

fn main {

    var machine:# = #MooreMachine()

    machine.i_0()
    machine.i_0()
    machine.i_1()
}

#MooreMachine

    -interface-

    i_0
    i_1

    -machine-

    $Q0
        |>| 
            setOutput(0) ^
        |i_0| 
            -> "0" $Q1 ^
        |i_1| 
            -> "1" $Q2 ^

    $Q1
        |>| 
            setOutput(0) ^
        |i_0| 
            -> "0" $Q1 ^
        |i_1| 
            -> "1" $Q3 ^

    $Q2 
        |>| 
            setOutput(0) ^
        |i_0| 
            -> "0" $Q4 ^
        |i_1| 
            -> "1" $Q2 ^


    $Q3 
        |>| 
            setOutput(1) ^
        |i_0| 
            -> "0" $Q4 ^
        |i_1| 
            -> "1" $Q2 ^

    $Q4 
        |>| 
            setOutput(1) ^
        |i_0| 
            -> "0" $Q1 ^
        |i_1| 
            -> "1" $Q3 ^

    -actions-

    setOutput [value] {
        print(value)
    }
##

Here is the state machine diagram corresponding to (and generated from) the code above:

You can see the program run here and find the full code listing here.

Conclusion

Frame syntax helps to highlight the differences between Mealy and Moore machines. As demonstrated, Frame naturally supports both approaches so, with Frame, you don’t have to choose!

(or even remember)