GATE CS 2007 Q75 — Regular Expressions and Finite Automata

To find the number of states in the minimum state automaton, we can use the state minimization algorithm (partition refinement method).

Let the states of the given DFA be $q_0, q_1, q_2, q_3$, where $q_0$ is the start state, and the final states are $F = \{q_0, q_2\}$. The transition rules from the given diagram are:

• $\delta(q_0, a) = q_1$, $\delta(q_0, b) = q_2$
• $\delta(q_1, a) = q_2$, $\delta(q_1, b) = q_3$
• $\delta(q_2, a) = q_3$, $\delta(q_2, b) = q_0$
• $\delta(q_3, a) = q_0$, $\delta(q_3, b) = q_1$

Step 1: 0-equivalence Partition ($P_0$)
Divide the states into final and non-final states:
$P_0 = \{ \{q_0, q_2\}, \{q_1, q_3\} \}$

Step 2: 1-equivalence Partition ($P_1$)
We check if the states in each group behave identically on all inputs:

• For $\{q_0, q_2\}$:
  On input $a$: $\delta(q_0, a) = q_1$ and $\delta(q_2, a) = q_3$. Both $q_1, q_3$ belong to the same group $\{q_1, q_3\}$.
  On input $b$: $\delta(q_0, b) = q_2$ and $\delta(q_2, b) = q_0$. Both $q_2, q_0$ belong to the same group $\{q_0, q_2\}$.
  Thus, $q_0 \equiv q_2$.
• For $\{q_1, q_3\}$:
  On input $a$: $\delta(q_1, a) = q_2$ and $\delta(q_3, a) = q_0$. Both $q_2, q_0$ belong to the same group $\{q_0, q_2\}$.
  On input $b$: $\delta(q_1, b) = q_3$ and $\delta(q_3, b) = q_1$. Both $q_3, q_1$ belong to the same group $\{q_1, q_3\}$.
  Thus, $q_1 \equiv q_3$.

Since the partition does not split further, $P_1 = P_0 = \{ \{q_0, q_2\}, \{q_1, q_3\} \}$. The minimum state automaton has exactly 2 states.