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
    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?2011-08-11
  • 0
    @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$.2011-08-11
  • 1
    Crossposted to [cstheory](http://cstheory.stackexchange.com/questions/7737/).2011-08-14

1 Answers 1

0

Question was answered at cstheory.