Finite state machines (Mealy and Moore) — Hinglish notes

3.4.10 · Hardware › Sequential Circuits

Finite State Machine KYA hai?

Mealy aur Moore ke beech ka poora distinction output function $λ$ mein hi rehta hai:

Type	Output function	Output depend karta hai	Likha jaata hai
Moore	$λ : S \to O$	sirf state par	output state ke andar label hota hai
Mealy	$λ : S \times I \to O$	state AUR current input par	output transition arrow par label hota hai

Hardware mein FSM KAISE banta hai

Har FSM ka ek hi three-block skeleton hota hai:

Figure — Finite state machines (Mealy and Moore)

State register — flip-flops jo current state $Q$ hold karte hain. Har clock edge par next state $D = δ (Q, I)$ par update hota hai.
Next-state logic — combinational logic jo $δ$ compute karta hai.
Output logic — combinational logic jo $λ$ compute karta hai.

Flip-flops ki sankhya derive karna

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

Goal: jab bhi input bit stream ne do consecutive 1s produce kiye hon tab output $Z = 1$ karo.

States (har ek kya yaad rakhta hai):

$S_{0}$ : "abhi tak koi useful 1 nahi dekha" — output 0
$S_{1}$ : "last bit ek single 1 tha" — output 0
$S_{2}$ : "11 dekha" — output 1

Transition table ("0 aur 1 par main kahan jaaunga?" pooch ke derive kiya gaya):

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

Yeh step kyun? 0 par 1s ki koi bhi run toot jaati hai, toh hum $S_{0}$ ki taraf reset karte hain. 1 par hum apna "kitne 1s row mein hain" counter aage badhate hain, $S_{2}$ par saturate karte hain.

Input 0 1 1 0 1:

Start $S_{0}$ →(1) $S_{1}$ →(1) $S_{2}$ (out=1 yahan) →(0) $S_{0}$ →(1) $S_{1}$
Output stream: 0 0 1 0 0. Note karo ki 1 doosre 1 ke ek cycle baad aata hai — yeh Moore ki characteristic delay hai.

Worked Example 2 — same detector Mealy machine ke roop mein

Ab output transition par do, taaki hum usi edge par flag kar sakein jo 11 complete karta hai.

State	in=0 (next / out)	in=1 (next / out)
$A$ (abhi tak 1 nahi)	$A$ / 0	$B$ / 0
$B$ (ek 1)	$A$ / 0	$B$ / 1

Sirf 2 states kyun? Kyunki output "kya yeh completing 1 hai?" ka jawab input dekh ke milta hai, toh hume alag $S_{2}$ state ki zaroorat nahi — hum use transition label mein merge kar dete hain. Yeh classic "Mealy uses fewer states" hai.

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 lekin 1 doosre 1 ke same cycle mein produce hota hai — Moore se "time" mein ek cycle pehle.

Common Mistakes

Recall Feynman: ek 12-saal ke bachche ko explain karo

Ek board game imagine karo jahan ek chhota marker ek square par rakha hai. Clock ki har "tick" par tum ek card padhte ho (input) aur rules batate hain ki marker ko kis square par le jaana hai. Har square ek state hai, aur marker machine ki memory hai. Moore game mein, jo prize tum jeetते ho woh us square par likha hota hai jahan tum land karte ho. Mealy game mein, prize us arrow par likha hota hai jis par tum chalte ho, toh yeh is par bhi depend karta hai ki tumne kaun sa card padha. Same game hai, lekin Mealy tumhe chalte waqt pay karta hai jabki Moore land karne ke baad pay karta hai.

Active-Recall Flashcards

FSM ke 6 tuple components kya hain?

States

S

, initial state

s_{0}

, inputs

I

, outputs

O

, next-state function

δ

, output function

λ

Moore machine mein output kis par depend karta hai?

Sirf current state par:

Z = λ (Q)

Mealy machine mein output kis par depend karta hai?

Current state AUR current input par:

Z = λ (Q, I)

Moore state diagram mein output kahan likha hota hai?

State bubble ke andar.

Mealy state diagram mein output kahan likha hota hai?

Transition arrows par.

∣ S ∣

states ke liye kitne flip-flops chahiye?

⌈ lo g_{2} ∣ S ∣ ⌉

Kaun si machine ko aam taur par kam states ki zaroorat hoti hai, Mealy ya Moore?

Mealy.

Kaun si machine ke outputs glitch-free aur synchronous hote hain?

Moore.

Kaun si machine same clock cycle mein input change par react kar sakti hai?

Mealy (uska output input mein combinational hai).

Real hardware mein reset/initial state kyun matter karta hai?

Power-up state undefined hoti hai; reset FSM ko ek known

s_{0}

mein force karta hai.

Kisi bhi FSM ke teen hardware blocks kaun se hain?

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

Connections

Flip-flops — state register ke liye storage element
Sequential Circuits — FSMs canonical clocked sequential circuit hain
Combinational Logic — $δ$ aur $λ$ blocks banata hai
State minimization — flip-flops/logic bachane ke liye $∣ S ∣$ reduce karna
State encoding — states ko codes assign karna binary / one-hot / Gray mein
Clocking and timing — kyun Moore glitch-free hai aur Mealy glitch kar sakta hai
Sequence detectors — classic FSM application