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$
$\endgroup$
2
-
$\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$– RaphaelJul 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$– RaphaelJul 5, 2012 at 8:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
2$\begingroup$ Ooohhh! *facepalm* Maybe you want to add the central design trick; it might not be obvious for the novice. $\endgroup$– RaphaelJul 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$– sdcvvcJul 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$– RaphaelJul 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$– RaphaelJul 23, 2012 at 7:21