Mealy v/s. Moore

Moore machines are discrete dynamical systems which can be expressed using TLA+ syntax as follows:

/\ x[k + 1] = f[x[k], u[k]]
/\ y[k] = g[x[k]]

where x the state, u the input, y the output, f describes the transition relation (discrete dynamics) and g the output map (here a state labeling) and k denotes time (index in the sequence).

A Mealy machine is of a slightly more general form:

/\ x[k + 1] = f[x[k], u[k]]
/\ y[k] = g[x[k], u[k]]

Note that now g is not a state labeling any more, it is an edge labeling.

They are not equivalent, in particular Moore machines are strictly causal, whereas Mealy machines are not.

For more details, refer to Lee and Seshia, Introduction to Embedded Systems, LeeSeshia.org, page 58.

Explanation by Example / Anecdote.

This is perhaps best illustrated with an example and an anecdote.

I hate airports, and getting to them, but I love being on the plane. There are three distinct states that I have to enter into before getting on the plane:

1. State: In Taxi (event: then I pay the fare, and transition to the next state:)
2. State: In Lounge (event: wait 2 hours, and transition to the next state: )
3. State: In Plane

But what is the outcome?

In a Mealy machine, the preceding state from which you come from makes a difference - how you get somewhere is very important. In a Moore machine, how you get to a state makes no difference.

Let's add in an outcome to the above to create a Moore representation of a state machine:

Example of a Moore Representation of a State Machine:

1. State: In Taxi (event: pay fare and then transition to the next state). (Outcome: unhappy).
2. State: In Lounge (event: wait 2 hours, and then transition to the next state) (outcome: unhappy)
3. State: In Plane (outcome: happy).

With a Moore representation the outcome is attached directly to the state. With a Mealy representation - the particular outcome/output depends on where you have come from. For example, if I can get to the plane without having to catch a taxi and wait in the lounge, then I would be happy. Inputs make a difference. The where you come from is important. A Mealy representation state machine allows for this to be shown in the diagram. In other words, the output/outcome is shown OUTSIDE the state, during the transition.

Moore machine output is a function only of the state of the machine, Mealy machine output is a function of the state of the machine and its inputs.

In a Moore machine the output produced is associated to the current state of the machine and on it only. In a Mealy machine, instead, it is associated to both a state and a specific input.

From a practical point of view you have that output is placed on states in a Moore machine (so every state has its ouput), while on the latter you have outputs on transitions (so an ouput is decided from the current state AND the outgoing transition)