Finite state machines: Mealy and Moore, sequence detectors, state minimisation

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• What makes a counter self-starting? from Lesson 6.2.3
• Minimum flip-flops for N states? from Lesson 6.2.2
• With D flip-flops, what is D for each bit? from Lesson 6.2.3

1 · The Hook

🎣

A combination lock opens only after the right sequence of digits; a vending machine gives a chocolate after enough coins. Both are finite state machines: a few states, an input at each step, and an output. GATE asks you to read state diagrams, to give the output for an input sequence, to count the states a sequence detector needs, and to minimise state tables.

2 · Predict First

🤔

A machine must output 1 whenever the last three input bits were 1, 0, 1. What does it need to remember between steps?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

How much of the pattern it has seen so far: nothing, "1", or "10". That is 3 states (plus, for some designs, a fourth "just saw 101" state).

🗣️

In plain words

A state machine remembers only which state it is in. At each clock it reads the input, moves to the next state and produces an output. In a Moore machine the output depends only on the state; in a Mealy machine it depends on the state and the current input (so it can react in the same clock cycle).

1. Mealy vs Moore

2. Sequence detector for 101 (overlapping)

States: S0 = nothing useful seen, S1 = seen "1", S2 = seen "10". Mealy (3 states):

After detecting 101, the last "1" can start a new pattern, so S2 --1--> S1 (overlapping). For non-overlapping detection, S2 --1--> S0. Moore needs a 4th state S3 = "seen 101" with output 1 (S3 --0--> S2, S3 --1--> S1). Input 1 0 1 0 1 1 0 1 → overlapping output 0 0 1 0 1 0 0 1; non-overlapping 0 0 1 0 0 0 0 1. Rule of thumb: detecting a k-bit sequence needs k states (Mealy) and k + 1 states (Moore).

3. Number of flip-flops

A machine with s states needs ⌈log₂ s⌉ flip-flops (binary state assignment).

4. State minimisation

Two states are equivalent if, for every input sequence, they give the same outputs. Find them by partitioning:

• Split the states into groups with equal outputs.
• Split a group further if two of its states go (on some input) to different groups.
• Repeat until nothing changes; each final group becomes one state.

Example (Moore, output Z):

Outputs: {A, B, C, F}, {D, E}. Next-state groups split {A, B, C, F} into {A}, {B, C}, {F}. Final: {A}, {B, C}, {D, E}, {F} → 4 states (2 flip-flops).

4 · Visual

Mealy detector for 101 with overlap: arrows are labelled input/output; the 1/1 arrow fires on the final 1 of 101.

5 · Worked Examples

Example 1 Easy

How many flip-flops does a 5-state machine need?

Solution

⌈log₂ 5⌉ = 3.

Example 2 Medium

Give the outputs of the overlapping Mealy 101 detector for input 1 0 1 0 1.

Solution

0 0 1 0 1 (two overlapping detections).

Example 3 GATE

Minimum number of states for a Moore machine that detects the sequence 1011 (overlapping allowed)?

Solution

k + 1 = 5.

6 · GATE Traps

⚠️

• Moore output belongs to the state, Mealy output to the transition.
• Overlapping detectors reuse the tail of a match; non-overlapping restart from S0.
• Moore usually needs one more state than Mealy for the same detector.
• Equivalent states need equal outputs and equivalent next states for every input.

7 · Memory Hook

🧠

"Moore: output in the state. Mealy: output on the arrow. k-bit detector: k (Mealy) or k + 1 (Moore) states. Minimise by splitting groups."

8 · Connect the Dots

Phase 6 is complete, and so is the whole syllabus. Phase 7 gathers it: the master rule sheet, mixed practice, the GATE pattern drill and the final test.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markFlip-flops

How many flip-flops are needed for a state machine with 9 states?

Numerical answer: ________

Q2MCQ1 markMoore vs Mealy

In a Mealy machine, the output depends on:

• (A) the clock only
• (B) the input only
• (C) the present state only
• (D) the present state and the present input

Q3NAT2 marksDetector output

The overlapping Mealy 101 detector of this lesson receives 1 1 0 1 0 1 0 1. How many 1s does it output?

Numerical answer: ________

Q4NAT2 marksMinimisation

In the minimisation example of this lesson, how many states remain?

Numerical answer: ________

Q5NAT1 markDetector states

Minimum number of states of a Mealy machine detecting the sequence 1101?

Numerical answer: ________

10 · Rule Card

• Moore: output = f(state). Mealy: output = f(state, input); usually fewer states.
• k-bit sequence detector: k states (Mealy), k + 1 (Moore). Overlapping vs non-overlapping changes the arrows after a match.
• s states → ⌈log₂ s⌉ flip-flops.
• Minimise by partition: group by outputs, split by next-state groups, repeat.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

finite state machinestate diagramstate tableMoore machineMealy machineoutput timingsequence detectoroverlapping and non-overlapping detectionstate assignment and flip-flop countequivalent statesstate minimisation by partitioning

12 · Answer Vault