# 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?

## 1 Answer

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)$$?

• 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