Finite State Machines — Mealy & Moore
State diagrams, state minimisation, sequence detectors – the most conceptually rich topic in Digital Logic. Expect 1-2 marks in GATE CS almost every year. Master this completely.
Last updated: April 2026 | GATE CS 2024-2026 syllabus
Key Takeaways
- An FSM (Finite State Machine) is a sequential circuit with a finite number of states, defined by: states, inputs, outputs, transition function, and output function.
- Moore machine: output depends only on current state. Mealy machine: output depends on current state AND current input.
- Mealy machines typically use fewer states than equivalent Moore machines for the same function.
- State minimisation: merge equivalent states (same output, same transitions to equivalent states). Uses equivalence partitioning or implication table method.
- Sequence detector: FSM that outputs 1 when the last k inputs match a target sequence. Overlapping detectors can reuse a partial suffix as a new prefix.
- State assignment: encoding states as binary numbers. Affects the complexity of the combinational logic for transitions and outputs.
- Converting Mealy to Moore: split each Mealy state into multiple Moore states, one per distinct output value. Converting Moore to Mealy: move output from states to transitions entering those states.
1. FSM Definition and Components
A Finite State Machine (FSM) is a mathematical model of computation represented by a directed graph. It is defined by a 6-tuple:
Q = finite set of states
Σ = finite input alphabet
Δ = state transition function: Q × Σ → Q
λ = output function (Moore: Q → Ω, Mealy: Q × Σ → Ω)
q0 = initial state
F = set of accepting/final states (for recognisers; not used in general Moore/Mealy machines)
In digital logic, FSMs are implemented as synchronous sequential circuits: flip-flops store the state, combinational logic computes the next state and output.
2. Mealy vs Moore Machines
| Property | Moore Machine | Mealy Machine |
|---|---|---|
| Output depends on | Current state only | Current state + current input |
| Output timing | Synchronous (changes with state) | Can change between clock edges (asynchronous to clock) |
| Number of states | Generally more states | Generally fewer states |
| State diagram notation | Output written inside state circle | Output written on transition arc (input/output) |
| Output glitches | Less likely (output tied to state) | Possible (input change can cause output change mid-cycle) |
| Design preference | Safer for synchronous systems | Faster response, fewer states |
Mealy output function: Z = λ(q, x) (output is a property of the transition)
3. State Diagrams and State Tables
State Diagram Notation
- States: Circles (Moore: state/output inside; Mealy: just state name)
- Transitions: Directed arcs labelled with input (Moore) or input/output (Mealy)
- Initial state: Arrow pointing to the start state from no source
- Final/accepting states: Double circle (used in automata theory; optional in sequential logic)
State Table Format
Moore machine state table:
| Present State | Next State (x=0) | Next State (x=1) | Output Z |
|---|---|---|---|
| A | B | A | 0 |
| B | A | C | 0 |
| C | B | A | 1 |
Mealy machine state table:
| Present State | Next State (x=0) | Output (x=0) | Next State (x=1) | Output (x=1) |
|---|---|---|---|---|
| A | B | 0 | A | 1 |
| B | A | 1 | C | 0 |
| C | B | 0 | A | 0 |
4. State Minimisation
State minimisation finds the smallest FSM (fewest states) that produces the same input-output behaviour as the original.
Equivalence Partitioning Method
- Step 1 – Initial partition P0: Group states by output. States with the same output are in the same group.
- Step 2 – Refine partition: For each group, check if all states in the group transition to states in the same group for every input. If two states in the same group transition to different groups on some input, split them.
- Step 3 – Repeat Step 2 until no further splitting occurs.
- Step 4 – Merge: States that remain in the same group are equivalent – merge them into one state.
Worked Example – State Minimisation
Given Moore machine with 5 states:
| State | NS (x=0) | NS (x=1) | Output |
|---|---|---|---|
| A | B | C | 0 |
| B | A | D | 0 |
| C | E | A | 0 |
| D | A | B | 1 |
| E | A | B | 1 |
P0 (group by output): {A,B,C} (output 0) and {D,E} (output 1)
P1 – check {A,B,C}: On x=0: A→B (group 0), B→A (group 0), C→E (group 1). C transitions to group 1 on x=0, while A and B stay in group 0. Split: {A,B} and {C}.
Check {D,E}: On x=0: D→A (group 0), E→A (group 0). On x=1: D→B (group {A,B}), E→B (group {A,B}). Same transitions → D and E stay together.
P1 = {A,B}, {C}, {D,E}
P2 – check {A,B}: On x=0: A→B ({A,B}), B→A ({A,B}). On x=1: A→C ({C}), B→D ({D,E}). Different groups on x=1! Split: {A} and {B}.
P2 = {A}, {B}, {C}, {D,E}
P3 – no further splits possible.
5. Mealy-Moore Conversion
Mealy to Moore
- For each Mealy state q that produces different outputs for different inputs, create multiple Moore states – one for each distinct output value that q produces as a destination state.
- More precisely: for each (state, output) pair that appears as the result of any transition, create a Moore state. Label it q/z where z is the output.
- Transitions in the Moore machine: if the Mealy machine goes from state p to state q with output z on input x, the Moore machine goes from p/z' (or p' for the initial state) to q/z on input x.
- Assign output z to Moore state q/z.
Moore to Mealy
- Keep the same states and transitions.
- Move the output from each state to all transitions leading into that state.
- The initial state output must be handled carefully (the first output is produced before any transition).
Converting Moore to Mealy may allow state merging, potentially reducing the state count.
6. Sequence Detectors
A sequence detector is an FSM that monitors a serial bit stream and outputs 1 when the last k bits match a target pattern.
Overlapping vs Non-Overlapping Detection
Overlapping: After detecting the target sequence, the longest suffix of the detected sequence that is also a prefix of the target becomes the new current state. This allows detection of patterns like 1011 in 10110111…
Design Procedure
- Define the target sequence (e.g., 1011).
- Create states representing “seen k correct bits so far”: S0 (0 bits), S1 (seen 1), S2 (seen 10), S3 (seen 101), S4 (seen 1011 – detecting state).
- For each state, determine transitions:
- On a matching next bit: advance to the next state.
- On a non-matching bit: go back to the appropriate state (the state representing the longest matching prefix of the target that is a suffix of the current history).
- For overlapping detection, from S4, the failure function (like KMP algorithm) determines where to go next instead of S0.
Example – Overlapping Detector for 101
| State (Meaning) | Input x=0 | Input x=1 | Output (Mealy) |
|---|---|---|---|
| S0 (start) | S0 | S1 | 0 / 0 |
| S1 (seen 1) | S2 | S1 | 0 / 0 |
| S2 (seen 10) | S0 | S3 | 0 / 0 |
| S3 (seen 101) | S2 | S1 | 1 / 0 |
Output column shows output when exiting S3 on x=0 (detection) and x=1. In overlapping design, after detecting 101 followed by 0, we are in state S2 (seen 10 of the next potential sequence).
7. State Assignment
State assignment maps symbolic state names (A, B, C…) to binary codes (00, 01, 10…). The choice of encoding affects the complexity of the next-state and output logic.
Common Encoding Strategies
| Encoding | FFs needed | Advantage | Disadvantage |
|---|---|---|---|
| Binary encoding | ⌈log2N⌉ | Minimum FF count | Complex next-state logic |
| One-hot encoding | N (one FF per state) | Simple next-state logic | Many FFs, impractical for large N |
| Gray code | ⌈log2N⌉ | Reduces glitches (only 1 bit changes per transition) | Less intuitive |
| Output-coded | Varies | Simplifies output logic (output = subset of state bits) | Depends on output pattern |
8. GATE CS Solved Examples
Example 1 – Number of States in Sequence Detector (GATE CS 2022)
Question: How many states are needed in a Mealy machine to detect the sequence 1010 with overlapping?
Analysis: We need to track how many bits of the prefix 1010 have been matched so far.
- S0: No bits matched (start)
- S1: Matched "1"
- S2: Matched "10"
- S3: Matched "101"
- S4: Matched "1010" (output 1, then handle overlap)
After detecting 1010 (S4), if next input is 1, the suffix "1" is a prefix of 1010 → go to S1. If next is 0, no prefix of 1010 matches → go to S0.
Example 2 – State Minimisation (GATE CS 2019)
Question: A Moore machine has the following state table. Find the minimum number of states.
| State | NS (0) | NS (1) | Output |
|---|---|---|---|
| A | B | C | 0 |
| B | A | D | 1 |
| C | B | A | 1 |
| D | D | A | 0 |
| E | D | B | 0 |
| F | B | C | 0 |
P0 (by output): {A, D, E, F} (output 0) and {B, C} (output 1)
P1: Check {A, D, E, F}: On x=0: A→B(1), D→D(0), E→D(0), F→B(1). A and F go to output-1 group; D and E go to output-0 group. Split: {A,F} and {D,E}.
Check {B,C}: On x=0: B→A({A,F}), C→B({B,C}). Different groups! Split: {B} and {C}.
P1 = {A,F}, {D,E}, {B}, {C}
P2: Check {A,F}: On x=0: A→B, F→B (same group). On x=1: A→C, F→C (same). No split.
Check {D,E}: On x=0: D→D({D,E}), E→D({D,E}). On x=1: D→A({A,F}), E→B({B}). Different groups! Split: {D} and {E}.
P2 = {A,F}, {D}, {E}, {B}, {C} – no further merging possible.
Example 3 – Mealy to Moore Conversion (GATE CS 2017 style)
Question: A Mealy machine has 3 states (A, B, C) and produces output 0 or 1 on transitions. How many states does the equivalent Moore machine have at most?
Rule: Count the number of distinct (destination-state, output) pairs across all transitions.
Example transitions:
- A on 0 → B, output 1
- A on 1 → C, output 0
- B on 0 → A, output 0
- B on 1 → C, output 1
- C on 0 → A, output 1
- C on 1 → B, output 0
Distinct (destination, output) pairs: (B,1), (C,0), (A,0), (C,1), (A,1), (B,0) – all 6 are distinct.
9. Common Mistakes
Mistake 1 – Confusing Mealy and Moore output placement
Error: In a Moore state diagram, writing the output on the transition arc instead of inside the state circle.
Root cause: Mixing up the notation from memory.
Fix: Moore: output is a property of the STATE (written inside the circle as state/output). Mealy: output is a property of the TRANSITION (written on the arc as input/output).
Mistake 2 – Wrong failure transitions in overlapping sequence detectors
Error: On a mismatch, always returning to S0 (the start state).
Root cause: Not computing the longest proper suffix that is also a valid prefix of the target sequence.
Fix: Use the same logic as the KMP failure function. For example, in detecting 1011: after seeing 101, on input 0 (mismatch for the 4th bit), the suffix 10 is a valid prefix of 1011 → go to state S2, not S0.
Mistake 3 – Stopping state minimisation too early
Error: Stopping after P1 without continuing to check if the refined groups can be further split.
Root cause: The iterative nature of equivalence partitioning is easy to miss.
Fix: Keep refining until the partition does not change between iterations. Only then are the equivalence classes final.
Mistake 4 – Incorrect Mealy-to-Moore state count
Error: Saying a Mealy machine with n states always becomes a Moore machine with exactly n states.
Root cause: Forgetting that each Mealy state may need to be split if it produces different outputs for different inputs.
Fix: Count the number of distinct (state, output) pairs on incoming transitions. That is the number of Moore states needed. It can be up to 2n for binary output.
Mistake 5 – Confusing state count with flip-flop count
Error: An FSM with 5 states requires 5 flip-flops.
Root cause: Confusing one-hot encoding (5 FFs for 5 states) with binary encoding (⌈log25⌉ = 3 FFs for 5 states).
Fix: Unless the problem specifies one-hot encoding, assume binary encoding: n states need ⌈log2n⌉ flip-flops. 5 states need 3 FFs (encodes up to 8 states, 3 unused).
10. Frequently Asked Questions
What is the difference between a Mealy and Moore machine?
In a Moore machine, output depends only on the current state – output is synchronised to the clock. In a Mealy machine, output depends on both the current state and the current input – output can change between clock edges. Mealy machines typically require fewer states for the same function. Moore machines are safer in synchronous design because their outputs don't glitch with input changes.
What is state minimisation and how is it done?
State minimisation finds the fewest-state FSM equivalent to the original. The equivalence partitioning method: (1) Group states by output. (2) Split groups where states transition to different groups on the same input. (3) Repeat until stable. (4) Merge states in the same final group.
How do you design a sequence detector FSM?
Define the target sequence. Create states for each prefix matched: S0 (nothing), S1 (first bit), …, Sk (full match). On matching input, advance. On mismatch, use the failure function to find the longest suffix of the current match that is also a prefix of the target (like KMP). Output 1 when Sk is reached.
How many states does a Mealy machine need compared to a Moore machine for the same function?
A Mealy machine generally needs fewer states. Converting Mealy to Moore: split each Mealy state into one Moore state per distinct output value it produces as a destination. For binary output, a Mealy machine with n states becomes at most a Moore machine with 2n states. The Mealy machine is always at least as compact as the equivalent Moore machine.