Finite state machines (Mealy and Moore): Foundations

Before you can read the parent note comfortably, you need to earn every symbol it throws at you. We build them one at a time, each resting on the last, each pinned to a picture.

1. A "state" — the machine's memory of where it is

The picture: a single labelled bubble. That bubble is the state. The whole set of bubbles is the machine's entire memory — nothing is remembered except which bubble we are on right now.

The symbol for the whole collection of bubbles is $S$ (capital S, for the Set of States). We write individual bubbles $S_{0}, S_{1}, S_{2}, \dots$ — the little number is just a name tag, not a quantity.

2. $∣ S ∣$ — "how many bubbles"

The two vertical bars $∣ \cdot ∣$ mean "the size of" (count the members). So $∣ S ∣$ reads aloud as "the number of states."

Why the topic needs this: the cost of the machine in hardware grows with $∣ S ∣$ , so we count them constantly.

3. $\in$ — "is a member of"

The picture: a bubble that lives inside the fenced-off region $S$ . The parent writes $s_{0} \in S$ — meaning "the start bubble is one of our bubbles." (Of course it is; the symbol just says so formally.)

4. $s_{0}$ — the reset / initial state

The picture: an arrow coming from nowhere into one bubble, marking "start here."

5. $I$ and $O$ — inputs and outputs

The picture: a wire coming into the machine (input) and a wire going out (output). On a board game, the input is the card you read this turn; the output is the prize you collect.

Why both are needed: an FSM's whole job is to turn a stream of inputs over time into a stream of outputs. $I$ names what it can read; $O$ names what it can say.

6. Functions and the arrow $\to$ (the heart of it)

Before the parent's $δ$ and $λ$ make sense you must know what a function is and what the arrow $\to$ means.

The picture: a box with an input slot on the left ( $A$ ) and an output slot on the right ( $B$ ), and inside, a rulebook.

7. The Cartesian product $\times$ — "one from each, paired up"

The picture: a grid. Down the side you list every bubble; across the top every input symbol; each cell is one pair $(state, input)$ .

Why the topic needs it: the next-state rule must answer "where do I go?" for every combination of where-I-am and what-I-read. That combination is precisely a member of $S \times I$ . This grid is the transition table.

8. $δ$ — the next-state function

The picture: an arrow leaving one bubble, labelled with the input that causes it, landing on another bubble.

9. $λ$ — the output function (where Mealy and Moore split)

The picture: in Moore the prize is printed inside the bubble; in Mealy the prize is printed on the arrow (so it also depends on which card you read to travel that arrow).

10. The 6-tuple $(S, s_{0}, I, O, δ, λ)$

A tuple is just an ordered shopping list wrapped in parentheses. Now every item on the parent's list is something you built:

11. The clock, $Q$ , and $Q^{+}$ — from paper to flip-flops

The picture: a row of memory cells (Flip-flops) whose value is $Q$ ; on a clock edge they overwrite themselves with $Q^{+}$ .

12. $lo g_{2}$ and the ceiling $⌈ ⌉$ — counting flip-flops

The parent uses $n = ⌈ lo g_{2} ∣ S ∣ ⌉$ . Two new symbols to earn.

Why base 2 and not any other tool? Because each flip-flop stores one bit — a thing with exactly 2 possible values. Put $n$ of them together and you get $2^{n}$ distinct patterns (doubling per flip-flop). To label $∣ S ∣$ bubbles uniquely you need $2^{n} \geq ∣ S ∣$ , and undoing the " $2^{n}$ " is exactly $lo g_{2}$ .

Why round up, never down? You cannot own $1.6$ flip-flops. If the maths asks for $1.6$ bits you must buy $2$ whole flip-flops, so we always ceiling.

How these foundations feed the topic

Equipment checklist

Test yourself — cover the right side and answer each aloud before revealing.

What does

∣ S ∣

mean?

The number of states (count the bubbles).

Read

s_{0} \in S

in plain words.

The initial/start state is one of the states in the set

S

What does the arrow in

f : A \to B

tell you?

f

is a rule taking a member of

A

(in) and producing exactly one member of

B

(out).

What is a member of

S \times I

A pair (one state, one input) — one cell of the transition table.

What does

δ : S \times I \to S

do?

Takes current state + input, returns the next state (moves the marker); no output involved.

What is the difference between Moore's and Mealy's

λ

Moore

λ : S \to O

uses state only; Mealy

λ : S \times I \to O

also uses the input.

In one sentence, what physical thing is the Mealy/Moore boundary?

Whether the input wire reaches the output-logic block (Mealy yes, Moore no).

What is

Q^{+}

The state stored just after the next clock edge, equal to

δ (Q, I)

Why is the flip-flop count a

lo g_{2}

Each flip-flop stores 1 bit, so

n

flip-flops give

2^{n}

patterns; undoing

2^{n}

to reach

∣ S ∣

lo g_{2}

Why the ceiling

⌈ ⌉

on the flip-flop count?

You can only buy whole flip-flops, so always round the bit-count up.

How many flip-flops do 3 states need, and why?

2, because

⌈ lo g_{2} 3 ⌉ = ⌈ 1.585 ⌉ = 2

Connections

Parent: Finite State Machines — the topic these symbols unlock
Flip-flops — the cells that physically store $Q$
Combinational Logic — builds the $δ$ and $λ$ rules
Sequential Circuits — the family this machine belongs to
State encoding — how bubbles become bit-patterns, where $lo g_{2}$ bites
Clocking and timing — the tick that turns $δ$ into $Q^{+}$
State minimization — shrinking $∣ S ∣$ to save flip-flops
Sequence detectors — the worked-example application