# Proof that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a CFL

I want to prove that $$L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$$ is a Context Free Language.

so far, I tried to find a Context Free Grammar for $$L$$ or to use properties of Context Free Languages but have not been successful yet.

Any guidance and explanation would be greatly appreciated.

Suppose that $$w$$ is in the language. We can write $$w$$ as a concatenation of runs: $$w = a^{i_1} b^{j_1} a^{i_2} b^{j_2} \dots a^{i_m} b^{j_m},$$ where all indices other than possibly $$i_1,j_m$$ are strictly positive.

A word of this form belongs to $$(a^nb^n)^m$$ if all indices are equal. Since $$w$$ is in the language, there must exist two indices which are different. There are several cases to consider:

1. $$w = \epsilon$$.
2. $$i_1 = 0$$ and $$w \neq \epsilon$$. In other words, $$w$$ starts with $$b$$.
3. $$j_m = 0$$ and $$w \neq \epsilon$$. In other words, $$w$$ ends with $$a$$.
4. $$i_s \neq i_t$$ for some $$s < t$$. The word is thus of the general form $$(a+b)^*ba^xb^+(a^+b^+)^*a^yb(a+b)^*,$$ where $$x \neq y$$.
5. $$j_s \neq j_t$$ for some $$s < t$$. This is similar to the preceding case.
6. $$i_s \neq j_t$$ for some $$s \leq t$$. The word is thus of the general form $$(a+b)^*ba^x(b^+a^+)^*b^ya(a+b)^*,$$ where $$x \neq y$$.
7. $$j_s \neq i_t$$ for some $$s < t$$. This is similar to the preceding case.

Starting with a context-free grammar for $$\{a^xb^y : x \neq y \}$$ (a standard exercise – separate into cases $$x and $$x>y$$), you can create a grammar covering all the cases above.