# How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free?

I have following language $$L:= \{a^n b^n c^m \mid n \neq m; n,m \ge 0 \}$$ and would like to use proof by contradiction by applying Pumping Lemma for CFLs to show that $$L$$ is not a CFL.

In any case, i need to choose $$w = uv^iwx^iy$$ so that $$w \in L$$.

I tried $$a^p b^p c^{p+1}$$ , $$a^p b^p c^{p+p!}$$ ($$p$$ - Pumping Length) and couple of others. All of my proofs converged to 5 cases:

1. Only A (both $$v$$ and $$x$$ pump $$a$$'s),
2. A & B ($$v$$ pumps $$a$$'s, $$x$$ pumps $$b$$'s),
3. Only B (both - $$b$$'s),
4. B & C ($$v$$ - $$b$$'s, $$x$$ - $$c$$'s),
5. Only C (both - $$c$$'s).

Cases #1-#4 are not a problem, but in #5 $$w \in L$$ regardless $$i$$ chosen (cause condition is not broken). Thus, how do i choose the word here?

Your analysis is correct. In order to keep the $$a^n b^n c^m$$ structure of the string, the only ways to pump are case (2) pump both $$a$$'s and $$b$$'s, or case (5) pump only $$c$$'s. All other case will distroy the structure of the string.
You applied the $$p!+p$$-trick, and consider the string $$a^p b^p c^{p!+p}$$. In case (2) this will indeed pump to a string of the form $$a^{p!+p} b^{p!+p} c^{p!+p}$$ outside of the language because all segments are of equal length. No luck in case (5), you are right.
The solution is to apply Ogden's Lemma. The Lemma is like the common Pumping Lemma for CF languages where we count so called "marked" positions in a word. By marking the $$a$$'s in the string one is forced to pump $$a$$'s, so only case (2) applies.
• Thanks for quick answer! I tried to understand Ogden's Lemma alone, but have no materials that explain it in simplified way :( So, we have w = $a^p b^p c^{p! + p}$. Then we apply Ogden's Lemma and mark $a$'s. After that we apply conditions of Ogden's Lemma ($vxy$ has $\leq$ p $a$'s & $vy$ has $\geq$ 1 $a$'s & $uv^i x y^i z \in L$. Altogether it means we pump $a$'s, leaving $b$'s and $c$'s constant, thus coming to (1) & breaking it's condition successfully. Why are we allowed to ignore (5) while applying Ogden's Lemma though? Don't get it :( Sep 19 at 22:00