# Is a^mb^n where m=n^2 a CFL?

Is $$a^mb^n$$ where $$m=n^2$$ a CFL?

I have a doubt regrading this problem. Say if we pop $$n$$ number of $$a's$$ from the stack for each $$b$$ then it is a CFL (to be exact DCFL) right?

On the other hand I have this doubt, do we know the number of $$b's$$ we are provided with, if not how can we pop $$n$$ number of $$a's$$ for each $$b$$? So this case doesn't make it a CFL right?

Which of these 2 cases are applicable? Are we always aware of the number of $$b's$$ we have? Then shouldn't it be a regular language?

• Did you try the pumping lemma? – narek Bojikian Dec 27 '19 at 14:48

This is not a context-free language, as an immediate consequence of Parikh's theorem.

In terms of pushdown automata, there is no way for a PDA to keep track of the number of $$b$$'s in the string in a way it can access repeatedly while reading (or popping) the $$a$$ part of the string. This is an essential feature of context-free languages; it is the same reason why languages such as $$\{a^n b^n c^n d^n | n > 0\}$$ are not context-free.

For more examples, check out our reference question on proving languages are not context-free.

• Thanks a lot.. :) – Turing101 Dec 28 '19 at 4:45

Here is an alternative argument. Let $$h$$ be the homomorphism given by $$h(a) = \epsilon$$, $$h(b) = b$$. Then $$h(L) = \{ b^{n^2} : n \geq 0 \}.$$ If $$L$$ were context-free, then $$h(L)$$ would be unary context-free, and so regular. But $$h(L)$$ is not eventually periodic.

You can also show that $$h(L)$$ is not context-free using the pumping lemma. The pumping lemma gives us a constant $$p$$ such that $$b^{p^2}$$ can be partitioned into $$uxyzw$$, where $$|xyz| \leq p$$, $$|xz| \neq 0$$, and $$ux^iyz^iw \in h(L)$$ for all $$i \geq 0$$. Let $$|xz| = q$$. Then $$ux^2yz^2w = b^{p^2+q}$$, but $$p^2 < p^2+q \leq p^2 + p < p^2+2p+1 = (p+1)^2$$, and so $$b^{p^2+q} \notin h(L)$$.

• Right, thanks for the correction. – Yuval Filmus Dec 27 '19 at 21:01
• Thanks a lot.. :) – Turing101 Dec 28 '19 at 4:45