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