GATE CS 2000 Q1.5 — Regular and Context-free Languages

To find the language $L$ generated by the given grammar, let us derive a few strings:

• $S \to 00$ (length 2)
• $S \to 0S0 \to 0(00)0 = 0000$ (length 4)
• $S \to 0S0 \to 0(0S0)0 \to 00(00)00 = 000000$ (length 6)

In general, each application of the rule $S \to 0S0$ adds one $0$ to the left and one $0$ to the right, increasing the length of the string by $2$. The derivation terminates with the rule $S \to 00$, which contributes two $0$s.

Thus, the language generated is the set of all even-length strings of $0$s: $$L = \{ 0^{2n} \mid n \ge 1 \} = (00)^+$$

Let us evaluate the options:

• Option A ($L = 0^+$): Incorrect. $0^+$ contains strings of odd length (e.g., $0, 000$), which are not present in $L$.
• Option B ($L$ is regular but not $0^+$): Correct. Since $L$ can be represented by the regular expression $(00)^+$, it is a regular language, and it is not equal to $0^+$.
• Option C ($L$ is context free but not regular): Incorrect. Every regular language is also context-free, but since $L$ is regular, the "not regular" part makes this statement false.
• Option D ($L$ is not context free): Incorrect. Since $L$ is regular, it is also context-free.