GATE CS 2006 Q29 — Regular and Context-free Languages

To determine which language is not regular, we analyze each option based on whether it requires finite or infinite memory (states) to be recognized.

1. $L = \{ s \in (0+1)^* \mid n_{0}(s) \text{ is a 3-digit prime} \}$

   The set of 3-digit prime numbers is finite (ranging from $101$ to $997$). Since the number of $0$'s is restricted to a finite set of values and there is no restriction on $1$'s, a DFA only needs to count $0$'s up to $999$. Any count beyond $999$ can go to a dead state. Since this requires a finite number of states, the language is regular.

2. $L = \{ s \in (0+1)^* \mid \text{for every prefix } s' \text{ of } s, |n_{0}(s') - n_{1}(s')| \le 2 \}$

   This condition requires that at any point during the scanning of the string, the running difference between the number of $0$'s and $1$'s must stay within the range $[-2, 2]$. If the difference ever exceeds this range, the string is rejected. This can be tracked using a finite number of states (representing differences of $-2, -1, 0, 1, 2$, plus a dead state). Thus, the language is regular.

3. $L = \{ s \in (0+1)^* \mid |n_{0}(s) - n_{1}(s)| \le 4 \}$

   This condition only constrains the final difference of the entire string. During the processing of the string, the intermediate difference can grow arbitrarily large (for example, in the string $0^k 1^k$, the difference reaches $k$ before returning to $0$). To verify if the final difference is $\le 4$, a machine must keep track of an arbitrarily large difference, which requires infinite memory. Thus, this language is not regular.

4. $L = \{ s \in (0+1)^* \mid n_{0}(s) \bmod 7 = n_{1}(s) \bmod 5 = 0 \}$

   This language requires the number of $0$'s to be a multiple of $7$ and the number of $1$'s to be a multiple of $5$. This can be easily recognized by a DFA using the product construction with $7 \times 5 = 35$ states. Since it requires finite memory, the language is regular.