Following is a state table for a finite state machine: Present State | Input-0 (Next State, Output) | Input-1 (Next State, Output) A | B, 1 | H, 1 B | F, 1 | D, 1 C | D, 0 | F, 1 D | C, 0 | F, 1 E | D, 1 | C, 1 F | C, 1 | D, 1 G | C, 1 | D, 1 H | E, 1 | A, 1 A. Find the equivalence partition on the states of the machine. B. Give the state table for the minimal machine. (Use appropriate names for the equivalent states. For example if states X and Y are equivalent then use XY as the name for the equivalent state in the minimal machine.) What is the minimum number of states in the equivalent minimal machine?

GATE 1997 · Theory of Computation · Minimal State Automata · medium

Answer: Final equivalence partition: { {A}, {B}, {H}, {E,F,G}, {C,D} }. The minimal machine has 5 states. Merged states: EFG (states E, F, G are equivalent) and CD (states C, D are equivalent).

1. Form initial partition P0 by output vectors: From the table, the output pairs (out_0, out_1) for each state: A: (1,1), B: (1,1), C: (0,1), D: (0,1), E: (1,1), F: (1,1), G: (1,1), H: (1,1) So P0 = { {A,B,E,F,G,H}, {C,D} }
2. Refine to P1: Group {A,B,E,F,G,H}: check next-states on input 0: A->B (in group1), B->F (in group1), E->D (in group2!), F->C (in group2!), G->C (in group2!), H->E (in group1) So E, F, G go to group2 on input 0, while A, B, H go to group1 on input 0. Split {A,B,E,F,G,H} into {A,B,H} and {E,F,G}. Group {C,D}: next-states on input 0: C->D (group2), D->C (group2) — same group; on input 1: C->F (group1), D->F (group1) — same group. No split. P1 = { {A,B,H}, {E,F,G}, {C,D} }
3. Refine to P2: Group {A,B,H}: next-states on input 0: A->B (group1), B->F (group2), H->E (group2). A's next-state-on-0 is in group1, but B and H have next-states in group2. Split: {A} vs {B,H}. Group {E,F,G}: next-states on input 0: E->D (group3), F->C (group3), G->C (group3). All in group3. On input 1: E->C (group3), F->D (group3), G->D (group3). All same group. No split — {E,F,G} stays. Group {C,D}: as before, no split. P2 = { {A}, {B,H}, {E,F,G}, {C,D} }
4. Check P3 for stability: Group {B,H}: on input 0: B->F (in {E,F,G}), H->E (in {E,F,G}) — same group. On input 1: B->D (in {C,D}), H->A (in {A}) — DIFFERENT groups! Split: {B} vs {H}. Wait — recheck: P2 groups are {A}, {B,H}, {E,F,G}, {C,D}. On input 1: B->D (in {C,D}), H->A (in {A}) — different groups, so split {B,H} into {B} and {H}. Group {E,F,G}: on input 0: all go to {C,D}. On input 1: E->C (in {C,D}), F->D (in {C,D}), G->D (in {C,D}) — same. No split. P3 = { {A}, {B}, {H}, {E,F,G}, {C,D} } — 5 groups. Group {E,F,G}: on input 0: E->D ({C,D}), F->C ({C,D}), G->C ({C,D}) — same. On input 1: E->C ({C,D}), F->D ({C,D}), G->D ({C,D}) — same. No split. P4 = P3 = { {A}, {B}, {H}, {E,F,G}, {C,D} } — 5 groups. However checking more carefully: in P3, check group {A}: only 1 state, no split. {B}: 1 state. {H}: 1 state. {C,D}: on input 0: C->D ({C,D}), D->C ({C,D}) same; on input 1: C->F ({E,F,G}), D->F ({E,F,G}) same. No split. So final partition = { {A}, {B}, {H}, {E,F,G}, {C,D} } with 5 equivalence classes. Minimal machine has 5 states: A, B, H, EFG, CD.