Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
3  
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.