GATE CS 2008 Q9 — Regular and Context-free Languages

Let the language be $L = \{ a^p \mid p \text{ is a prime } \} = \{ a^2, a^3, a^5, a^7, a^{11}, \dots \}$.

We can analyze the properties of $L$ as follows:

1. Not Regular: We can prove this using the Pumping Lemma for regular languages. Suppose $L$ is regular with pumping length $n$. Choose a prime $p \ge n+2$. Let $w = a^p \in L$. We split $w = xyz$ such that $|xy| \le n$ and $|y| = k \ge 1$. According to the pumping lemma, $xy^iz \in L$ for all $i \ge 0$. The length of $xy^iz$ is $p + (i-1)k$. If we choose $i = p+1$, the length becomes $p + pk = p(1+k)$. Since $p \ge 2$ and $1+k \ge 2$, the length $p(1+k)$ is a composite number. Thus, $a^{p(1+k)} \notin L$, which is a contradiction. Hence, $L$ is not regular.


2. Not Context-Free: By Parikh's Theorem, any context-free language over a unary alphabet (a single-letter alphabet like $\{a\}$) must also be regular. Since $L$ is over a unary alphabet and is not regular, it cannot be context-free.


3. Accepted by a Turing Machine: Primality testing is a decidable problem. We can easily construct a Turing Machine that, given an input $a^m$, systematically tests if $m$ has any divisors other than $1$ and $m$ (by simulating division). Since the TM halts and accepts if $m$ is prime, the language is recursive (and hence accepted by a Turing Machine).

Thus, the language is neither regular nor context-free, but it is accepted by a Turing machine.