$(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.

  • $\begingroup$ How would it work with only finite number of states? $\endgroup$ – Dmitri Urbanowicz Dec 27 '18 at 12:38
  • $\begingroup$ @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. $\endgroup$ – virmis_007 Dec 27 '18 at 14:34
  • $\begingroup$ 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$. $\endgroup$ – 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.


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.