GATE CS 2017 Set 2 Q40 — Regular and Context-free Languages

Let us analyze each language and the corresponding statements:

• Language $L_1 = \{a^p \mid p \text{ is a prime number}\}$:
  By Parikh's Theorem, any context-free language over a unary alphabet (single-letter alphabet) must be regular. Since the set of prime numbers does not form an arithmetic progression, $L_1$ is not regular. Consequently, $L_1$ cannot be context-free either.
  Therefore, Statement I ("$L_1$ is context free but not regular") is incorrect.


• Language $L_2 = \{ a^nb^mc^{2m} \mid n \geq 0, m \geq 0 \}$:
  In $L_2$, the number of $a$'s is independent of $b$'s and $c$'s, and we only need to match the number of $c$'s to twice the number of $b$'s. This can be easily done using a single stack (pushing two symbols for every $b$ and popping one for every $c$).
  We can write a Context-Free Grammar (CFG) for $L_2$: $$S \to A B$$ $$A \to aA \mid \epsilon$$ $$B \to bBcc \mid \epsilon$$ Since $L_2$ is context-free, Statement II ("$L_2$ is not context free") is incorrect.


• Language $L_3 = \{a^n b^n c^{2n} \mid n \geq 0 \}$:
  $L_3$ requires matching three counts simultaneously ($n$ $a$'s, $n$ $b$'s, and $2n$ $c$'s), which cannot be done with a single stack. Thus, $L_3$ is not context-free (can be formally proven using the pumping lemma for CFLs). However, it is easily decidable by a Turing machine, meaning it is a recursive language.
  Therefore, Statement III ("$L_3$ is not context free but recursive") is correct.


• Language $L_4 = \{ a^n b^n \mid n \geq 1\}$:
  This is a standard deterministic context-free language (DCFL) because we can construct a Deterministic Pushdown Automaton (DPDA) that pushes $a$'s onto the stack and pops them upon reading $b$'s.
  Therefore, Statement IV ("$L_4$ is deterministic context free") is correct.

Since only statements III and IV are correct, the correct option is D.