Following problem is decidable:

Given a context-free grammar $G$, is $L(G) = \varnothing$?

Following problem is undecidable:

Given a context-free grammar $G$, is $L(G) = A^{\ast}$?

Is there a characterization of context-free languages $M$ with decidable equality $L(G) = M$?

  • 1
    $\begingroup$ The general equivalence problem on CFL's is undecidable, but I guess you want a subset of all CFL's for which the equivalence problem is decidable? $\endgroup$ – sxd Aug 11 '11 at 1:10
  • $\begingroup$ @Dimitri: I'd like a description of the set $X$ of languages such that $M \in X$ iff it is decidable given any CFG $G$ (not neccessarily from $X$) if $L(G) = M$. $\endgroup$ – sdcvvc Aug 11 '11 at 6:29
  • 1
    $\begingroup$ Crossposted to cstheory. $\endgroup$ – sdcvvc Aug 14 '11 at 11:52

Question was answered at cstheory.


Your Answer

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

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