GATE CS 2025 Set 1 Q49 — Regular Expressions and Finite Automata

To find the minimum number of states required to realize the given finite state machine (FSM), we use the state minimization algorithm (equivalence partitioning).

Step 1: $0$-equivalence partition ($P_0$)
We group the states based on their outputs for $X = 0$ and $X = 1$:

• States with output $(0, 0)$: $\{A, B, C, E\}$
• States with output $(1, 0)$: $\{D, H\}$
• States with output $(1, 1)$: $\{F\}$
• States with output $(0, 1)$: $\{G\}$

Thus, $P_0 = \{\{A, B, C, E\}, \{D, H\}, \{F\}, \{G\}\}$.

Step 2: $1$-equivalence partition ($P_1$)
We check the next-state transitions of states within each multi-state group of $P_0$:

• For group $\{A, B, C, E\}$:
  • $A \xrightarrow{0} F$ (Group $\{F\}$) and $A \xrightarrow{1} B$ (Group $\{A, B, C, E\}$)
  • $C \xrightarrow{0} F$ (Group $\{F\}$) and $C \xrightarrow{1} E$ (Group $\{A, B, C, E\}$)
  • $B \xrightarrow{0} D$ (Group $\{D, H\}$) and $B \xrightarrow{1} C$ (Group $\{A, B, C, E\}$)
  • $E \xrightarrow{0} D$ (Group $\{D, H\}$) and $E \xrightarrow{1} C$ (Group $\{A, B, C, E\}$)
  Since $A$ and $C$ transition to the same groups, and $B$ and $E$ transition to the same groups, this group splits into $\{A, C\}$ and $\{B, E\}$.
• For group $\{D, H\}$:
  • $D \xrightarrow{0} G$ (Group $\{G\}$) and $D \xrightarrow{1} A$ (Group $\{A, B, C, E\}$)
  • $H \xrightarrow{0} G$ (Group $\{G\}$) and $H \xrightarrow{1} A$ (Group $\{A, B, C, E\}$)
  Thus, $D$ and $H$ remain equivalent.

This gives $P_1 = \{\{A, C\}, \{B, E\}, \{D, H\}, \{F\}, \{G\}\}$.

Step 3: $2$-equivalence partition ($P_2$)
We check the transitions using the groups in $P_1$:

• For $\{A, C\}$: $A \xrightarrow{1} B$ and $C \xrightarrow{1} E$. Since $B$ and $E$ are in the same group $\{B, E\}$ in $P_1$, $A$ and $C$ remain equivalent.
• For $\{B, E\}$: $B \xrightarrow{1} C$ and $E \xrightarrow{1} C$. They transition to the same state, so they remain equivalent.
• For $\{D, H\}$: Both transition to $G$ on $0$ and $A$ on $1$, so they remain equivalent.

Since no further splitting occurs, $P_2 = P_1 = \{\{A, C\}, \{B, E\}, \{D, H\}, \{F\}, \{G\}\}$.

The minimized FSM has exactly 5 states.