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.
Is this language Context-Free?
formal languages;context free;pumping lemma
Hint: YesSolution: $$\{(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.