0
$\begingroup$

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.

Edit after comments

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 ?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Patrick87 Jun 13 '14 at 21:03
  • $\begingroup$ @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. $\endgroup$ – user19369 Jun 13 '14 at 21:27
  • $\begingroup$ Hint: In LaTeX, type \{ ... \} for sets. $\endgroup$ – Raphael Jun 13 '14 at 21:37
  • $\begingroup$ ... 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. $\endgroup$ – Patrick87 Jun 13 '14 at 21:43
  • $\begingroup$ Could someone tell me why I got minus for this question ? $\endgroup$ – user19369 Jun 13 '14 at 21:45
0
$\begingroup$

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 ?

$\endgroup$

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.