Consider the formal problem:

Given a context-free grammar $G$, is the language $L(G)$ empty?

Can we determine if the problem is recursively enumerable, recursive, in NP, or in P? Can the entire procedure be explained?

  • 2
    $\begingroup$ Please ask 1 question and pose it in the title. This makes your question far more useful for those who will come after us. Thanks. $\endgroup$ – reinierpost Dec 10 '17 at 0:33
  • 1
    $\begingroup$ Also, what research have you done? We expect you to do a significant amount of research before asking here, to make sure your question isn't already covered in standard sources -- I suggest checking textbooks and searching online (e.g., Wikipedia). In this case, your question is answered on Wikipedia (en.wikipedia.org/wiki/Context-free_grammar#Decidable_problems) with a reference, and it's covered in standard textbooks. $\endgroup$ – D.W. Dec 10 '17 at 2: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.