For regular expression $E$ and a context free grammar $G$- why deciding if $L(G)\subseteq L(E)?$ is a recursive problem?

Question

I'd love your help with understanding why does the following language is recursive:

Input: a regular expression $E$ and a context free grammar $G$

question: $L(G)\subseteq L(E)?$

I tried to think of an algorithm for showing that this problem is decidable, but I don't manage to find one, or to reduce to a recursive problem.

Thanks a lot!

Answer 1

Fix a DFA for $L(E)$, and consider the set $A$ of assertions of the form

Nonterminal $S$ in $G$ generates at least one string that takes DFA state $s_1$ to $s_2$.

Each production of $G$ induces a rule that proves some assertions in $A$ given other ones, and every true assertion of this form arises from a finite number of applications of such rules (namely, corresponding to a parse tree for the string it speaks of).

Thus, start with the empty subset of $A$, and repeatedly apply the rules corresponding to all productions of $G$ until you reach a fixpoint. (This must happen sooner or later because $A$ is finite). Then check whether $A$ says that the starting symbol can generate a string that takes the DFA from the initial state to a non-accepting one.