3
$\begingroup$

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
    Crossposted to [cstheory](http://cstheory.stackexchange.com/questions/7737/).2011-08-14

1 Answers 1

0

Question was answered at cstheory.