GATE CS 1998 Q2.5 — Regular Expressions and Finite Automata

The language $L$ consists of all binary strings over the alphabet $\Sigma = \{0, 1\}$ that end with either $00$ or $11$. That is:

Let us construct the Deterministic Finite Automaton (DFA) for $L$ by tracking the suffix of the input string processed so far. We define the following 5 states:

• $q_0$: Start state (empty string $\epsilon$ processed).
• $q_1$: The string processed so far ends in $0$ (but not $00$).
• $q_2$: The string processed so far ends in $1$ (but not $11$).
• $q_3$: The string processed so far ends in $00$ (Accepting state).
• $q_4$: The string processed so far ends in $11$ (Accepting state).

The transition rules for these states are as follows:

To verify if this DFA is minimal, we check for equivalent states:

1. The accepting states $\{q_3, q_4\}$ cannot be merged because on input $0$, $q_3$ stays in an accepting state ($q_3$) while $q_4$ goes to a non-accepting state ($q_1$).
2. The non-accepting states $\{q_0, q_1, q_2\}$ cannot be merged because:
   • On input $0$, $q_1$ transitions to an accepting state ($q_3$) while $q_0$ and $q_2$ transition to non-accepting states.
   • On input $1$, $q_2$ transitions to an accepting state ($q_4$) while $q_0$ transitions to a non-accepting state.

Since no two states are equivalent, all $5$ states are pairwise distinguishable. Thus, the minimal DFA has exactly $5$ states.