# Prove by Pumping Lemma that Language $L=\{a^ib^kc^k : i\geq k\geq 1\}$ isn't Context-Free

I'm new to this forum. I have some difficulties on using Pumping Lemma to prove non-CF language.

Let $$L=\{a^ib^kc^k : i\geq k\geq 1\}$$ and the followings are my attempt.

Proof. Suppose by contradiction that $$L$$ is a context-free language. Let $$p$$ be the constant given by the P.L. We choose a string $$s=a^pb^pc^p$$. Assume $$s\in L$$ and it satisfies properties of a context-free language. i.e. $$s$$ can be written as $$s=uvwxy$$ where $$|v|\neq\varepsilon$$ and $$|x|\neq\varepsilon$$. Further $$|vwx|\leq q$$ and $$uv^iwx^iy\in L,\ \forall i\geq 0$$.

• If $$v$$ contains at most one symbol and $$x$$ contains at most one symbol (e.g. $$v=a$$, $$w=b$$, $$x=c$$.) Consider $$s=uv^0wx^0=b\notin L$$. And we reached contradiction.
• If $$v$$ contains more than one symbol or $$x$$ contains more than one symbol (e.g. $$v=ab$$, $$w=\varepsilon$$, $$x=ca$$.) Consider $$s=uv^2wx^2=ababcaca\notin L$$. And contradiction reached.

Therefore, the language $$L$$ is not context-free. Q.E.D.

I'm sure I could have missed important cases, and my confusion raises here as what is a general approach to find all cases that could be contradictions. Thanks.

• It looks like you have understood the pumping lemma pretty well. All advice you need is to proceed slowly and carefully. For example, there is no need to "Assume $s\in L$" since it is a fact. For example, where was $y$ when you reset $s$? – Apass.Jack Feb 27 at 21:40
• @Apass.Jack Thanks. That was some typographical errors. – tooooony Feb 27 at 22:14
• "If $v$ contains at most one symbol and $x$ contains at most one symbol (e.g. $v=a$, $w=b$, $x=c$.) Consider $s=uv^0wx^0=b\notin L$" Suppose $p=2$ and $v=a$, what happens? An example is good for understanding, but is generally excluded in proof. – Apass.Jack Feb 27 at 22:18