Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Possible Duplicate:
How to prove that a language is not context-free?

I'm having a hard time figuring this out, any help is appreciated.

Let EQUAL be the language of all words over $\Sigma = \{a,b,c\}$ that have the same number of $a$’s, $b$’s and $c$’s

$\qquad \text{EQUAL} = \{ w \in \Sigma^* \mid |w|_a = |w|_b = |w|_c \}$

The order of the letters doesn't matter. How can you prove that EQUAL is non-context-free?

share|improve this question

marked as duplicate by Raphael Nov 1 '12 at 14:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
Check the various methods given at this question –  Ran G. Nov 1 '12 at 6:31
    
It's actually an example in this answer. Closing as duplicate. –  Raphael Nov 1 '12 at 14:35

1 Answer 1

up vote 3 down vote accepted

It is known that the intersection of a context-free language with a regular language is context-free. If EQUAL were context-free, so would be its intersection with $a^*b^*c^*$, which is the well-known non-context-free $\{a^nb^nc^n : n \in \mathbb{N}\}$.

share|improve this answer