Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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)$.
