GATE CS 2006 Q30 — Regular and Context-free Languages

To determine the class of the language $L$, we can analyze it as the intersection of two simpler languages:

Let $L_1 = \{ s \in (0+1)^* \mid d(s) \pmod 5 = 2 \}$.
We can construct a Deterministic Finite Automaton (DFA) with $5$ states (representing remainders $0, 1, 2, 3, 4$ modulo $5$) to recognize $L_1$. The transition from state $q$ on reading bit $b \in \{0, 1\}$ goes to state $(2q + b) \pmod 5$. Thus, $L_1$ is a regular language.

Let $L_2 = \{ s \in (0+1)^* \mid d(s) \pmod 7 \neq 4 \}$.
Similarly, the language $L_3 = \{ s \in (0+1)^* \mid d(s) \pmod 7 = 4 \}$ is regular because it can be recognized by a $7$-state DFA. Since regular languages are closed under complementation, its complement $L_2 = \overline{L_3}$ is also a regular language.

Since regular languages are closed under intersection, the language: $$L = L_1 \cap L_2$$ is also a regular language.