31 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!

| 31 views
+1
one is simple and other is intersection with regular language

+1 vote

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.

by Active (1.7k points)
edited
+1