If regular languages are a subset of context-free languages

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

Vivek Vikram Singh vivek14 13 Oct 2014 03:14 pm

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 Anastasio Bruto da Costa antonio 13 Oct 2014 07:53 am

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 Mehta aparajita 14 Oct 2014 07:39 pm

 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.?