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

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?

Given a context-free grammar $$G$$ and a regular expression $$R$$, is $$L(G) \supseteq L(R)$$?
• Thank you for the answer! About the exercise I would say no, it is not decidable. If it were decidable, given the regular expression $(a \cup b)^*$, we would be able to determine if $\Sigma ^* \subseteq L(G) \Leftrightarrow L(G) = \Sigma ^*$ which is undecidable. So we get a contradiction, thus the initial assumption is false. – Da Mike Jun 19 '19 at 21:52