Theory of Computation: Context Free Languages

Question

Hi, I am having a doubt understanding the result of CFL – Regular:

Here’s my approach:

1. CFL – Regular = CFL INTERSECTION Regular’ = CFL INTERSECTION Regular = CFL
2. Suppose some CFL L1= {a^n b^n | n>=1} and some Regular R1= (a+b)* : 

Now if I do CFL – Reg = {ab,aabb,aaabbb, ….} – { epsilon, a, b, ab, aabb, aaabbb, …..} 

It gives { phi } which is Regular (hence also CFL)
 

So is it better to say CFL – Regular = Regular or CFL – Regular = CFL ? If both are separate options, which one should I go for? Thanks

 

Answer 1

CFL. Because a regular language is also a context free language, as you can make a context free grammar from the D.F.A of the corresponding regular language.

Answer 2

A trivial example is that A∗ is regular, and if L is context-free but not regular then

 L∩A∗=L

is context-free but not regular.

So L ∩A is CFL.

https://cs.stackexchange.com/questions/18642/intersection-of-context-free-with-regular-languages