# Is the language $(a^n)^mb^n$ context free?

$$(a^n)^mb^n$$ for $$m,n\ge 1$$
This can be rewritten as $$a^{nm}b^n$$
i.e. number of $$a$$'s is a multiple of number of $$b$$'s, or for every m $$a$$'s there is one $$b$$. I thnk this language can be accepted by NPDA. For every m $$a$$'s one a can be pushed into the stack, and similarly one can be popped on encountering a $$b$$. But the NPDA needs to try this for every possible m, where m varies from 1 to maximum string length of $$a$$'s.

• How would it work with only finite number of states? – Dmitri Urbanowicz Dec 27 '18 at 12:38
• @DmitriUrbanowicz I thought that since a similar problem for finding m exists for the language $ww^R$ where m in this case is the number of characters after which the NPDA has to begin the reverse string comparison by popping out symbols from the stack; so, since the above language is CFL, this might qualify as one too. – virmis_007 Dec 27 '18 at 14:34
• For $ww^r$ there are finite number of transitions that do something to the stack. What you propose requires infinite number of transitions for every $m$. – Dmitri Urbanowicz Dec 28 '18 at 7:26

The difficulty of trying every possible $$m$$ is, in fact, insurmountable. That language is not context-free.
For the sake of contradiction, assume it is context-free. Let $$p$$ be its pumping length. Consider the word $$a^{p^2p}b^{p^2}$$. I will let you take it from here.