Link to home
Start Free TrialLog in
Avatar of codeBuilder
codeBuilder

asked on

Sample proof using closure properties

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.
Avatar of TommySzalapski
TommySzalapski
Flag of United States of America image

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.
ASKER CERTIFIED SOLUTION
Avatar of GwynforWeb
GwynforWeb
Flag of Canada image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial