[Math] Is the complement of {(a^nb^n)^m | n>0,m>0} context-free

Question

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?

Answer 1

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.