# Is the language with decreasing numbers of a, b and c context-free by pumping lemma?

So I've been given the following language on an assignment. It is the only question I have left of 10, and I've been racking my brains out trying to solve it for hours.

$$L=\{w:w\in(a+b+c)^*, n_a(w) > n_b(w)>n_c(w)\}$$

where $n_x(w)$ represents the number of character $x$ found in $w$. The problem statement is: prove or disprove that the language is context-free. Context-free grammars or pushdown automata are acceptable proofs. Use pumping lemma to disprove.

I've extensively explored both possibilities and I'm fairly certain that it is context-free.

The approach I've taken in finding a context-free grammar for the language involves using rules which preserve the constraint $n_a(w) > n_b(w) > n_c(w)$ (ie. whenever a $b$ is added, add an $a$; whenever a $c$ is added, add a $b$). Then, I've attempted to enforce that there are at least two $a$s and at least one $b$ (base case for the constraint).

The grammar I've used is:

$S\implies XaXaXbX | XaXbXaX | XbXaXaX$

$X \implies XX| A | B | C | \lambda$

$A \implies a$

$B \implies ab | ba$

$C \implies abc | acb | bac | bca | cab | cba$

(where $\lambda$ is the empty string)

My grammar fails for strings like $cccaaaaabbbb$.

I'm confused as to where to go from here.

I would really like a push in the right direction, not an answer. Any help is greatly appreciated!

• Are you aware that the language $a^n b^n c^n$ is not context free? are you familiar with the proof of this fact? – Shaull Nov 29 '13 at 18:39
• I'm afraid it's neither context-free, nor does it violate the pumping lemma. Try Ogden's lemma instead. – avakar Nov 29 '13 at 18:51
• I think I came up with a pumping lemma proof. See below. – connorbode Nov 29 '13 at 22:07
• Ah. I see what Ogden's lemma is. I thought this was just called pumping lemma for context-free languages. – connorbode Nov 29 '13 at 22:20
• My bad, I totally forgot you can pump down. – avakar Nov 29 '13 at 22:51

If your language is context free, so is its intersection with the regular language $a^* b^* c^*$. And your proof in the answer that this isn't context free does go through. Your proof omits the cases where one of the strings straddles the $a/b$ or $b/c$ boundaries. 