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!

  • 3
    $\begingroup$ 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? $\endgroup$ – Shaull Nov 29 '13 at 18:39
  • 1
    $\begingroup$ I'm afraid it's neither context-free, nor does it violate the pumping lemma. Try Ogden's lemma instead. $\endgroup$ – avakar Nov 29 '13 at 18:51
  • $\begingroup$ I think I came up with a pumping lemma proof. See below. $\endgroup$ – connorbode Nov 29 '13 at 22:07
  • $\begingroup$ Ah. I see what Ogden's lemma is. I thought this was just called pumping lemma for context-free languages. $\endgroup$ – connorbode Nov 29 '13 at 22:20
  • $\begingroup$ My bad, I totally forgot you can pump down. $\endgroup$ – 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.


The following is my attempt at an answer. I took a screenshot of my assignment, rather than retyping the proof into StackExchange.


My answer

  • $\begingroup$ Are the cases I've listed exhaustive? $\endgroup$ – connorbode Nov 29 '13 at 22:09
  • 2
    $\begingroup$ Please take the time and copy the text down for SE; as it is, it can neither be searched nor edited. $\endgroup$ – Raphael Jan 29 '14 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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