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

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!

-
Are you the same person as Numerator? The type of questions, the way you write, and the format of the questions are the same. – William Aug 5 '12 at 20:50

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.