How to prove this language is not context free?

Question

$$L=\{a^{nm} \mid \text{$n$ and $m$ are prime numbers}\}$$

How can i prove $L$ is not context free? I tried pumping lemma but couldn't find an i that $uv^ixy^iz \notin L$.

Any idea or hint on how to prove this?

Answer 1

We want to prove that, for arbitrarily large integers $n$ such that $n$ is the product of two primes, and for all non-negative integers $a,b,c,d, h$ such that $$\begin{cases}a+b+c+d+h=n\\ b+d\ge1\end{cases}$$

there is a positive integer $k$ such that $a+b+c+k(b+d)$ is not the product of two primes.

Since all the info is condensed in $a+b+c=u$ and $b+d=v$, we may just be looking for a $k$ for each $v$ and $u$ such that $u+v=n$ and $v\ge 1$.

Consider three distinct primes $p_1,p_2,p_3$ which do not divide $v$. You want to find $k$ such that $$kv+u\equiv 0\pmod {p_1p_2p_3}$$

Since $v\in \Bbb Z_{p_1p_2p_3}^*$, this is always possible. Explicitly, any positive integer in the form $$k\equiv -u\cdot v^{(p_1-1)(p_2-1)(p_3-1)-1}\pmod {p_1p_2p_3}$$ works. For instance, $k=(p_1^np_2p_3-u)\cdot v^{(p_1-1)(p_2-1)(p_3-1)}$.

Answer 2

A simple proof consists to use Parikh's theorem, which states that the commutative image of a context-free language is semilinear. In your case, this theorem implies that if your language is context-free, then the set $$ \{nm \mid \text{$n$ and $m$ are prime numbers} \} $$ is a finite union of arithmetic progressions, or equivalently, that your language is regular. Now, if your language were regular, its intersection with the regular language $(a^2)^*$ would also be regular, that is, the language $$ \{ (a^2)^p \mid \text{$p$ is a prime number} \} $$ would be regular. You should now be able to show that this is not the case.