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

We minimize the 8-state machine by partition refinement (the implication / equivalence-classes method): two states are equivalent iff they produce the same outputs and, for every input, transition to equivalent states.

Step 0 — group by output behavior (the output pair for $x=0,x=1$):

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

Call these blocks $P_1=\{a,b,c,e\}$, $P_2=\{d,h\}$, $P_3=\{f\}$, $P_4=\{g\}$.

Step 1 — refine by successor blocks. Map each state's next states to the block that contains them:

State	$x=0$ block	$x=1$ block
$a$	$f\in P_3$	$b\in P_1$
$b$	$d\in P_2$	$c\in P_1$
$c$	$f\in P_3$	$e\in P_1$
$e$	$d\in P_2$	$c\in P_1$

So $\{a,c\}$ share pattern $(P_3,P_1)$ while $\{b,e\}$ share $(P_2,P_1)$. Split $P_1\to\{a,c\}$ and $\{b,e\}$. States $d,h$ both go to $(P_4,\,\text{block of }a)$, so $\{d,h\}$ stays together.

New partition: $\{a,c\},\{b,e\},\{d,h\},\{f\},\{g\}$.

Step 2 — refine again with blocks $A=\{a,c\}$, $B=\{b,e\}$, $C=\{d,h\}$, $D=\{f\}$, $E=\{g\}$:

State	$x=0$	$x=1$
$a$	$f\in D$	$b\in B$
$c$	$f\in D$	$e\in B$
$b$	$d\in C$	$c\in A$
$e$	$d\in C$	$c\in A$
$d$	$g\in E$	$a\in A$
$h$	$g\in E$	$a\in A$

Within every block the successor patterns agree ($a,c$ both $(D,B)$; $b,e$ both $(C,A)$; $d,h$ both $(E,A)$), so the partition is stable.

Result — 5 equivalence classes:

$\{a,c\},\quad \{b,e\},\quad \{d,h\},\quad \{f\},\quad \{g\}$

The original $8$ states collapse to $\boxed{5}$ distinct states, so 5 states remain — option 2.

Exam trick: Always seed the partition by output pattern first, then refine only by which block each successor falls in (never by the raw state name). The procedure halts the moment a refinement step changes nothing; the number of remaining blocks is the answer.