Search code examples
context-free-grammarformal-languages

How to prove that L={w|#a(w)=#b(w)=#c(w)} is not context free using closure

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

Thanks

EDIT :

I know that the language L1 = {a^i b^i c^i | i>=0} is not a context free language . Now I'm trying to find another language L2 , where L2 would be a regular language , in order to make a contradiction , since if L1 is context free and L2 is a regular language , then L1∩L2 is also context free .

Solution

  • Well, in order to get from L to L1, you need to impose an ordering on the a's, b's and c's. There's a really simple regular language you can intersect with L to impose this ordering - can you see what it is?

    If you know how to prove that L3 = { w | #0(w) = #1(w) } is non-regular using closure properties, the proof of this one is really similar.