Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Crosspost from math.SE. –  sdcvvc Aug 14 '11 at 10:51
1  
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
add comment

2 Answers

up vote 7 down vote accepted

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

share|improve this answer
add comment

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?

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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