This is the proof I came across:

$L=\{a^{x^j}|j\ge 0, 2\le x\in \mathbb N\}$ is a non-context-free language. Suppose otherwise, then let $n$ be the constant promised in the pumping lemma. Let's choose $z=a^{x^n}, 1<x, z\in L$ therefore exists a decomposition of $z$ into the following form: $z=uvwxy, u=a^{k_1},v=a^{k_2},w=a^{k_3},x=a^{k_4},y=a^{x^n-k_1-k_2-k_3-k_4}$

For $i=2: a^{x^n+k_2+k_4}\quad$ *

$$ x^n< x^n+k_2+k_4\le x^n+n<x^n+x^n\le x^{n+1}\quad ** $$ which means that the language is not context-free.

$L$ is contained in the union of all non-context-free languages and the union can be represented by the regular expression $a^+$ therefore the union is a context-free language (because it can be represented by reg. expression).

1) First I don't understand why we needed to bother with proving that $L$ is not context-free. Why couldn't we say from the very beginning that the union of all non-context-free languages is $a^+$ and therefore it's context-free?

2) Why for $i=2: a^{x^n+k_2+k_4}$? Is it because the length of $a^{x^n}$ without $k_2, k_4$ is $a^{x^n-k_2-k_4}$ and because $i=2$ then $a^{x^n-k_2-k_4+(2k_2+2k_4)}=a^{x^n+k_2+k_4}$?

3) In point ** we found an accurate upper bound for $x^n$ which is $x^{n+1}$. But it doesn't necessarily mean than the power of $x$ will be $n+1$ it's just an upper bound. Why is it enough for the proof?


1 Answer 1


I think you made a mistake in the definition of L.

The x should be fixed once and for all. Otherwise $L=a*$ and all your question just don't make sens.

Thus I assumed that you wanted to show that $L_x=\{ a^{x^j}|j\geq 0\} $ is non-context-free for $x\in\mathbb{N}$.

1) How do you know that " the union of all non-context-free languages is $a^+$"? I didn't know before knowing that the languages $L_x$ are non-context-free ...

2) yes

3) I think your confusion comes the confusion on the language definition. With the definition $L_x$ it should be clearer. If it is not please tell me.

  • $\begingroup$ Yes $x$ should be fixed but it can be any natural number. In my first subquestion I meant why $a^{x^j}$ accurately describes the language but $a^+$ does not. $\endgroup$
    – Yos
    Jan 28, 2019 at 16:19
  • $\begingroup$ I did understand the 3) point though now. Reading the inequality from right to left suddenly made more sense. $\endgroup$
    – Yos
    Jan 28, 2019 at 16:26
  • $\begingroup$ if you're interested I have an interesting question here: cs.stackexchange.com/questions/103502/… $\endgroup$
    – Yos
    Jan 28, 2019 at 16:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .