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.
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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.