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?


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 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 at 16:26
  • $\begingroup$ if you're interested I have an interesting question here: cs.stackexchange.com/questions/103502/… $\endgroup$ – Yos Jan 28 at 16:27

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.