$(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$
$\endgroup$
3
-
$\begingroup$ How would it work with only finite number of states? $\endgroup$– Dmitri UrbanowiczCommented Dec 27, 2018 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_007Commented Dec 27, 2018 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 UrbanowiczCommented Dec 28, 2018 at 7:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
