Proving a Context Free Language

Question

I need to prove whether a Language L = $a^ib^jc^k$ ( with i = j x k ) is context Free. I am using the pumping lemma to prove that this is not a CFL. Currently I have been able to prove in the decomposition uwxyz if w and y is in one of the following formats (i) only a s (ii) only b s (iii) only c s (iv) w is $a^q$ and y is $b^s$. Pumping down or up will cause us to move out of L.

But in the case (v) w is $a^q$ and y is $c^s$ . I am having trouble proving that pumping up or down will move us out of L.

So far, What I have is that if s = uwxyz in L

(p+q+r)j = (l+s+t)

$u = a^p$ $w = a^q$ $x = a^rb^jc^l$ $y = c^s$ $z = c^t$

and if $s. = uw^ixy^iz$ also in L

(p+iq+r)j = (l+is+t)

Substracting the 2 equations give me jq(i-1) = (i-1)s

Since i isn't equal to 1. When pumping up or down. If i choose a q and s such that jq = s. Pumping up or down keeps me in L.

Have I made an error in my assumptions anywhere. Or is there A CFL that can represent L ?

Answer 1

For arbitrary words and foctorizations the pumping lemma does not necessarily lead out of the language. There are several conditions which you are not using:

1. There is a constant $N$ such that the pumping condition applies only to words from $L$ which are longer than $N$.
2. $|wxy|<N$.

You only need to find one example word where pumping does not work. Assuming that your reasoning for your cases (i) through (iv) works, choose a word with $j>N$. Then the condition $|wxy|<N$ makes your case (v) impossible, because the two pumping factors cannot be that far apart.