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?


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 '17 at 20:09
  • $\begingroup$ Euh? That is the definition of the complement. $\endgroup$ – Hendrik Jan Dec 9 '17 at 21:03
  • $\begingroup$ Is that a "yes"? :) $\endgroup$ – cnmesr Dec 9 '17 at 22:08

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.