0
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by Raphael Oct 25 '18 at 22:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Have you tried proving that this is not context-free using the pumping lemma? $\endgroup$ – Yuval Filmus Oct 25 '18 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$ – Apass.Jack Oct 25 '18 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 '18 at 22:23
0
$\begingroup$

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.

$\endgroup$

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