Sample proof using closure properties

codeBuilder
codeBuilder used Ask the Experts™
on
I know that the intersection of a context free language and a regular language is context free however i cannot understand the below proof.

The below words are quoted from : link (look at the end of the page)

i didn't understand the part  L' = L n a*b*c*  .  How can i say such an equivalence ? Is it correct?


Sample proof using closure properties

Let L={w in {a,b,c}* with equal numbers of a's, b's, and c's}. L is not context-free.

To show this, suppose L were context free. Consider L' = L n a*b*c*. Because context-free languages are closed under intersection with regular languages, L' must be regular. But L' is just anbncn, which we know not to be regular. So we must have been wrong in our assumption that L was regular.
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Awarded 2010
Top Expert 2013

Commented:
i didn't understand the part  L' = L n a*b*c*  .  How can i say such an equivalence ? Is it correct?

They are defining a new language, L' as the intersection of L and a*b*c*. Then they discuss what that would imply. So they aren't stating an equivalence, they are defining a language.
You are over complicating the proof, it is very simple:-

L={w in {a,b,c}* with equal numbers of a's, b's, and c's}

Its a proof by contradiction.  So lets assume L is context free.

Consider the language a* b* c* ,  it is clearly regular

The intersection of L and  a* b* c*    is   L' = a^nb^nc^n
ie the same numer of a's, b's and c's , we know this is not regular.
(The intersection is simply the strings that occur in both languages)

But the intersection of a regular language and a context free language is regular

This is a contradiction. So our initial assumption is wrong,

 ie  L is not context free.
(You will also notice L=L')

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial