8
$\begingroup$

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.

$\endgroup$
  • $\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 '12 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 '12 at 8:44
8
$\begingroup$

Hint:

Yes

Solution:

$$\{(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.

$\endgroup$
  • 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 '12 at 9:42
  • $\begingroup$ I don't understand, I thought that the complement of a CFL wasn't CFL in general. Thank you $\endgroup$ – Andrés Felipe Téllez Crespo Jul 11 '12 at 21:55
  • $\begingroup$ $\{(a^n b^n)^n\}$ is not context-free, but its complement is. $\endgroup$ – sdcvvc Jul 11 '12 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 '12 at 7:19
  • $\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 '12 at 7:21

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.