The Gateway to Computer Science Excellence
0 votes
26 views

What is the difference between regular intersection and intersection?

(I found out that CFL is closed under regular intersection but not under intersection)

Thanks!

in Theory of Computation by (99 points) | 26 views
+1
one is simple and other is intersection with regular language

1 Answer

+1 vote
Best answer

Regular intersection means the intersection of a language "A" with another language "B" which is regular. When we just say intersection it means that both languages under discussion are of same type. When you say a language is closed under an operation it means that after applying the operation, the resultant language will also be of same type.
Now coming to CFL's, yes they are NOT closed under intersection with other CFL's here's the proof:
A= {a^nb^mc^m | n,m>=1}   B= {a^mb^mc^n | n,m>=1}
the result of A intersection B will be {a^nb^nc^n | n>=1} which is definately not regular.
Thus CFLs are not closed under intersection.
And yes the intersection of any language with a regular language will always be of the same type because the intersection operation requires the elements to be present in the particular language, thus the resultant set will either be finite or it will be of the same type.
I'll explain this with an example, let A={a*b*} and B= {a^n b^n | n>=1} now what will be A intersection B? 
It will be "B" only. Now here you can see A is actually a superset of the language B. Now you can understand that the intersection of any language "B" with a regular language "A" will either be regular or it will be "B" itself. Thus in worst case the resultant language will be of the same type as the language "B". It cannot go beyond that ! 
Please note that the above example shall not be considered as the formal proof. You can find the formal proof in Ullman.  
PS: if you found the answer to be helpful, please upvote it!

by Active (1.7k points)
edited by
+1

@Abhipsa Mishra please recheck the answer, I've updated it. Please read it carefully ! 

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,565 answers
195,748 comments
101,702 users