# $L = \{ a^{j!} \mid j \geq1\}$ is not context free by pumping lemma

How I use the pumping lemma to prove that the language $$L = \{ a^{j!} \mid j \geq1\}$$ is not context-free?

Suppose $$L$$ is context free. Then, by pumping lemma, there exist two integers $$h \ge 1$$ and $$1 \le x \le \min\{h!, c_L\}$$, where $$c_L$$ is a constant depending on $$L$$, that satisfy the following:

• $$a^{h!} \in L$$
• $$a^{h!-x} a^{xn} \in L$$ for every $$n \ge 0$$.1

Now you only need to show that, for some value of $$n$$, $$a^{h!-x} a^{xn} \not\in L$$. Equivalently, you want to find a value of $$n$$ (possibly depending on $$h$$) such that $$h! + (n-1)x$$ cannot be written as $$j!$$ for any integer $$j \ge 1$$.

For example, if $$h = 1$$ then $$x=1$$ so you can pick $$n=0$$ to obtain $$h! + (n-1)x = 0$$.

When $$h \ge 2$$, you can pick $$n=2$$ so that $$h! + (n-1)x = h! + x$$, which is not a factorial of an integer as the following inequalities show: $$h! < h! + x \le 2 \cdot h! < (h+1)!$$

1. This is a consequence of the general form of the pumping lemma and of the fact that all the words in your language contain only the character a.