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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.