Mealy v/s. Moore

Question

What is the difference between Mealy & Moore type of finite state machines?

Solution 1

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)

Solution 2

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.

Solution 3

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.

Solution 4

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.

View more solutions

Comments

[Admin]

Can one type always be converted to the other?

[Jack]

Not from a theoretical point of view. From a practical point of view the output function in a Moore machine is a function state -> output while in a Mealy is state, input -> output. This means that if you explode every state of your Mealy machine adding the specific input for every outgoing transition you can simulate the same behaviour also if it's conceptually different.

[m33lky]

Any Mealy machine can be converted to a Moore one.

[Parham]

@dekpos: yes you can. Mealy to Moore would require splitting the each Mealy state into the number of inputs coming into it with different outputs. So if a Mealy state has two inputs with two different outputs, you would split that one Mealy state into two states in the Moore machine where each new state's output would match one of the two transition outputs in the Mealy machine. For the reverse situation you would simply move the output of the state to the incoming transitions instead. This is theoretical.

[supercat]

@Jack: Would it be correct to say that one can produce any desired Mealy machine using a combination of a Moore machine whose outputs match its state, and a purely combinatorial circuit (no feedback paths) which takes as input the inputs to the original machine along with its state outputs, and then generates the desired outputs for the circuit as a whole?

[Vinod]

@m33lky "A Mealy machine may be converted to an almost equivalent Moore machine that differs only in that the output is produced on the next reaction rather than on the current one." quoted from Lee & Seshia, Introduction to Embedded Systems, LeeSeshia.org

[maxweber]

See: stackoverflow.com/questions/5357918/…