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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.