# Decidability of equality of CFL's

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$?

-
Crosspost from math.SE. – sdcvvc Aug 14 '11 at 10:51
For example, it is decidable when $M$ is finite (easy), when $M = \{a\}^{\ast}$ (by Parikh's theorem) or when $M = \{a^n b^n\}$ (by Parikh and checking intersection with complement of $a^{\ast} b^{\ast}$) – sdcvvc Aug 14 '11 at 10:53
Do you know if the set of CFGs $G$ s.t. being equal to $L(G)$ is decidable, is decidable itself? What kind of characterization are you looking for? Do you want a "simple" list of properties which will cover all cases? – Kaveh Aug 15 '11 at 1:26
I think this is exactly the question. – domotorp Aug 15 '11 at 19:28
@Kaveh: I don't know if that set is decidable, though it seems it isn't. The best answer would either be some "simple" conditions covering all cases, or examples showing the phenomenon is too complex. It's a bit vague, but I think it's answerable. – sdcvvc Aug 15 '11 at 20:30

Hopcroft shows in particular that, if $M$ is regular, then $L(G)=M$ is decidable iff $M$ is bounded, i.e. there exist $n$ words $w_1,w_2,\ldots,w_n$ s.t. $M\subseteq w_1^\ast w_2^\ast\cdots w_n^\ast$.