Using the Pumping Lemma to Prove $L = \{a^ib^jc^k \mid k = i*j\}$ is not Context-Free

Question

I want to use the Pumping Lemma to prove that

$$L = \{a^ib^jc^k \mid k = i*j\}$$

is not context-free. I think I have the intuition, but I don't know how to prove it. Help?

Answer 1

Part of on how to the proof $L$ is not context-free.

Assume L is context-free and prove it's not

To prove that $L$ is not context-free we use the Pumping Lemma for context-free languages. We assume that $L$ is a context-free language and by obtaining a contradiction to prove that $L$ is not a context-free language.

define the pumping length, this is something that should exists if $L$ is context free, we don't really care what that value could be. We only care whether it exist or not.

Let $p$ be the pumping length for $L$ that is guaranteed to exists by the pumping lemma, such that $p \geq 1$

Define a string that $\in L$ that we can "pump". We want some string of at length $> p$ so that we can divide it in the given format, then pump it and show we always end up with contradicting one of the conditions of the pumping lemma. We will take the subset of string in $L$ where $i$, $j$ are equal such that we have as many $a's and b's $ as that we have $c's$

Let $s = a^p b^p c^{p^2} \in L$

Because $s \in L$ and the length of $s$ will always be greater than $p$ we may divide $s$ into five pieces $s = uvxyz$ that satisfy the following conditions:

1. for each $i \geq 0$, $uv^ixy^iz \in L$
2. $|vy| > 0$, ( $v$ and $y$ cannot both be the empty string) and
3. $|vxy| \leq p$ (the length of $vxy$ can be at most $p$)

Show that all possible cases you can divide your $s$ into the five pieces as stated by the lemma, yet for each case you end up pumping by a certain value for $i$ such that you end up with a string that $\notin L$

Description of cases

Take $p=4$ then our string looks like $aaaa\ bbbb\ cccc\ cccc\ cccc \in L$ Note the spaces are for readability only We divide our string in two ways such that we satisfy both condition 2 and 3 of

Case 1 $vxy$ contains one symbol:

$v$ and $y$ contain both: only a's, only b's or only c's so you have $vxy = "aaaa" \lor "bbbb" \lor "cccc"$

Case 2 : $v$ contains a's and b's and $y$ contains b's

we take $vxy = "ab\ b\ b"$

Case 3 : $v$ contains b's and c's and $y$ contains c's

we take $vxy = "bb\ b\ c"$

These are the cases I find. Because of the pumping length we have that our $vxy$ can never have all three symbols, since there are exactly the same amount of b's a any chosen P.

Then for each take $i \geq 0$, $uv^ixy^iz \notin L$ to show we always have a $i$ that contradicts with condition 1 of the lemma since our string $\notin L$ anymore.

For case 1 take some number like $i = 10$

You have a string with more a's such that the string $\notin L$ anymore.

case 2: take some number like $i = 10$

You have a string with more a's and b's such that the string $\notin L$ anymore.

case 3: take some number like $i = 10$

You have a string with more b's and c's such that the string $\notin L$ anymore.

Because one of these cases must always happen you will always have a contradiction as result, thus an contradiction is unavoidable. So the assumption that $L$ is a context-free language must be false. Thus we have proved $L$ is not a context-free language.

Answer 2

Hint. Use Parikh's theorem on the commutative image of context-free languages.