The Gateway to Computer Science Excellence

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,565 answers

195,748 comments

101,702 users