GATE CS 2006 Q34 — Regular Expressions and Finite Automata

The regular language is defined over the alphabet $\Sigma = \{1\}$ as $L = (111 + 11111)^*$. The lengths of the strings in $L$ are of the form $3a + 5b$ for non-negative integers $a, b \ge 0$.

Using the Frobenius coin problem, the largest integer that cannot be expressed as $3a + 5b$ is: $$3 \times 5 - 3 - 5 = 7$$ Thus, all strings of length $n \ge 8$ belong to $L$. Let us list the membership of $1^n$ in $L$ for $n \ge 0$:

• $n \in L$: $\{0, 3, 5, 6, 8, 9, 10, 11, \dots\}$
• $n \notin L$: $\{1, 2, 4, 7\}$

To find the minimum number of states in the DFA, we determine the equivalence classes of the Myhill-Nerode relation. Let $q_i$ represent the state reached after reading a string of length $i$ for $0 \le i \le 8$:

• $q_0, q_3, q_5, q_6, q_8$ are accepting states.
• $q_1, q_2, q_4, q_7$ are non-accepting states.

Thus, there are exactly $9$ states in the minimal DFA.