Is the complement of {(a^nb^n)^m | n>0,m>0} context-free? I've been asked to decide whether a given language is CFL. If yes, I should find the grammar that creates it, and if not, I need to prove it (with the pumping lemma). 
The given language is the complement of the next language:
$L=\{(a^{n}b^{n})^{m} \mid n>0, m>0\}$. The alphabet is $\{a,b\}$.
I couldn't find any grammar that can create words of type $abaabb$ and also words of type $aabbb$. 
Any suggestions? 
 A: Let $L=\left\{(a^nb^n)^m:n,m\in\Bbb Z^+\right\}$ and $L'=\{a,b\}^*\setminus\left\{(a^nb^n)^m:n,m\in\Bbb Z^+\right\}$; we’re interested in whether $L'$ is context-free.
$L$ consists of those words having alternating blocks of $a$s and $b$s such that


*

*all of the blocks are the same positive length,  

*the first block is a block of $a$s, and  

*the last block is a block of $b$s.


From this characterization of $L$ it’s not hard to devise a test for membership in $L'$.


*

*The empty word $\epsilon$ is in $L'$.  

*Every word that begins with $b$ or ends with $a$ is in $L'$.  

*Every word that has a block of $a$s either immediately preceded or immediately followed by a block of $b$s of a different length is in $L'$. (By block I mean a maximal block: a string of consecutive $a$s or $b$s that cannot be extended to a longer such string.)  

*And finally, every word in $L'$ is in at least one of these three categories.


It’s easy to design a context-free grammar that produces every word in the first two categories. The third category is also context-free. Here’s a start on it: the grammar fragment
$$\begin{align*}
&S\to XbaaAbaY\mid aaAbaY\mid XbaaAb\mid aaAb\\
&A\to aAb\mid aA\mid\epsilon
\end{align*}$$
generates strings of the following forms, where $n>m$: $Xba^nb^maY$, $a^nb^maY$, $Xba^nb^m$, and $a^nb^m$. Provided that you give $X$ and $Y$ the right productions, these are all of the ways to have a block of $a$s followed by a shorter block of $b$s.
