Mealy vs Moore machine: a 1011 detector built the Mealy way

A Mealy machine is a state machine whose output depends on the current state and the current input; a Moore machine's output depends on the state alone. This live circuit is a Mealy 1011 sequence detector: Z = 1 while the machine is in state 101 and X is 1, so it needs only four states and two flip-flops.

The states record how much of 1011 has arrived: S0 nothing, S1 "1", S2 "10" and S3 "101". There is no "1011" state, because the Mealy output does not wait for one: in S3 the input itself completes the pattern, so Z = Q1 AND Q0 AND X lights during the clock that brings the last 1, and the edge that ends that clock moves the machine on to S1 (the final 1 can start the next match, so 1011011 counts twice). The Moore version of the same detector needs a fifth state, S4 = "1011", three flip-flops, and raises Z one clock later, after the edge, from the state alone. That is the trade in general: Mealy machines need fewer states and answer in the same clock, but their output follows the input combinationally, so a glitch on X can reach Z; Moore outputs change only on clock edges. More examples in the finite state machine lesson and the traffic light controller, a Moore machine.

Big circuit: pinch, scroll or tap + to zoom in, then drag to move around.

Live circuit: click the inputs to toggle them and watch the outputs update. It runs the real simulator, right here on the page.

Open this circuit in the lab →

What you need

2× D flip-flop: the state Q1 Q0 (four states need two bits)
1× AND: D0 = X (every 1 can start or continue the pattern), gated by NOT CLR
3× AND: D1 = Q0 X' + Q1 Q0' X: the terms Q0 X' and Q1 Q0' X, then NOT CLR
1× OR: the two terms of D1
2× AND: the Mealy output Z = Q1 Q0 X
3× NOT: NOT X, NOT Q0 and NOT CLR

Step by step

Write the state table: for each state and each X, the next state and Z. Only S3 with X = 1 gives Z = 1.
Encode S0 = 00, S1 = 01, S2 = 10, S3 = 11 and read the flip-flop inputs off the table: D0 = X, D1 = Q0 X' + Q1 Q0' X.
Build the output from the state and the input: Z = Q1 Q0 X. This direct path from X to Z is what makes it a Mealy machine.
Add a synchronous clear by ANDing each D with NOT CLR, so one clock with CLR on returns to S0.
Turn CLR off and feed 1, 0, 1, 1 on X, one bit per clock: Z lights during the clock of the final 1.

State table

State	Q1 Q0	Next if X = 0	Next if X = 1	Z if X = 1
S0 (nothing)	00	S0	S1	0
S1 (1)	01	S2	S1	0
S2 (10)	10	S0	S3	0
S3 (101)	11	S2	S1	1

Before the page is built, a 16-clock stream with three matches (two of them overlapping) and a 1010 near miss is run through the circuit: Z is checked during every clock, before the edge, and the state Q1 Q0 after every edge. The live circuit starts with CLR on, in S0.

You can also read the full theory in the lesson on sequence detectors and Moore and Mealy machines. Prefer to build it yourself from scratch? Open the digiwleea lab and place the gates on the canvas, or start from the logic gate simulator.

Build more parts from gates

half adder full adder half subtractor full subtractor 2:1 multiplexer 4:1 multiplexer XOR gate from NAND gates 2-to-4 decoder SR latch D flip-flop JK flip-flop T flip-flop 4-bit shift register 4-bit ripple carry adder D latch 1-to-4 demultiplexer 4-bit magnitude comparator 4-bit ring counter 4-bit Johnson counter 4-to-2 priority encoder 4-bit synchronous counter 3-to-8 decoder 8-to-1 multiplexer 4-bit carry lookahead adder half adder from NAND gates 2-bit comparator BCD to 7-segment decoder 4-bit up/down counter decade counter 2-bit multiplier 4-bit ALU 4-bit array multiplier NOT, AND, OR and NOR from NAND NOT, OR, AND and XOR from NOR full adder from NAND gates SR latch from NAND gates parity generator and checker 4-bit adder/subtractor BCD adder 4-bit universal shift register mod-6 counter 4-bit ripple counter binary to Gray code converter half adder from NOR gates full adder from NOR gates 4-bit register with parallel load 1011 sequence detector binary to BCD converter D flip-flop from NAND gates 1-bit ALU CMOS inverter CMOS NAND gate CMOS NOR gate PISO shift register SR flip-flop from NAND gates BCD to excess-3 code converter Hamming (7,4) code encoder and corrector traffic light controller 4-bit barrel shifter CMOS AND gate CMOS OR gate CMOS XOR gate 1-bit magnitude comparator half subtractor from NAND gates full subtractor from NAND gates 8-to-3 encoder Gray to binary converter 4-to-16 decoder full adder using 4:1 multiplexers edge detector serial adder 4-bit carry-select adder master-slave JK flip-flop (NAND)half subtractor from NOR gates 1-to-8 demultiplexer excess-3 to BCD code converter vending machine FSM 4-bit carry-save adder 3-bit synchronous counter (JK)CMOS transmission gate tri-state buffer (CMOS)2-to-1 mux from transmission gates

Each of these is one step from a transistor to a working CPU. Build every gate from CMOS transistors and work all the way up in the free digiwleea lab, with the free theory reference alongside.

Open the Mealy machine (1011 detector) in the lab →

Frequently asked

What is the difference between a Moore and a Mealy machine?

In a Moore machine the outputs depend only on the current state, so they change only on clock edges. In a Mealy machine the outputs depend on the current state and the current inputs, so they can change as soon as an input changes. Mealy machines usually need fewer states.

Why does a Mealy machine need fewer states?

Because the output can use the input directly. A Moore 1011 detector needs a state that means "just saw 1011" to hold Z = 1; the Mealy version raises Z from state "101" plus the incoming 1, so that extra state disappears: four states instead of five here.

Which is faster, Mealy or Moore?

A Mealy machine reacts in the same clock as the input, one clock earlier than the equivalent Moore machine. The price is that its output can glitch when the input does, so designs that need clean outputs register them, which effectively turns the output back into a Moore output.

Can every Mealy machine be converted to a Moore machine?

Yes. Split each state by the output value it produces on its incoming transitions, so the output can be attached to the state. The Moore machine may need more states and responds one clock later.

Is a sequence detector a Moore or a Mealy machine?

It can be either. This page builds the Mealy version of the 1011 detector; the Moore version is a separate live build with one more state and three flip-flops.