Proving that $a^{2^kp}$ isn't context-free (where $p$ goes over all primes)

Question

I have this language and have to prove that its not context free:

$$L = \{a^{2^kp } \mid k \in \mathbb{N}, p \text{ is prime number}\}.$$

Because it's unary, a context free language is also regular, so it should be enough to prove that this language isn't regular.

Proving $a^p$ and $a^{2^k}$ aren't regular is simple. But how do I prove it with the "product" of these two?

My thought was, because $a^{2^k}$ isn't regular and also not context free, if $a^{2^k}$ were regular/context free, concatenating this language $p$ times, we would deduce that the above language would also be regular/contextfree, because regular and CFL are closed under concatenation. But because $a^{2^k}$ isn't regular/context free, the $p$-times concatenation of this also isn't regular/context free.

Is my attempt correct?

Answer 1

Your attempt is wrong for several reasons:

1. If $L$ isn't regular then it doesn't mean that $L^p$ isn't regular. For example, let $L = \{ a^{n^2} : n \geq 0 \}$. Then $L$ isn't regular but $L^4$ is regular.

2. The language $L^p$ (the concatenation of $p$ copies of $L$) is not the same as the language $\{ w^p : w \in L \}$. For example, $\{a,aa\}^2 = \{a,aa,aaa,aaa\}$ whereas $\{ w^2 : w \in \{a,aa\} \} = \{aa,aaaa\}$.

3. To obtain your language from $L' = \{ a^{2^n} : n \geq 0 \}$ you will need to take the union of infinitely many powers of $L'$. There is usually very little you can say about infinite unions, since every language can be written as an infinite union of words.

One way to show that your language isn't regular is using the following criterion:

Suppose that $L = \{ a^i : i \in S \}$ is an infinite regular language. Then $|S \cap \{1,\ldots,n\}|/n$ tends to a positive rational limit.

This criterion follows from the fact that $L$ is regular iff $S$ is eventually periodic.

The Erdős–Kac theorem implies that the fraction of numbers in $\{1,\ldots,n\}$ with at most two distinct prime factors tends to 0. In particular, if $S = \{ 2^k p : k \geq 0, p \text{ prime} \}$ then $|S \cap \{1,\ldots,n\}|/n \longrightarrow 0$. Since $L$ is infinite, the criterion shows that it is not regular.

Answer 2

Since every context-free language over a one-symbol alphabet is regular (see this question), it suffices to show that your language isn't regular. Assume it is and denote by $n$ the integer of the pumping lemma for regular languages and pump the string $s=2^kp$ where $k$ is chosen to be less than $\log_2n$. From here, the proof runs exactly as the standard proof for the language $\{a^{2^k}\mid k>0\}$.