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
    $\begingroup$ Crosspost from math.SE. $\endgroup$ – sdcvvc Aug 14 '11 at 10:51
  • 1
    $\begingroup$ 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}$) $\endgroup$ – sdcvvc Aug 14 '11 at 10:53
  • $\begingroup$ 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? $\endgroup$ – Kaveh Aug 15 '11 at 1:26
  • $\begingroup$ I think this is exactly the question. $\endgroup$ – domotorp Aug 15 '11 at 19:28
  • $\begingroup$ @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. $\endgroup$ – sdcvvc Aug 15 '11 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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Artem Kaznatcheev Jan 25 '14 at 0:08
  • 1
    $\begingroup$ Yes, please delete this answer, and repost it as a new question (with a link to this one) $\endgroup$ – Suresh Venkat Jan 25 '14 at 0:42
  • 1
    $\begingroup$ @SureshVenkat it seems the user asks this at the end of this question. So maybe a new question isn't needed. $\endgroup$ – Artem Kaznatcheev Jan 25 '14 at 0:46
  • 2
    $\begingroup$ @ArtemKaznatcheev yes, but then the defn of $\textbf{pCFL}$ should be inserted in that question as well. $\endgroup$ – Suresh Venkat Jan 25 '14 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.