3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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 \}$? $\endgroup$ Jul 7, 2018 at 20:03
  • $\begingroup$ 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. $\endgroup$
    – RajS
    Jul 7, 2018 at 20:14

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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) $\endgroup$
    – RajS
    Jul 7, 2018 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.