# Is the language $\{a^n b^n c^i | i \leq n\}$ context free?

I'm trying to apply the CFL pumping lemma. And, I've already tried words $a^pb^p$ and $a^pb^pc^p$. Not sure where to go from here.

• Hint: Try reversing the language first. – PMar Apr 11 '17 at 18:50
• Sometimes, the Pumping lemma is not strong enough. See our reference question for more approaches. (I guess Ogden's lemma would easily work here.) – Raphael Apr 11 '17 at 19:10
• Sometimes, it helps to realize that the pumping lemma also allow deleting the pumped segments: $uv^iwx^iy$ with $i=0$. – Hendrik Jan Apr 11 '17 at 19:27
• @PMar Context free languages are not closed under complement. I don't see how that helps. – Daniel Apr 12 '17 at 2:22

Classical pumping works. According to the pumping lemma we can find a segmentation $uvwxy$ such that $uv^iwx^iy$ is in the language for all $i$.

Start with your own suggestion $a^pb^pc^p$.

Three easy steps.

• Each of the "pumping segments" $v$, $x$ can only be within the boundaries of one the "letter segments" $a^p$, $b^p$, $c^p$.

• It is not possible to have one of $v$ or $x$ to be in the $a^p$ segment without the other being inside the $b^p$ segment. And the other way around. In that case pump down ($i=0$).

• Final possibility both $v$ and $x$ are in $c^p$. Pump up.