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.

| cite | improve this question | | | | |
  • $\begingroup$ 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$? $\endgroup$ – John L. Feb 27 '19 at 21:40
  • $\begingroup$ @Apass.Jack Thanks. That was some typographical errors. $\endgroup$ – tooooony Feb 27 '19 at 22:14
  • $\begingroup$ "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. $\endgroup$ – John L. Feb 27 '19 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.