سوال ۷۶ کنکور ارشد مهندسی کامپیوتر ۱۴۰۵

This is a Mealy machine (the output depends on the present state and the input $x$). We minimize the 7 states by the partition‑refinement (state‑reduction) procedure and then match the reduced machine to a diagram.

Step 1 — group by output behaviour

Split the states by their output pair $(z_{x=0},\, z_{x=1})$:

• output $(1,0)$: $\{a,b,c,d\}$
• output $(0,1)$: $\{e,f,g\}$

Step 2 — refine by successor blocks

Repeatedly split any block whose members send the two inputs into different blocks. This converges to four equivalence classes:

$P=\{a,b,d\},\qquad Q=\{c\},\qquad R=\{e,g\},\qquad T=\{f\}$

• $a,b,d$ all do $0\to f\,(T)/1$ and $1\to e\text{ or }g\,(R)/0$ — identical behaviour, so they merge.
• $e,g$ both do $0\to a\text{ or }b\,(P)/0$ and $1\to e\text{ or }g\,(R)/1$ — they merge.
• $c$ and $f$ each behave uniquely and stay alone.

Step 3 — reduced state table

State	Next ($x=0$)	Next ($x=1$)	Out ($x=0$)	Out ($x=1$)
$P$	$T$	$R$	1	0
$Q$	$P$	$Q$	1	0
$R$	$P$	$R$	0	1
$T$	$T$	$R$	0	1

Step 4 — read the self-loops and match

A fast fingerprint of the reduced machine is its self-loops:

• $R$ loops on input $1$ with output $1$ → label $1/1$
• $T$ loops on input $0$ with output $0$ → label $0/0$
• $Q$ loops on input $1$ with output $0$ → label $1/0$
• $P$ has no self-loop

So the correct diagram must contain exactly the three self-loops $\{1/1,\ 0/0,\ 1/0\}$ and one loop-free state. Only diagram (1) does — with the encoding $00=R,\ 10=T,\ 11=Q,\ 01=P$:

• $00$ self-loops $1/1$ ($=R$), $10$ self-loops $0/0$ ($=T$), $11$ self-loops $1/0$ ($=Q$), $01$ has no loop ($=P$).
• Remaining edges also match: $01\xrightarrow{0/1}10$, $01\xrightarrow{1/0}00$, $00\xrightarrow{0/0}01$, $10\xrightarrow{1/1}00$, $11\xrightarrow{0/1}01$.

Diagram 2 has self-loops $\{1/1,1/1,1/0\}$ (no $0/0$), diagram 3 has $\{1/0,0/0,0/0\}$ (no $1/1$), diagram 4 has $\{1/1,0/1,0/0\}$ (no $1/0$) — all wrong. The answer is option 1.

Exam trick: After reducing a Mealy machine, you rarely need to match every edge. Fingerprint each reduced state by its self-loop label $(x/z)$; the option whose set of self-loops matches is almost always the unique answer.