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?


1 Answer 1


No, reasoning with the complement will not work as context-free languages are not closed under complement.

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

  • $\begingroup$ Could I also say that $\bar{L} = \left\{a,b\right\}^* \setminus L$? $\endgroup$
    – cnmesr
    Dec 9, 2017 at 20:09
  • $\begingroup$ Euh? That is the definition of the complement. $\endgroup$ Dec 9, 2017 at 21:03
  • $\begingroup$ Is that a "yes"? :) $\endgroup$
    – cnmesr
    Dec 9, 2017 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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