Construct PDA for $Σ^* -\{(a^nb) ^n, n>0\}$

Question

I want to construct a PDA for $Σ^* -\{(a^nb) ^n, n>0\}$ where $Σ=\{a, b\}$. Here is my try: I know that context-free languages are closed under union operation. Also I know how to make a PDA for union. So I tried to decompose the given language to some parts. For example, the language of the strings starting by $b$, the language of strings ending with $a$, the language of strings containing $bab$ as a substring. I made a context-free grammar for these languages. Then I made PDAs based on each grammar and I combined them to get a PDA for the union of them. But I know that the union of these languages does not cover all strings in the given language. Could you help me find what I'm missing and how to make a context-free grammar for that?

Answer 1

If a word is not of the form $(a^nb)^n$ for $n > 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 > j$ and $i < 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.)