Is this language Context-Free?

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.

sdcvvc

Posted 2012-07-05T05:40:38.400

Reputation: 3 367

2Ooohhh! *facepalm* Maybe you want to add the central design trick; it might not be obvious for the novice. – Raphael – 2012-07-05T09:42:33.420

I don't understand, I thought that the complement of a CFL wasn't CFL in general. Thank you – Andrés Felipe Téllez Crespo – 2012-07-11T21:55:47.267

${(a^n b^n)^n}$ is not context-free, but its complement is. – sdcvvc – 2012-07-11T22:09:59.397

@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). – Raphael – 2012-07-23T07:19:42.540

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). – Raphael – 2012-07-23T07:21:30.293

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.

– Raphael – 2012-07-05T08:31:02.437

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. – Raphael – 2012-07-05T08:44:42.330

Is this language Context-Free?

Answers