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

My guess is


Am I correct with this?

  • $\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 '18 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$
    – 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.

  • 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$
    – anir
    Jul 7 '18 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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