# Prove or disprove: Complement of language $L=\left\{baba^2ba^3b…ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is context-free

Prove or disprove: Complement of language $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is context-free.

I'm not quite sure how this is done. I would first try to find out whether $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ itself is context-free.

The language creates words $x$ of length $|x|= n+1+\frac{n(n-1)}{2}= \frac{n(n+1)}{2}$

So $L$ is not context-free. But I was looking for the complement of $L$, i.e. $\bar{L}$, the language.

Is it possible to argue that $\bar{L}$ is context-free because $L$ is not?

Or how would you show it better?

Consider an alternative description of $L$: it consists of all strings $ba^{a_1}ba^{a_2} \dots ba^{a_n}b$ such that (1) $a_1 =1$ and (2) for all $1\le k<n$, $a_{k+1} = a_k+1$.
• Could I also say that $\bar{L} = \left\{a,b\right\}^* \setminus L$? – cnmesr Dec 9 '17 at 20:09