Is the language

$$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$$

context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.

  • $\begingroup$ Crossposted on math.SE; please don't do that! Did you check out the question I pointed you to? Please include your attempts and why they fail. $\endgroup$
    – Raphael
    Jul 5, 2012 at 8:31
  • $\begingroup$ Parikh's theorem works for $\{(a^nb^n)^n \mid n \geq 1\}$ but not for $L$; unfortunately, $\Psi_{\{a,b\}}[L] = \mathbb{N}^2$. Even the Interchange lemma seems to be fulfilled. Wow, nasty one. $\endgroup$
    – Raphael
    Jul 5, 2012 at 8:44

1 Answer 1





$$\{(a^n b^n)^n \mid n \geq 1 \} = \{a^{n_1} b^{n_2} \dots a^{n_{2k-1}} b^{n_{2k}}\}: k \geq 1 \land n_1 = k \land \forall i. n_i = n_{i+1} \}$$

and therefore the complement is

$$\{a,b\}^{\ast} \setminus \{(a^n b^n)^n \mid n \geq 1 \} = \{a^{n_1} b^{n_2} \dots a^{n_{2k-1}} b^{n_{2k}}: n_1 \neq k \lor \exists i. n_i \neq n_{i+1}\}$$

which is context-free as you can easily write a nondeterministic PDA.

  • 2
    $\begingroup$ Ooohhh! *facepalm* Maybe you want to add the central design trick; it might not be obvious for the novice. $\endgroup$
    – Raphael
    Jul 5, 2012 at 9:42
  • $\begingroup$ I don't understand, I thought that the complement of a CFL wasn't CFL in general. Thank you $\endgroup$ Jul 11, 2012 at 21:55
  • $\begingroup$ $\{(a^n b^n)^n\}$ is not context-free, but its complement is. $\endgroup$
    – sdcvvc
    Jul 11, 2012 at 22:09
  • $\begingroup$ @AndrésFelipeTéllezCrespo: The complement of a CFL is not always CFL (so no closure property) but nobody says that there is no CFL whose complement is CFL. In particular, all the complements of all regular languages are context-free (because they are even regular). $\endgroup$
    – Raphael
    Jul 23, 2012 at 7:19
  • 1
    $\begingroup$ Languages similar to $L$ -- a finite disjunction of suitable conditions -- can be solved by using nondeterminism: guess the violated condition and verify that it is violated (ignore the rest). $\endgroup$
    – Raphael
    Jul 23, 2012 at 7:21

Your Answer

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

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