<p>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:</p>

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

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

CC BY-SA 3.0
2011-08-14T22:49:49.107Z
2011-08-16T14:15:12.610Z
2011-08-16T14:15:12.610Z
Sylvain
<p>Sorry to bring up an old thread.  But here's something that might be relevant.</p>

<p>Let <strong>pCFL</strong> be the class of permutation-closed CFLs.  The equality problem for <strong>pCFL</strong> is decidable.</p>

<p>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.</p>

<p>Now, if $L$ is in <strong>pCFL</strong>, 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 <strong>pCFL</strong>, $L_1 = L_2$ iff $W_{L_1} = W_{L_2}$. But equality of semilinear sets is decidable; see:</p>

<ul>
<li>Huynh 1980 "The complexity of semilinear sets": <a href="http://link.springer.com/chapter/10.1007%2F3-540-10003-2_81#" rel="nofollow">http://link.springer.com/chapter/10.1007%2F3-540-10003-2_81#</a></li>
</ul>

<p>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?</p>

CC BY-SA 3.0
2014-01-25T00:08:10.893Z
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](http://cs.stackexchange.com).
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-25T00:42:50.127Z
Yes, please delete this answer, and repost it as a new question (with a link to this one)
Suresh Venkat
CC BY-SA 3.0
2014-01-25T00:46:10.257Z
@SureshVenkat it seems the user asks this at the end of [this question](http://cstheory.stackexchange.com/q/20715/1037). So maybe a new question isn't needed.
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-25T00:47:43.923Z
@ArtemKaznatcheev yes, but then the defn of $\textbf{pCFL}$ should be inserted in that question as well.
Suresh Venkat
CC BY-SA 3.0
2014-01-24T17:05:10.070Z
2014-01-24T17:05:10.070Z
Shane Steinert-Threlkeld
<p>Following problem is decidable:</p>

<p>Given a context-free grammar $G$, is $L(G) = \varnothing$?</p>

<p>Following problem is undecidable:</p>

<p>Given a context-free grammar $G$, is $L(G) = A^{\ast}$?</p>

<p>Is there a characterization of context-free languages $M$ with decidable equality $L(G) = M$?</p>

CC BY-SA 3.0
2011-08-14T10:51:19.273Z
Crosspost from [math.SE](http://math.stackexchange.com/questions/56764).
sdcvvc
CC BY-SA 3.0
2011-08-14T10:53:14.233Z
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
CC BY-SA 3.0
2011-08-15T01:26:51.100Z
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
CC BY-SA 3.0
2011-08-15T19:28:12.033Z
I think this is exactly the question.
domotorp
CC BY-SA 3.0
2011-08-15T20:30:13.467Z
@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
<computability><fl.formal-languages>
Decidability of equality of CFL's
sdcvvc
# Decidability of equality of CFL's

(Asked by: username_0 on 2011-08-14)

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

**Tags:** computability, fl.formal-languages

> **Comments:**
> **username_0**: Crosspost from [math.SE](http://math.stackexchange.com/questions/56764).  
> **username_0**: 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}$)  
> **username_1**: 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?  
> **username_2**: I think this is exactly the question.  
> **username_0**: @username_1: 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.  

---

## 2 answers

### Answer by username_3 on 2011-08-14. Score: 7 | Accepted answer

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](http://dx.doi.org/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](http://dx.doi.org/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$.


---

### Answer by username_4 on 2014-01-24. Score: -2

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:

* Huynh 1980 "The complexity of semilinear sets": <http://link.springer.com/chapter/10.1007%2F3-540-10003-2_81#>

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?

> **Comments:**
> **username_5**: 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](http://cs.stackexchange.com).  
> **username_6**: Yes, please delete this answer, and repost it as a new question (with a link to this one)  
> **username_5**: @SureshVenkat it seems the user asks this at the end of [this question](http://cstheory.stackexchange.com/q/20715/1037). So maybe a new question isn't needed.  
> **username_6**: @ArtemKaznatcheev yes, but then the defn of $\textbf{pCFL}$ should be inserted in that question as well.  

---

