6
$\begingroup$

Is the following problem decidable in general:

Given a regular language $R$ and context-free $C$, is every string in $R$ also in $C$? That is, is $L(R)\subseteq L(C)$? What about $L(C)\subseteq L(R)$?

I know that this is decidable if $R$ and $C$ are both regular and undecidable if they are both context free.

2 Answers 2

10

It is a well-known undecidable problem whether a context-free grammar generates all possible strings over the alphabet. Therefore your problem must also be undecidable, because it is easy to write down a regular grammar for all strings.

12

This is a correct answer for $R \subseteq C$ for regular $R$ and context-free $C$. The question also mentions the reverse inclusion $C \subseteq R$.

Somewhat surprisingly, that is decidable. We have $C \subseteq R$ iff $C \cap R^c = \emptyset$. Here $R^c$ is the complement of $R$ is regular, and thus the intersection $C \cap R^c$ is context-free. Emptiness of context-free languages is decidable.