Mealy and Moore machines

Why it exists

A DFA answers yes or no. Many machines must compute: add two numbers one bit at a time, find the two's complement of a binary number, flag every occurrence of a pattern in a stream, output the remainder of the number read so far. A finite-state transducer is a finite automaton that writes an output symbol as it reads. Two models are used: in a Mealy machine the output belongs to the transition, in a Moore machine it belongs to the state. They are the models behind the synchronous circuits of digital logic (state machines). GATE asks: what does this machine output on this input, what does it compute, how many states are needed, convert one model to the other, the shortest input that reaches a state with a given output.

Prerequisites

You need DFAs (DFA): states, transitions on every symbol, a run on a string. The minimisation technique is the one of DFA minimisation.

Precise definitions

A Mealy machine is a tuple $(Q, \Sigma, \Delta, \delta, \lambda, q_0)$ with a finite set of states $Q$, an input alphabet $\Sigma$, an output alphabet $\Delta$, a transition function $\delta : Q \times \Sigma \to Q$, an output function $\lambda : Q \times \Sigma \to \Delta$ and a start state $q_0$. On the input $a_1 a_2 \dots a_n$ it goes through states $q_0, q_1, \dots, q_n$ with $q_i = \delta(q_{i-1}, a_i)$ and writes $\lambda(q_{i-1}, a_i)$ at step $i$. The output has exactly $n$ symbols.

A Moore machine has the same parts except $\lambda : Q \to \Delta$: the output depends only on the state. The machine writes $\lambda(q_0)$ before reading anything and then $\lambda(q_i)$ after step $i$. The output has $n + 1$ symbols. (Some books drop the output of the start state so that both models give $n$ symbols; then a Moore machine is a Mealy machine whose output is the same on all edges entering a state. State the convention in an answer.)

There are no accepting states: a transducer computes a function from input strings to output strings, not a language. A DFA is the special case of a Moore machine with outputs accept and reject.

Equivalence. Two machines are equivalent if they compute the same function. A Moore machine and a Mealy machine are compared after dropping the first symbol of the Moore output.

How it works

Reading a Mealy diagram

Edges are labelled input/output. The machine below reads a binary number from the least significant bit and outputs the two's complement: it copies bits up to and including the first 1, then inverts every bit after that.

Why it works: the two's complement is the one's complement plus 1. Inverting every bit turns the trailing 0s into 1s and the lowest 1 into 0; adding 1 then turns those trailing 1s back into 0s and the 0 into 1. The net effect: the bits up to and including the lowest 1 are unchanged, every bit above it is inverted. Reading from the right, the machine needs only one bit of memory: "have I seen a 1 yet?". That is why 2 states suffice. The same input gives output $0101011$, which is $106 = 128 - 22$, the two's complement in 7 bits of $0110100$ read as $22$.

Other Mealy machines of the same kind, all with 2 states: add one (state "carry pending", it turns trailing 1s into 0s and the first 0 into 1, then copies) and the serial adder (the input symbol is a pair of bits, the state is the carry). The carry flip-flop of a serial adder in hardware is exactly this second state.

A Mealy machine in C

A Mealy machine is two tables indexed by state and input symbol: the next state and the output symbol.

#include <stdio.h>
#include <string.h>
 
struct mealy {
    int next[3][2];
    char out[3][2];
};
 
static void run(const struct mealy *m, const char *w, char *out) {
    int q = 0;
    size_t n = strlen(w);
    for (size_t i = 0; i < n; i++) {
        int a = w[i] - '0';
        out[i] = m->out[q][a];
        q = m->next[q][a];
    }
    out[n] = '\0';
}
 
int main(void) {
    /* two's complement, least significant bit first: state 0 = copy, state 1 = invert */
    struct mealy twos = { {{0, 1}, {1, 1}, {0, 0}}, {{'0', '1'}, {'1', '0'}, {'0', '0'}} };
    /* detector of 101: state k = length of the longest suffix read that is a prefix of 101 */
    struct mealy det = { {{0, 1}, {2, 1}, {0, 1}}, {{'0', '0'}, {'0', '0'}, {'0', '1'}} };
    char out[32];
 
    run(&twos, "0110100", out);
    printf("two's complement of 0110100: %s\n", out);
    run(&det, "1011010", out);
    printf("detector of 101 on 1011010: %s\n", out);
 
    int good = 0;
    for (int v = 0; v < 256; v++) {
        char in[9];
        for (int i = 0; i < 8; i++) in[i] = ((v >> i) & 1) ? '1' : '0';
        in[8] = '\0';
        run(&twos, in, out);
        int r = 0;
        for (int i = 0; i < 8; i++) r |= (out[i] == '1') << i;
        if (r == ((256 - v) & 255)) good++;
    }
    printf("correct two's complement for %d of 256 eight-bit inputs\n", good);
    return 0;
}

two's complement of 0110100: 0101011
detector of 101 on 1011010: 0010010
correct two's complement for 256 of 256 eight-bit inputs

Mealy against Moore

The same task, a detector that outputs 1 exactly when the last three symbols read are $101$ (overlapping occurrences count), as a Mealy and as a Moore machine:

The Mealy machine has 3 states and the Moore machine 4: the Moore machine needs a state that means "just completed $101$" so that the output 1 can be attached to a state, while the Mealy machine puts the 1 on the transition. Running both on the same input:

Conversions

Moore to Mealy. Keep the states. Put on the edge $(q, a)$ the output of the state $\delta(q, a)$ it enters. The Mealy output is the Moore output without its first symbol. The number of states does not change.

Mealy to Moore. A Moore state must remember the output of the edge that entered it, so the new states are pairs $(q, o)$ with $q \in Q$ and $o$ an output symbol that some edge into $q$ writes (plus the start state with an arbitrary first output). At most $|Q| \cdot |\Delta|$ states are needed, and sometimes that many are.

Minimisation

Two states of a Mealy machine are equivalent if from either of them every input string produces the same output. The partition-refinement algorithm of DFAs works: start with the partition that puts two states together when they write the same output on every input symbol, then repeatedly split a class when two of its states send some input symbol to different classes; stop when nothing changes, and merge each class into one state. For a Moore machine, start from the partition by the state output instead. Unreachable states are deleted first.

The table counts the classes of a machine whose designer remembered the last three inputs to output the input of two steps ago: only the last two matter, so $8$ states shrink to $4$. Two states of a machine with $k$ states are equivalent exactly when they write the same output on every input of length less than $k$, which is why short inputs are enough to compare the states of a small machine.

For a sequence detector of a pattern of length $n$ the minimal Mealy machine has $n$ states (state $k$ means: the longest suffix read that is a prefix of the pattern has length $k$), and the minimal Moore machine has $n + 1$. The values for the patterns $101$ and $1011$ above were confirmed by trying every machine with fewer states.

Shortest input to a state with a given output

"What is the shortest input that takes the machine to state $s$ with output $o$?" is a breadth first search: explore the pairs (state, last output) in order of the length of the input that reaches them, remembering the input.

A Moore machine that computes

Reading a binary number from the most significant bit, the remainder modulo 3 of the number read so far is updated by $r \mapsto 2r + b \pmod 3$. Three states suffice, and the output of a state is its remainder:

Worked examples

Cheat box

Traps and GATE patterns

Connections

A transducer is a DFA with output, and its minimisation is the algorithm of DFA minimisation with a different initial partition. In digital logic the same machines appear as clocked sequential circuits (state machines): the flip-flops hold the state and combinational logic computes the next state and the output; the carry flip-flop of a serial adder is the second state of the Mealy machine here (adders). Standard designs of DFA design patterns (counting modulo $n$, remembering the last symbols) carry over to output machines.

PYQs

Consider a finite state machine (FSM) with one input X
and one output f, represented by the given state transition
table. The minimum number of states required to realize
this FSM is ________. (Answer in integer)

Given the following state table of an FSM with two
states A and B ,one input and one output.

If the initial state is A=0,B=0.what is the minimum length
of an input string which will take the machine to the state
A=0,B=1 with output = 1.

For a state machine with the following state diagram the
expression for the next state S+ in terms of the current
state and the input variables x and y is

The following diagram represents a finite state
machine which takes as input a binary number from
the least significant bit.

Which of the following is TRUE?

Self-check

Revision card

References