Department of Computer Science Course: CS 3724

State machine models

Up to this point, we have implicitly considered only one model for a state machine; a model in which the outputs are a function of both the present state and the input. This model, shown pictorially in Figure 2.28 is called the Mealy model for sequential devices. It is a general model for state machines, and assumes that there are two types of inputs; clock inputs and data inputs. The clock inputs cause the state transitions and ``gate'' the outputs, (so the outputs are really ``pulse'' outputs; i.e., they are valid only when the clock is asserted). The data transitions determine the values of next-states and outputs. Essentially, the clock inputs control the timing of the state transitions and outputs, while the data inputs determine their values.

Figure 2.28: The Mealy model of a state machine

So far, the state diagrams we have drawn correspond to this model; we have labelled the transitions with the inputs which cause the transition, and the output corresponding to the transition.

Another, model for state machines is the Moore model, in which the outputs are associated with the states of the device. In the Moore machine, the outputs are stable for the full time the device is in a given state. (The outputs are said to be ``level'' outputs, and are valid even when the clock inputs are not asserted.) Again, there are two types of inputs, clock inputs and data inputs. In this case, however, the clock inputs only directly enable the state transitions. In this model, the transitions are functions of the present states and inputs, but the outputs are functions of the states only. Figure 2.29 shows a pictoral representation of the Moore model of a state machine. (The Moore model describes state machines like the traffic light controllers we have seen as ASM diagrams in a very natural manner.)

Figure 2.29: The Moore model of a state machine

Figure 2.30 shows a state diagram for the Mealy machine derived earlier which produces a 1 as output whenever the sequence 0101 is input. This machine has four states, and the ourtrputs are associated with the inputs to the strate machine.

Figure 2.30: Mealy state machine for sequence 0101

Figure 2.31 shows a state diagram for a Moore machine which performs the same function. Note that a state diagram for a Moore machine is labelled differently from a Mealy machine state diagram; the transitions are labelled only with the inputs which cause the transition, while the states are labelled with the corresponding outputs. (The output is a function of the state only, and does not depend directly on the input.)

Figure 2.31: Moore state machine for sequence 0101

Comparing the Mealy and Moore state diagrams in Figures 2.30 and 2.31 respectively, it is clear that the diagrams are very similar for states A, B, C and D. State E is a ``new'' state, because the output of 1 must be associated with some state. In fact, state E is equivalent to state C in the Mealy diagram -- Mealy state C has been split into two Moore states, one (C) with output 0, and one (E) with output 1. They are equivalent in the sense that the outputs from both Mealy state C and Moore state E (and Moore state C, too) have the same next-states for the same inputs.

Note that state C was the only Mealy state in which the incoming arcs (or arrows) correspond to different outputs. Moreover, the state which was ``split'' retained all transitions to the corresponding next-states in the Mealy machine. (In this example, all of the other states are associated with only one output.)

In general, from this observation, it is possible to convert any Mealy type machine into an equivalent Moore type machine, and vice-versa. First, we must define what we mean for two state machines to be equivalent. Two state machines are said to be equivalent if they produce exactly the same output for all inputs. Consequently, to derive an equivalent Moore machine from a Mealy machine, it must be possible to guarantee that the two machines produce the same output after any arbitrary input string has been input. This can be done by splitting all the Mealy states corresponding to different outputs, and ensuring that these states are connected to next-states which correspond to equivalent states in the original Mealy machine.

As a slightly more complex example, the Mealy machine specified by the following state table, where x is the single external input, and y is the output, and having a state diagram as shown in Figure 2.32 can be converted into a Moore machine as follows:

Present State	Next State		Output, y, for
	x=0	x=1	x=0	x=1
A	C	B	0	0
B	A	D	1	0
C	B	A	1	1
D	D	C	1	0

Figure 2.32: Mealy state machine

Each state with different output values associated with transitions into the state is split into states corresponding to each different output; e.g., state B has a transition from state $A$ with an output of 0, and from state $C$ with an output of 1. State B is therefore split into two states, $B_0$, with an output of 0, and $B_1$, with an output of 1. Every transition to B with output 0 goes to $B_0$; every transition to B with an output 1 goes to $B_1$. The next-states of $B_0$ and $B_1$ are exactly the same as for B. Similarly, state D is split into two states, $D_0$ and $D_1$ because an output of 0 is associated with a transition to D from B, and an output of 1 is associated with a transition to D from D.

The state table becomes the following, corresponding to the state diagram shown in Figure 2.33:

Present State	Next State		Output		State
	x=0	x=1	x=0	x=1	output
$A$	$C$	$B_0$	0	0	1
$B_0$	$A$	$D_0$	1	0	0
$B_1$	$A$	$D_0$	1	0	1
$C$	$B_1$	$A$	1	1	0
$D_0$	$D_1$	$C$	1	0	0
$D_1$	$D_1$	$C$	1	0	1

Here we have added a column called state output, which is the output the device has while in a given state. The output no longer depends on the input, x. In fact, the columns in the table associating the output for the inputs are now redundant (and should really be omitted).

Figure 2.33: Moore state machine

We can see that the Moore machine accepts the same input sequences as the Mealy machine we started with, and produces the same output sequence. In addition, it produces the output 1 when started in state A, without having any input sequence. i.e., a Moore machine accepts a zero length sequence, called a null sequence, and produces an output (while in its initial state.) If we wish, we can add a new state $A_0$ as the initial state, which produces a different output, say, 0, indicating that the machine is in its initial state. (There will be no transitions back into this initial state.)

Present State	Output	Next State
		x=0	x=1
$A_0$	0	$C$	$B_0$
$A_1$	1	$C$	$B_0$
$B_0$	0	$A_1$	$D_0$
$B_1$	1	$A_1$	$D_0$
$C$	0	$B_1$	$A_1$
$D_0$	0	$D_1$	$C$
$D_1$	1	$D_1$	$C$

Figure 2.34: Completed Moore state machine

Note that, in general, any Mealy machine with $N$ internal states and $P$ outputs can be converted to a Moore machine with at most $P \times N+1$ states. (The Mealy machine and its corresponding Moore machine will be equivalent, in the sense that both will give exactly the same output for all possible input sequences.)