Given $L=\{a^ib^jc^k | i\neq j \space and \space j=k\}$. Is this CFL? How do I write CFG for it or prove it with pumping lemma? Thanks.

  • 1
    $\begingroup$ Have you tried proving that this is not context-free using the pumping lemma? $\endgroup$ Oct 25, 2018 at 22:05
  • $\begingroup$ Since the fastest and accuratest universal gun, Yuval's is kicking in, I am leaving. (This comment may be deleted later.) $\endgroup$
    – John L.
    Oct 25, 2018 at 22:07
  • $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$
    – Raphael
    Oct 25, 2018 at 22:23

1 Answer 1


Suppose that $L$ were context-free. According to Ogden's lemma, there is a constant $p$ such that each word in $L$ with at least $p$ marked positions satisfies the constraints of the lemma. Consider the word $s = \underline{a^p}b^{p+p!}c^{p+p!}$, in which the underlined part is marked. According to Ogden's lemma, there is a decomposition $s = uvwxy$ in which $vx$ contains at least one $a$, and $uv^iwx^iy \in L$ for all $i \geq 0$. We now consider several cases:

  1. $x$ contains $b$s but not $c$s, or $c$s but not $b$s. Choosing $i = 0$, we obtain a word in which the number of $b$s differs from the number of $c$s, and so does not belong to $L$.

  2. $x$ contains both $b$s and $c$s. Choosing $i = 2$, we obtain a word not belonging to $a^*b^*c^*$, and so not belonging to $L$.

  3. $x$ contains no $b$s nor $c$s, and $v \notin a^*$. In this case $x = \epsilon$, and so $v$ must contain at least two different characters. Choosing $i = 2$, we again obtain a word not belonging to $a^*b^*c^*$, and so not belonging to $L$.

  4. $vx \in a^+$, say $vx = a^q$. Let $i = p!/q+1$. Then $uv^iwx^iy = a^{p+p!}b^{p+p!}c^{p+p!} \notin L$.

We have obtained a contradiction, and so $L$ is not context-free.


Not the answer you're looking for? Browse other questions tagged or ask your own question.