Finite state machines (Mealy and Moore)

WHAT is a Finite State Machine?

The whole distinction between Mealy and Moore lives in the output function $\lambda$ :

Type	Output function	Output depends on	Written
Moore	$\lambda : S \to O$	state only	output labelled inside the state
Mealy	$\lambda : S \times I \to O$	state AND current input	output labelled on the transition arrow

HOW an FSM is built in hardware

Every FSM has the same three-block skeleton:

Figure — Finite state machines (Mealy and Moore)

State register — flip-flops holding the current state $Q$ . Updated on each clock edge to the next state $D = \delta(Q, I)$ .
Next-state logic — combinational logic computing $\delta$ .
Output logic — combinational logic computing $\lambda$ .

Deriving the number of flip-flops

Worked Example 1 — "detect 11" sequence detector (Moore)

Goal: output $Z=1$ whenever the input bit stream has produced two consecutive 1s.

States (what each remembers):

$S_0$ : "no useful 1s seen yet" — output 0
$S_1$ : "last bit was a single 1" — output 0
$S_2$ : "saw 11" — output 1

Transition table (derived by asking "where do I go on 0 and on 1?"):

State	in=0 →	in=1 →	output
$S_0$	$S_0$	$S_1$	0
$S_1$	$S_0$	$S_2$	0
$S_2$	$S_0$	$S_2$	1

Why this step? On a 0 any run of 1s is broken, so we reset toward $S_0$ . On a 1 we advance our "how many 1s in a row" counter, saturating at $S_2$ .

Input 0 1 1 0 1:

Start $S_0$ →(1) $S_1$ →(1) $S_2$ (out=1 here) →(0) $S_0$ →(1) $S_1$
Output stream: 0 0 1 0 0. Note the 1 appears one cycle after the second 1 — Moore's characteristic delay.

Worked Example 2 — same detector as a Mealy machine

Now output on the transition, so we can flag on the very edge that completes 11.

State	in=0 (next / out)	in=1 (next / out)
$A$ (no 1 yet)	$A$ / 0	$B$ / 0
$B$ (one 1)	$A$ / 0	$B$ / 1

Why only 2 states? Because the output "is this a completing 1?" is answered by looking at the input, so we don't need a separate $S_2$ state — we merge it into a transition label. This is the classic "Mealy uses fewer states."

Input 0 1 1 0 1:

$A$ →(0,out0) $A$ →(1,out0) $B$ →(1,out1) $B$ →(0,out0) $A$ →(1,out0) $B$
Output stream: 0 0 1 0 0 but the 1 is produced the same cycle as the second 1 — one cycle earlier in "time" than Moore.

Common Mistakes

Recall Feynman: explain it to a 12-year-old

Imagine a board game where you have a little marker sitting on one square. Every "tick" of a clock you read a card (the input) and the rules tell you which square to move to. Each square is a state, and the marker is the machine's memory. In a Moore game, the prize you win is printed on the square you land on. In a Mealy game, the prize is printed on the arrow you walk along, so it also depends on which card you read. Same game, but Mealy pays you as you move while Moore pays you once you've landed.

Active-Recall Flashcards

What are the 6 tuple components of an FSM?

States

S

, initial state

s_0

, inputs

I

, outputs

O

, next-state function

\delta

, output function

\lambda

In a Moore machine the output depends on what?

The current state only:

Z=\lambda(Q)

In a Mealy machine the output depends on what?

Current state AND current input:

Z=\lambda(Q,I)

Where is the output written on a Moore state diagram?

Inside the state bubble.

Where is the output written on a Mealy state diagram?

On the transition arrows.

How many flip-flops are needed for

|S|

states?

\lceil \log_2 |S|\rceil

Which machine typically needs fewer states, Mealy or Moore?

Mealy.

Which machine has glitch-free, synchronous outputs?

Moore.

Which machine can react to an input change within the same clock cycle?

Mealy (its output is combinational in the input).

Why does the reset/initial state matter in real hardware?

Power-up state is undefined; reset forces the FSM into a known

s_0

Three hardware blocks of any FSM?

State register, next-state (combinational) logic, output (combinational) logic.

Connections

Flip-flops — the storage element for the state register
Sequential Circuits — FSMs are the canonical clocked sequential circuit
Combinational Logic — builds the $\delta$ and $\lambda$ blocks
State minimization — reducing $|S|$ to save flip-flops/logic
State encoding — binary / one-hot / Gray assignment of codes to states
Clocking and timing — why Moore is glitch-free and Mealy can glitch
Sequence detectors — the classic FSM application

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, ek normal combinational circuit ka output sirf abhi ke inputs par depend karta hai — usko koi memory nahi hoti. Lekin bahut baar hume "yaad" rakhna padta hai ki pehle kya hua, jaise vending machine ko yaad rehna chahiye ki kitne paise pade hain. Isi kaam ke liye Finite State Machine (FSM) use hoti hai: yeh flip-flops mein ek state store karti hai, aur har clock edge par input ke hisaab se ek state se doosri state mein jump karti hai. State register + next-state logic + output logic — bas yeh teen blocks hote hain.

Ab Mealy vs Moore ka pura funda sirf ek cheez par tika hai: output kis cheez se banta hai. Moore mein output sirf state se banta hai (diagram mein output state ke bubble ke andar likhte hain). Mealy mein output state aur current input dono se banta hai (output arrow par likhte hain). Yaad rakhne ka trick: Mealy matlab input yes. Circuit mein farak sirf itna hai ki Mealy mein ek input wire seedha output logic tak jaati hai; Moore mein nahi jaati.

Practical difference kya hai? Moore ka output clock edge ke baad, ek cycle late aata hai, par woh glitch-free aur clean hota hai. Mealy turant, usi cycle mein react karta hai aur aksar kam states chahiye hote hain, par glitch aa sakta hai. Humne "11 detect karo" wala example dono tarike se banaya — Moore ko 3 states lage, Mealy ko sirf 2, kyunki Mealy ne "yeh 1 sequence complete kar raha hai" wali baat state ki jagah arrow par label kar di.

Exam aur real design dono mein: states ginne ke baad flip-flops $\lceil \log_2|S|\rceil$ formule se nikaalo, aur reset state define karna kabhi mat bhoolo — warna power-on ke baad machine kahin bhi atak sakti hai. Yeh chota concept controllers, protocols, sabme aata hai, isliye ise achhe se pakdo.

WHAT is a Finite State Machine?

HOW an FSM is built in hardware

Deriving the number of flip-flops

Worked Example 1 — "detect 11" sequence detector (Moore)

Worked Example 2 — same detector as a Mealy machine

Common Mistakes

Active-Recall Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Sequential Circuits

Connections