Is $L(G) \subseteq L(R)$ decidable?

Question

Is the following problem decidable?

Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \subseteq L(R)$?

It is given that the following problem is undecidable

Given a context-free grammar G, is $ L(G) = \Sigma ^*$ ? $\ (1)$

and this problem decidable

Given a context-free grammar G, is $ L(G) = \emptyset $ ? $\ \ \ (2)$

My thought is this:

$L(G) \subseteq L(R)$ is the same as $ L(G) \cap \overline{L(R)} = \emptyset $. So, since regular languages are closed under complement, and the intersection of a $CFL$ with a $RL$ is a $CFL$, $L(G) \cap \overline{L(R)}$ is a $CFL$. Now, $(2)$ is decidable, so if we can create a context-free grammar for $L(G) \cap \overline{L(R)}$ and give it as input to a decider for $(2)$ we have decided our initial problem.

Is my thought correct? And if yes, how can create such a grammar?

Answer 1

Yes, your thought is correct. The only missing part, as you pointed out, is whether or how we can create a CFL algorithmically for the intersection of a CFL with a RL.

If you take a close look at any proof for the fact that the intersection of a CFL with a RL is a CFL, you will find that the proof is constructive or can be made to be constructive easily, giving that there is an algorithm to construct the CFL for a given PDA. Here "constructive" means the same as "algorithmic". It is just by convention or history, we tend to use the word "constructive" instead of "algorithmic" to describe a proof.

You can check your textbook, or this and this.

Exercise. Is the following problem decidable?

Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \supseteq L(R)$?