# How to disprove that the union of all non-context-free languages over $a$ is also non-context-free language?

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 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 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.

• 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.
– Yos
Jan 28, 2019 at 16:19
• I did understand the 3) point though now. Reading the inequality from right to left suddenly made more sense.
– Yos
Jan 28, 2019 at 16:26
• if you're interested I have an interesting question here: cs.stackexchange.com/questions/103502/…
– Yos
Jan 28, 2019 at 16:27