If regular languages are a subset of context-free languages then why their intersection gives a context-free language and not regular language?


vivek14's picture

The question is wrongly framed.

Suppose L1= \((a+b)^*\) it is a regular language. L2 = \(a^nb^n\) n>=0 is CFL. Now if you intersect them, you will find ​ ​\(a^nb^n\) which is CFL, but not regular.

Suppose L3 = ​ ​​ Ø and  L4 = \(a^nb^n\) and if u intersect then you will find Ø which is regular ,so CFL too as Reg are subset of CFL.

So intersection language will always be CFL, but not always Regular.

You can not say, it does not give regular but only give CFL.

antonio's picture

Aparajita, I understand your confusion. The subset containment (The set of all Regular languages are contained in the set of all Context-free languages) might make you think that for any language L that is regular, it is somehow smaller that some counterpart L' which is context-free, and therefore their intersection should be regular. But this is not the case. 

For example: L1 = a*b* is regular and L2=anbn is context free. L1 has more strings than L2. L1 contains all the strings that L2 has, but L1 also contains other strings where the number of as and bs are un-equal. Their intersection is therefore L2 which is context free.

The important point to note here is that L1 is also a context free language because we can write a context free grammar for L1. All regular languages are also context free because we can write CFGs for the set of regular languages. And as you may know, there is a well defined method for writing a CFG for a regular language.

aparajita's picture

 Ok! Now I understood :)Thank u.  can you please suggest some site or any study material from where I can study TOC and improve my concepts as well as prepare for GATE.?

Did not found what you are looking for, Ask your doubt or Help by your contribution

Enter your search keyword:

Search form


Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.