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

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?

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.)

• Can you explain how you reached to this decomposition? Also how to make a CFG for each of them? It doesn't look easy. – User584322 Apr 25 at 9:03
• It’s a case analysis. As to how to construct CFGs, it doesn’t look too hard. I trust that you can do it. – Yuval Filmus Apr 25 at 13:44
• But I couldn't do it. – User584322 Apr 25 at 14:08
• Well, I’m not going to do that for you. – Yuval Filmus Apr 25 at 14:22