The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

What is the difference between **regular intersection **and **intersection?**

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

Thanks!

+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.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.6k
- Others 1.8k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,339 questions

55,765 answers

192,354 comments

90,815 users