Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can I prove that the language $L = \{w \mid \#a(w)=\#b(w)=\#c(w)\}$ is not context free using closure?

EDIT :

I know that the language $L_1 = \{a^i b^i c^i \mid i\geq 0\}$ is not a context free language. Now I'm trying to find another language $L_2$, where $L_2$ would be a regular language, in order to make a contradiction, since if $L_1$ is context free and $L_2$ is a regular language, then $L_1 \cap L_2$ is also context free.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

$L_1$ is included in $L$: can you find a regular language $R$ so that $L_1=L\cap R$?

Hints:

  • $R$ needs to reject symbols other than $a,b,c$.
  • $R$ needs to enforce the order between appearances of $a$, $b$ and $c$.
share|improve this answer
1  
How about L = {a*b*c*} ? –  ron Jun 13 '12 at 2:36
    
Exactly! (but I called it $R$ since you already defined $L$ to be the language of the original question) Now can you finish the proof? What would happen if $L$ was context-free? –  Generic Human Jun 13 '12 at 2:39
1  
From here it's pretty simple , since L3={a*b*c*} is a regular language and L={w|#a(w)=#b(w)=#c(w)} is a context free language , then L1∩L3` would be also context free . But we know that L4 = {a^i b^i c^i | i>=0} = L1∩L3` is not context free , hence we have a contradiction . –  ron Jun 13 '12 at 2:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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