Construct PDA for $Σ^* -\{(a^nb) ^n, n>0\}$
If a word is not of the form $(a^nb)^n$ for $n &gt; 0$, then one of the following must happen:

The word is not of the form $(a^*b)^+$, i.e., it is either empty or ends in $a$.
The word is of the form $a^ib(a^*b)^*a^jb(a^*b)^*$ for some $i \neq j$.
The word is of the form $a^nb (a^*b)^k$, where $n \neq k+1$.

Each of these can be checked by a PDA or generated by a CFG. It might help to break a condition of the form $i \neq j$ into two alternatives, $i &gt; j$ and $i &lt; j$.
To see why this case distinction holds, let us assume that the word is of the form $(a^*b)^+$. We can write it as
$$
a^{i_1} b a^{i_2} b \cdots a^{i_m} b.
$$
The word is of the form $(a^nb)^n$ if $i_1 = \cdots = i_m = m$, which is equivalent to
$$
i_1 = i_2 \text{ and } i_1 = i_3 \text{ and } \cdots \text{ and } i_1 = i_m \text{ and } i_1 = m.
$$
Hence the word is not of the form $(a^nb)^n$ if
$$
i_1 \neq i_2 \text{ or } i_1 \neq i_3 \text{ or } \cdots \text{ or } i_1 \neq i_m \text{ or } i_1 \neq m.
$$
The case $i_1 \neq i_j$ is handled by the second bullet above, and the case $i_1 \neq m$ is handled by the third bullet.
(Thank you to Hendrik Jan for help with simplifying the cases.)