0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Sorry, what is $m+m^3$? $\endgroup$ – JB-Franco Oct 9 '17 at 11:40
  • $\begingroup$ It is much easier to use Parikh's theorem to prove that $L$ is not context-free... $\endgroup$ – J.-E. Pin Oct 9 '17 at 12:56
  • $\begingroup$ @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$?. $\endgroup$ – JB-Franco Oct 9 '17 at 17:15
  • 1
    $\begingroup$ @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$ $\endgroup$ – cronos2 Oct 9 '17 at 17:26

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.