2
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • 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, 2013 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, 2013 at 18:51
  • $\begingroup$ I think I came up with a pumping lemma proof. See below. $\endgroup$
    – connorbode
    Nov 29, 2013 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, 2013 at 22:20
  • $\begingroup$ My bad, I totally forgot you can pump down. $\endgroup$
    – avakar
    Nov 29, 2013 at 22:51

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
-2
$\begingroup$

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

Comments?

My answer

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are the cases I've listed exhaustive? $\endgroup$
    – connorbode
    Nov 29, 2013 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, 2014 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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