# 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. Aug 14, 2011 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}$) Aug 14, 2011 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? Aug 15, 2011 at 1:26
• I think this is exactly the question. Aug 15, 2011 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. Aug 15, 2011 at 20:30

I am not sure there is any general characterization for equivalence, but the following papers by Hopcroft, and Hunt and Rosenkrantz resp. might be a good start:

• John E. Hopcroft, On the equivalence and containment problems for context-free languages, Theory of Computing Systems 3(2):119-124, doi:10.1007/BF01746517;
• Harry B. Hunt, III and Daniel J. Rosenkrantz, On Equivalence and Containment Problems for Formal Languages, Journal of the ACM 24(3):387--396, 1977, doi:10.1145/322017.322020.

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

Sorry to bring up an old thread. But here's something that might be relevant.

Let pCFL be the class of permutation-closed CFLs. The equality problem for pCFL is decidable.

Given $L$ in $\Sigma = \{ \sigma_1 , \dots , \sigma_n \}$, let $W_L = \{ \langle \#_{a_1}(w) , \dots , \#_{a_n}(w) \rangle \mid w \in L\}$. By Parikh's Theorem, $W_L$ is semilinear whenever $L$ is context-free.

Now, if $L$ is in pCFL, we have that $w \in L$ iff $\langle \#_{a_1}(w) , \dots , \#_{a_n}(w) \rangle \in W_L$. Thus, for $L_1 , L_2$ in pCFL, $L_1 = L_2$ iff $W_{L_1} = W_{L_2}$. But equality of semilinear sets is decidable; see:

This raises a question to which I would like to know the answer: is it decidable whether a given context-free language is permutation-closed?

• This isn't an answer to the original question, but a separate (although related) question. You should ask it as it's own question (with a link back to this question) either here or on CS.SE. Jan 25, 2014 at 0:08
• Yes, please delete this answer, and repost it as a new question (with a link to this one) Jan 25, 2014 at 0:42
• @SureshVenkat it seems the user asks this at the end of this question. So maybe a new question isn't needed. Jan 25, 2014 at 0:46
• @ArtemKaznatcheev yes, but then the defn of $\textbf{pCFL}$ should be inserted in that question as well. Jan 25, 2014 at 0:47