# CFL, pumping lemma

I have difficulty with proving that the language $L = \{ a^p b^q | p \ge 1 , q \ge 1 , p \ge q^2 \vee q \ge p^2\}$

$w = uvxyz$

I've chosen word $w = a^{N^2} b^N$ where $N$ is a constant from pumping lemma and I proved cases where a $v,y$ is entirely in $a$ and $v,y$ is entirely in $b$ , but how to prove case where $v \in a$ and $y \in b$ ? I think that the word $w = a^{N^2} b^N$ isn't good, but I have no idea which one will be better.

After comments, my solution is :

$w = a^{n^2} b^N$ and $w = uvxyz$ , so $v = a^p$ and $y = b^q$ where $1 \leq p + q \leq N$ After pumping i-times I get $w_i = a^{n^2 + ip} b^{N+iq}$

so to prove that this word isn't in language I should choose i such as regardless of N,p,q it won't be true $N^2 + ip \ge (N+iq)^2$

$N^2 + ip \ge N^2 + 2Niq + i^2q^2$

$ip \ge 2Niq + i^2q^2$

for i = 1

$p \ge 2Nq + q^2$ which isn't true because $1 \leq p + q \leq N$

Is this correct ?

• The choice of word is fine. All you need to do is the following: show that you can pick a $k$ such that $N^2 + ki < (N + kj)^2$ regardless of the choice of $N, i, j$. Remember: $|vy| < N$ and $|v|, |y| \neq 0$. Assume the worst-case choice of $v$ and $y$ for this case: $|v| = N - 1$ and $|y| = 1$. You should find that the choice $k = N$ works. Please give this a try and, if it works, post an answer. – Patrick87 Jun 13 '14 at 21:03
• @Patrick87 I updated my question, because I can't post answer due to the fact that I am new user and I have to wait 8 hours. – user19369 Jun 13 '14 at 21:27
• Hint: In LaTeX, type \{ ... \} for sets. – Raphael Jun 13 '14 at 21:37
• ... looks OK to me :) Looks like the choice $k = 1$, as in your version, works just fine. There's no way to grow $\#_a$ fast enough when you add any $b$, since the number of $a$ you can add is limited by the pumping lemma. – Patrick87 Jun 13 '14 at 21:43
• Could someone tell me why I got minus for this question ? – user19369 Jun 13 '14 at 21:45

This answer is taken from the question (the user was unable to post as an answer at the time).

After comments, my solution is :

$w = a^{n^2} b^N$ and $w = uvxyz$ , so $v = a^p$ and $y = b^q$ where $1 \leq p + q \leq N$ After pumping i-times I get $w_i = a^{n^2 + ip} b^{N+iq}$

so to prove that this word isn't in language I should choose i such as regardless of N,p,q it won't be true $N^2 + ip \ge (N+iq)^2$

$N^2 + ip \ge N^2 + 2Niq + i^2q^2$

$ip \ge 2Niq + i^2q^2$

for i = 1

$p \ge 2Nq + q^2$ which isn't true because $1 \leq p + q \leq N$

Is this correct ?