Proving that the language $\{a^{i} b^{j} c^{k} : i < j < k\}$ is not Context Free using Pumping Lemma

2.6k Views Asked by At

$\textit{Proof}$. Let $A$ be the language $\{a^{i} b^{j} c^{k} : i < j < k\}$. We will use the Pumping Lemma to prove that $A$ is not Context Free Language (CFL). The proof is by contradiction.

Suppose that $A$ is CFL. Let $p$ be the Pumping length given by the Pumping Lemma. Let $s$ be the string $a^{p}b^{p+1}c^{p+2}$. Since $s \in A$ and $|s| \geq p$, the Pumping Lemma guarantees that $s$ can be divided into five pieces, $s = uvxyz$, satisfying the following conditions:

  1. for each $i \geq 0$, $uv^{i}xy^{i}z \in A$,
  2. $|vy| > 0$
  3. $|vxy| \leq p$

Thus, since $|vxy| \leq p$, we have the following cases:

  1. If $vxy$ has at least an $a$, then $vxy$ can only be a substring of $a^{p}b^{p+1}$, that is, we know that $vxy$ does not have $c's$, this way $uv^{2}xy^{2}z$ have at least $p+1\ a's$ and exactly $p+2\ c's$, which is impossible since the number of $c's$ must exceed the number of $a's$ in at least two units. Therefore, since $ uv^{2}xy^{2}z \notin A$, then condition 1 is violated and thus we have a contradiction.
  2. if $vxy$ does not have $a's$, then $vxy$ can only be a substring of $b^{p+1}c^{p+2}$. In such case, $uv^{0}xy^{0}z = uxz$ will have less than $p + 1\ b's$ or less than $p + 2\ c's$, however, in any case it will have exactly $p\ a's$. This situation is also impossible, and therefore $uxz \notin A$. Thus condition 1 is violated and then we have a contradiction.

Since we analyzed all possible cases and in all cases a contradiction was inevitable, then we can conclude that $A$ is not CFL. $\square$

I tried to write it as simple as possible with the intention to not have a big proof covering too many cases. But I am not so sure this is correct in the simplified form I attempt to do.