# Given a DFA $A$ and a CFG $G$, decide whether $L(G) ⊆ L(A)$

Propose a reasonably efficient algorithm to decide, given a DFA $A$ and a CFG $G$, whether $L(G) ⊆ L(A)$.

I think that I have to prove it by computing the intersection of both (DFA,CFG), and then look if the language generated by the intersection is the same as that generated by the CFG. But I'm not sure if it works.

• What are your thoughts on the subject? – Yuval Filmus Nov 27 '16 at 10:41
• Now i updated it with my thoughts. – Crider7 Nov 27 '16 at 10:49
• I suggest you give it a few more days. Make a list of what is doable for context-free grammars, and see if you can use these building blocks to solve your particular problem. – Yuval Filmus Nov 27 '16 at 10:54
• "I'm not sure if it works" - try it out and then you will know for sure. – Yuval Filmus Nov 28 '16 at 10:03