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.

  • $\begingroup$ What are your thoughts on the subject? $\endgroup$ Nov 27 '16 at 10:41
  • $\begingroup$ Now i updated it with my thoughts. $\endgroup$
    – Crider7
    Nov 27 '16 at 10:49
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 27 '16 at 10:54
  • 1
    $\begingroup$ "I'm not sure if it works" - try it out and then you will know for sure. $\endgroup$ Nov 28 '16 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.