1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Did you try the pumping lemma? $\endgroup$ – narek Bojikian Dec 27 '19 at 14:48
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks a lot.. :) $\endgroup$ – Turing101 Dec 28 '19 at 4:45
3
$\begingroup$

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

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

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.