5.4Mealy and Moore machines
The idea
A finite state machine remembers a state. In a Moore machine the output depends only on the state; in a Mealy machine it depends on the state and the current input.
Think of it like this: A vending machine: the state is the money inserted; a Mealy machine gives a drink the instant the last coin arrives, a Moore machine one step later.
Why it exists
Sequence detectors and machine-type questions are standard sequential-circuit material.
How it works
- Draw the states as what you must remember (the longest useful suffix of the input).
- Mealy: label each transition with input/output.
- Moore: put the output inside each state.
- A Moore machine for the same task usually needs one more state; flip-flops = ⌈log₂ states⌉.
Worked example: Overlapping detector for 1011
Mealy: 4 states (A, B, C, D) and an output of 1 on the last 1. Moore: 5 states with an extra state E whose output is 1.
Now play with it
- →Run the input 1011011 on the Mealy and the Moore machine and compare the outputs.
- →Try the divisible-by-3 machine on 110 (6) and 111 (7).
- Start in state A
- Read 1: A → B, output 0
- Read 0: B → C, output 0
- Read 1: C → D, output 0
- Read 1: D → B, output 1
- Read 0: B → C, output 0
- Read 1: C → D, output 0
- Read 1: D → B, output 1
| state | input 0 | input 1 |
|---|---|---|
| A | A / 0 | B / 0 |
| B | C / 0 | B / 0 |
| C | A / 0 | D / 0 |
| D | C / 0 | B / 1 |
Output depends on state AND input, so it appears on the same clock as the last 1. Four states.
Check yourself
In a Moore machine the output depends on
Exam notes (the dense version)
In a Moore machine the output depends only on the present state; in a Mealy machine it depends on the state and the current input, so it can react one clock earlier and usually needs fewer states (a sequence detector for 1011 needs 4 Mealy states but 5 Moore states). The next state function is the same kind in both. A Mealy output can change when the input changes between clock edges. With k states you need ⌈log₂ k⌉ flip-flops. An overlapping detector reuses the end of the previous match as the start of the next.
Previous year questions: Counters, Registers & State Machines (10)
PYQs are grouped by topic, so this is the full set for Counters, Registers & State Machines; try the ones that match this subtopic. Open all 10 on the topic page.