# Prove that $L = \{ a^nb^m : m = n^3 \}$ is not Context Free using Pumping Lemma

I have the following language:

$L = \left \{ a^nb^m : m = n^3, i,j > 0 \right \}$

Show that it is not Context Free using Pumping Lemma for Context Free Languages.

This is what I have done. I have no idea of what are those $i,j$ of the exercise.
Let $p = n$ so,

$\begin{array}{lcl}z & = & a^pb^{p^3}, \\ |a^pb^{p^3}| & = & p + p^3 > p, \\ a^pb^{p^3} & = & uv^2wx^2y, \\ |vwx| & < & p\end{array}$

the phrases are of the form:

$n = 0, z= \epsilon \\ n = 1, z = ab, \\ n=2, z= aabbbbbbbb, \\ n = 3, z = aaa\underbrace{bb \ldots bb}_{3^3=27}$

I have considered different cases based on what v and x can take:

$\mbox{case 1 - } \underbrace{aa \dots aabb}_{v}\underbrace{b \ldots b}_{w}\underbrace{bbbb}_{x} \\ \mbox{case 2 - } \underbrace{aa}_v \underbrace{\dots aabb}_w \underbrace{b \ldots bbbbb}_{x} \\ \mbox{case 3 - }\underbrace{aa}_v \underbrace{\dots a}_w \underbrace{aabbb \ldots bbbb}_{x}$

in case 1:
$v$ is formed by every $a$ of $vwx$ and some $b$s;
$x$ is formed by only $b$s;
therefore $w$ is formed by the remaining $b$s.

$vwx = a^lb^k$

with $v \ne \epsilon \mbox{ and } x \ne \epsilon$

$\begin{array}{lcl}v & = & a^lb^{k_1} \\ x & = & b^{k_2} \\ w & = & b^{k-k_1-k_2} \end{array}$

$uv^2wx^2y = a^{p+l}b^{p^3+k_1+k_2}$

with:

$\begin{array}{lcl}p+l & \ge & p + 1 & > & p \\ p^3+k_1+k_2 & \ge & p+2 & > & p\end{array}$

so if I understand the pumped word is still in the language if the following holds:

$\begin{array}{lcl}(p+l)^3 & = & p^3 + k_1 + k_2 \\ p^3 + 3p^2l + 3pl^2 + l^3 & = & p^3 + k_1 + k_2 \\ 3p^2l + 3pl^2 + l^3 & = & k_1 + k_2 \end{array}$

but I am unable to continue, how can I verify that equation? I have also tried another method:

$n=10, m= 10^3 = 1000 \\ a^{10}b^{1000} = uvwxy$

for example if I decompose the word in this way:

$\underbrace{a^4a^2}_u \underbrace{a^4b^{20}b^{10}}_v \underbrace{b^{50}b^{100}}_w \underbrace{b^{20}}_x \underbrace{b^{800}}_y$

if I go to pump it I obtain:

$\begin{array}{lcl} uv^2wx^2y & = & (a^4a^2)(a^4b^{20}b^{10})^2(b^{50}b^{100})(b^{20})^2(b^{800}) \\ & = & a^6a^8b^{40}b^{20}b^{50}b^{100}b^{40}b^{800} \\ & = & a^{14} b^{1050} \\ & \ne & a^n b^m, \forall n \end{array}$

the word is not in the language, in fact $14^3 \ne 1050$, so the language is not context free.

Can You help me? Thanks!

Note that in the given language a word length completely determines the actual word. We can enumerate the words, making $s_n = a^nb^{n^3}, \ L = \{s_n: n \in \Bbb N \}$. Now let's apply the pumping lemma.

Assume there $\exists p$ with all the mentioned properties. Then surely $|s_p| = p + p^3 > p$, and $s_p = uvwxy$ with, again, all the desired properties. Taking $n=2$ gives $s' = uv^2wx^2y \in L \implies |s'| = |s_p| + |vx| = m + m^3$ for some $m \in \Bbb N$. Clearly, since $|vx| \ge 1$, $|s'| = |s_p| + |vx| > |s_p| = p + p^3$, so $m > p$. Now,

$$m + m^3 \ge (p + 1) + (p + 1)^3 = p + 1 + p^3 + 3p^2 + 3p + 1 = (p + p^3) + 3p^2 + 3p + 2 = |s_p| + 3p^2 + 3p + 2$$

but

$$|s'| = |s_p| + |vx| \le |s_p| + p < |s_p| + 3p^2 + 3p + 2 \le m + m^3 \ \forall m > p$$

so $s' \notin L$.

• Sorry, what is $m+m^3$? – JB-Franco Oct 9 '17 at 11:40
• It is much easier to use Parikh's theorem to prove that $L$ is not context-free... – J.-E. Pin Oct 9 '17 at 12:56
• @J.-E.Pin yes thanks, but for me, the using of the Pumping Lemma for CF is mandatory, hence my question remains the same: in the above development what is $m+m^3$?. – JB-Franco Oct 9 '17 at 17:15
• @JB-Franco $m+m^3 : m \in \Bbb N$ is the theoretical length of $s'$ assuming $s' \in L$ since $\forall s \in L \exists m_s \in \Bbb N : |s| = m_s + {m_s}^3$ – cronos2 Oct 9 '17 at 17:26