# Difference between regular language and context free language

What is nature of difference of regular language and context free language?

My guess is

RL - CFL = RL
CFL - RL = CFL


Am I correct with this?

• I'm not sure what you're asking. Is it the following? Suppose that $L_1$ is regular and $L_2$ is context-free (or vice versa), what can we say about $L_1 \setminus L_2 = \{ w : w \in L_1 \text{ and } w \notin L_2 \}$? Jul 7 '18 at 20:03
• yess. Isnt $L_1 \setminus L_2$ notation used for left quotient? Just realized its called \setminus in $LATEX$. But earlier, I have came across it as left quotient. I meant set difference only by minus sign.
– anir
Jul 7 '18 at 20:14

No, those are not quite correct.

For any alphabet $$\Sigma$$, the language $$\Sigma^*$$ is regular. The set difference between that and any CFG with the same alphabet is the complement of the CFG, and CFGs are not closed with respect to complement. So your first claim is incorrect.

However, CFGs are closed with repect to intersection with a regular language and regular languages are closed with respect to complement. Thus, your second claim is correct.

• This is great. Can we have some systematic way to deduce what any operations on languages can result in, given that we know whether those family of languages is closed under different operations? (so that I can solve all similar problems)
– anir
Jul 7 '18 at 20:26