GATE CS 2011 Q45 — Regular Expressions and Finite Automata

To find the minimal DFA, we partition the states of the given DFA $D$ using the state minimization algorithm.

Let the states of the given DFA $D$ be:

• $q_0$ (Start state, non-accepting)
• $q_1$ (Non-accepting state)
• $q_2$ (Accepting state)

The transition table for $D$ is:

Step 1: Initial Partition ($P_0$)
Divide the states into non-accepting and accepting sets:$$P_0 = \{ \{q_0, q_1\}, \{q_2\} \}$$

Step 2: Check equivalence of $q_0$ and $q_1$
For input $a$:$$\delta(q_0, a) = q_1 \in \{q_0, q_1\} \quad \text{and} \quad \delta(q_1, a) = q_1 \in \{q_0, q_1\}$$For input $b$:$$\delta(q_0, b) = q_2 \in \{q_2\} \quad \text{and} \quad \delta(q_1, b) = q_2 \in \{q_2\}$$Since both $q_0$ and $q_1$ transition to the same state groups for all inputs, they are equivalent ($q_0 \equiv q_1$).

Step 3: Minimal DFA States and Transitions
The minimal DFA has two states:

• State $A = \{q_0, q_1\}$ (Start state, non-accepting)
• State $B = \{q_2\}$ (Accepting state)

• From $A$: on $a \to A$, on $b \to B$
• From $B$: on $a \to A$, on $b \to B$