Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 57 ยท State Machines

Finite State Machines: Moore and Mealy

Learn finite state machines: states, transitions, outputs and state diagrams. Compare Moore and Mealy machines and run both with a table-driven Python simulator.

So far every sequential circuit you have seen was small: a flip-flop, a register, a counter. Real controllers are more interesting. A traffic light, a vending machine, a network protocol, a keyboard scanner and the control unit of a CPU all follow rules like "if I am waiting for a coin and a coin arrives, go to the next step". Such a circuit remembers where it is in a procedure and decides what to do from that memory plus its current inputs.

The mathematical model for this is the finite state machine (FSM). In this lesson you will learn its parts, how to draw one, the difference between the two classic flavors (Moore and Mealy), and how to run any FSM from a transition table in Python. The next lesson, Designing a Sequential Circuit, turns a machine like this into real flip-flops and gates.

What a finite state machine is

An FSM has a finite number of states. At any moment it is in exactly one of them. A clock edge is the only moment the state can change, and the next state depends on two things: the current state and the current inputs. The machine also produces outputs.

Formally an FSM is made of:

  • a set of states, S
  • a set of input values, I
  • a set of output values, O
  • a next-state function: (state, input) -> next state
  • an output function
  • a start (reset) state

The "memory" is a register of flip-flops that holds the state. The next-state function is combinational logic that feeds the register. The output function is also combinational logic. This gives the standard hardware shape of every FSM:

flowchart LR
    IN["Inputs"] --> NSL["Next-state<br/>logic"]
    NSL --> REG["State register<br/>(flip-flops)"]
    REG -->|"current state"| NSL
    REG --> OL["Output<br/>logic"]
    IN -.->|"Mealy only"| OL
    OL --> OUT["Outputs"]

The state register feeds back into the next-state logic. Mealy machines also let the inputs reach the output logic directly.

The parts of an FSM

States A finite list of situations.
Transitions Rules for moving between states.
Outputs What the machine tells the world.
Start state Where it begins after reset.
1 / 2

State diagrams and state tables

There are two equivalent ways to write a machine down.

A state diagram draws each state as a circle and each transition as an arrow labeled with the input that causes it. A small machine that raises a flag after it has seen two 1s in a row looks like this:

stateDiagram-v2
    [*] --> S0
    S0 --> S0 : input 0
    S0 --> S1 : input 1
    S1 --> S0 : input 0
    S1 --> S2 : input 1
    S2 --> S0 : input 0
    S2 --> S2 : input 1

S0 means no 1 yet, S1 means one 1 so far, S2 means at least two 1s in a row. The output is 1 only in S2.

A state table lists the same information as rows: current state, input, next state and output. Tables are what we turn into logic equations, and they are also what a program uses to run the machine. A diagram is easier to read, a table is easier to check for completeness: every state needs a transition for every possible input, otherwise the circuit's behavior in that case is undefined.

Moore machines

In a Moore machine the output is a function of the state only. The state diagram attaches the output to the state (a circle labeled S2 / 1). Because the output changes only when the state changes, it is stable for the whole clock cycle and changes right after a clock edge, so Moore outputs are naturally free of glitches caused by input changes.

The traffic-light controller is a classic Moore machine: each state is a light color, and the output is "which lamp is on".

Python A table-driven FSM runner and a traffic light

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the table: the output column depends only on the state column. In cycles 0 and 1 the state is RED and the output is stop, even though the timer input was 0. The timer input matters only for where we go next.

Mealy machines

In a Mealy machine the output is a function of the state and the current input. On the state diagram the output is written on the arrow, next to the input: 1 / 0 means "if the input is 1, output 0". Because the output reacts to the input in the same cycle, a Mealy machine usually needs fewer states than a Moore machine for the same job, and it responds one clock cycle earlier.

The drawback is that the output is a combinational function of the inputs. If an input wiggles or glitches during the cycle, the output wiggles with it. Mealy outputs also inherit any timing problems on the input side. That is why they are often passed through a register before they leave the module.

Here is the same "two 1s in a row" detector as a Mealy machine. It only needs two states: A (the previous input was 0) and B (the previous input was 1). The output is 1 when the state is B and the input is 1 as well.

stateDiagram-v2
    [*] --> A
    A --> A : 0 / 0
    A --> B : 1 / 0
    B --> A : 0 / 0
    B --> B : 1 / 1

Each arrow shows input / output. The output is produced on the arrow, in the same cycle as the input.

Python Moore versus Mealy on the same input

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the two output rows. The Mealy output goes high in cycle 2, the same cycle in which the second 1 arrives. The Moore output goes high in cycle 3, because it must first move into state S2 and only then can show the result. The two sequences carry exactly the same information, just offset by one clock period, and the Moore machine used one more state.

Moore or Mealy?

Pick the right flavor

Moore Clean outputs, easy timing, more states.
Mealy Faster reaction, fewer states.
Inputs glitch? Prefer Moore or register the output.

Many real designs mix the two.

1 / 2

A practical rule: use Moore when the outputs drive the outside world directly (lamps, motors, other clocked blocks) because they change only once per cycle, shortly after the clock edge. Use Mealy when you need the fastest response or want to save states, and make sure the inputs are stable and synchronized. Any Mealy machine can be converted into an equivalent Moore machine by splitting states, and the reverse works too, so the choice is a design trade-off, not a limit on what you can build.

Things to watch for

  • Incomplete tables. Missing transitions mean undefined behavior. Our runner's check method catches this.
  • Reset. A real circuit needs a way to enter the start state at power-up. We return to this in State Machine Patterns and Pitfalls.
  • Too many states. Two states that behave identically for every possible input sequence are equivalent and can be merged. Smaller machines need fewer flip-flops and less logic.
  • Unused flip-flop combinations. With 3 states you need 2 flip-flops, which can hold 4 values. What the circuit does in the fourth, unused, state must be decided on purpose.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a Moore machine, what determines the output?

    A Moore output is a function of the state alone. It changes only when the state changes, which happens at a clock edge.
  2. 2. Why does a Mealy machine often need fewer states than a Moore machine for the same task?

    Because the Mealy output looks at the input directly, the machine can react in the same cycle. The Moore version has to move into an extra state first so that the state can carry the result.
  3. 3. On a Mealy state diagram, where is the output written?

    A label like 1 / 0 on an arrow means that for input 1 the output is 0. Moore diagrams put the output inside the state instead.
  4. 4. A state table has 4 states and 2 possible input values. How many rows does a complete table need?

    Every state needs a transition for every input value: 4 x 2 = 8 rows.
  5. 5. Which statement about glitches is true?

    A Moore output is a function of the state register, so it is steady during the cycle. A Mealy output also depends on the inputs and passes any glitches on them.

Summary

  • A finite state machine holds a state in flip-flops; combinational logic computes the next state and the outputs.
  • State diagrams show circles and arrows, state tables list every (state, input) pair, and a complete table defines behavior for all inputs.
  • Moore outputs depend only on the state: stable, clean, usually more states.
  • Mealy outputs depend on the state and the input: faster to react, usually fewer states, but they pass input glitches.
  • A table-driven runner in Python is a few lines: look up the next state and output in dictionaries.
  • Always define a start state, a transition for every input, and the behavior for unused states.

Next: Designing a Sequential Circuit.