Decidability of equality of CFL's

491 Views Asked by At

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

There are 1 best solutions below

0
On BEST ANSWER

Question was answered at cstheory.