<p>Fix an alphabet <span class="math-container">$\Sigma$</span>.</p>
<p>A language <span class="math-container">$R$</span> is <em>bounded</em> if there exists words <span class="math-container">$w_1, w_2, \cdots, w_k$</span> such that <span class="math-container">$R \subseteq w_1^* w_2^* \cdots w_k^*$</span>.</p>
<p>For a regular language <span class="math-container">$R$</span>, the problem <span class="math-container">$P_R$</span> is decidable iff <span class="math-container">$R$</span> is bounded [1].</p>
<p>[1] J. E. Hopcroft: <em>On the equivalence and containment problems for context-free languages</em>, Mathematical Systems Theory 3 (1969), pp. 119–124, doi <a href="https://doi.org/10.1007/BF01746517" rel="noreferrer">10.1007/BF01746517</a>.</p>

CC BY-SA 4.0
2024-12-22T04:22:27.017Z
Nice. This also confirms Denis' conjecture in the comments that $P_R$ is decidable iff $R$ has polynomial growth, since according to the article by Gawrychowski et al cited in the comments (and also referenced in [this question](https://cstheory.stackexchange.com/questions/54931/characterizing-regular-tree-languages-of-polynomial-growth)), "a context-free language is bounded if and only if it has polynomial growth".
Noam Zeilberger
CC BY-SA 4.0
2024-12-25T14:40:11.327Z
Oh, fun coincidence, I asked my question that you're linking to independently (without having seen your conversation with Denis in the comments). The motivation was that for word languages, there's a reduction from language growth to NFA ambiguity ([which I'm interested in for other reasons](https://cstheory.stackexchange.com/questions/54930/deciding-polynomial-ambiguity-in-input-size-or-height-of-a-tree-automaton-al)) but it doesn't work over trees.
Lê Thành Dũng 'Tito' Nguyễn
CC BY-SA 4.0
2024-12-21T13:34:12.980Z
2024-12-21T13:53:43.790Z
2024-12-21T13:53:43.790Z
Sasha
<p>It is a well-known fact that the following problem is undecidable:</p>
<ul>
<li>Instance: DFA <span class="math-container">$D$</span>, CFG <span class="math-container">$G$</span> over the same alphabet <span class="math-container">$\Sigma$</span></li>
<li>Question: Is <span class="math-container">$L(D) = L(G)$</span>?</li>
</ul>
<p>This question is undecidable even when it is promised that <span class="math-container">$L(D) = \Sigma^\star$</span> when <span class="math-container">$|\Sigma| \ge 2$</span>. However, this question is decidable given the promise that <span class="math-container">$L(D) = \emptyset$</span>.</p>
<p>For each <strong>fixed</strong> regular language <span class="math-container">$R$</span> over a fixed alphabet <span class="math-container">$\Sigma$</span>, does there always exist a proof of the decidability or undecidability of the following (modified) problem <span class="math-container">$P_R$</span>?</p>
<ul>
<li>Instance: CFG <span class="math-container">$G$</span> with alphabet <span class="math-container">$\Sigma$</span></li>
<li>Question: Is <span class="math-container">$L(G) = R$</span>?</li>
</ul>
<p>If so, is there a characterization on which regular languages <span class="math-container">$R$</span> has <span class="math-container">$P_R$</span> being decidable? (Of course, the answer is &quot;yes&quot; if we ask about Turing Machines instead of CFGs due to Rice's theorem.)</p>
<p>Based on comments, if <span class="math-container">$|\Sigma| = 1$</span> or the language of <span class="math-container">$R$</span> is finite, this modified question is decidable. Is it a necessary and sufficient condition for <span class="math-container">$R$</span>'s language to be infinite and <span class="math-container">$|\Sigma| \ge 2$</span>?</p>

CC BY-SA 4.0
2024-12-05T10:18:31.930Z
If $R$ generates a finite language $L(R) = \{w_1,\dots,w_n\}$ then $P_R$ is decidable, since it suffices to test that $w_1,\dots,w_n \in L(G)$ and that $L(G \cap \bar{R}) = \emptyset$.  I wonder if it is enough for $L(R)$ to be infinite for $P_R$ to be undecidable.
Noam Zeilberger
CC BY-SA 4.0
2024-12-05T13:46:07.683Z
You also need at least two letters for undecidability
Denis
CC BY-SA 4.0
2024-12-05T16:15:32.363Z
@Denis You mean that the case $|\Sigma| = 1$ is decidable, right?  (Since context-free = regular when $|\Sigma| = 1$, by Parikh's theorem.) But I don't see how to decide $L(G) = R$ even in the case that $|\Sigma| \ge 2$ but $R$ generates an infinite language of words over a single letter.
Noam Zeilberger
CC BY-SA 4.0
2024-12-06T01:15:49.390Z
@NoamZeilberger I think the existence of a word generated by the grammar and containing some forbidden letter is decidable isn't it ? It looks like a variant of the emptiness problem. Then it boils down to the earlier case.
Denis
CC BY-SA 4.0
2024-12-06T04:25:53.147Z
@Denis But how do you use the existence of such a word to decide language equality? You can decide $L(G) \subseteq L(R)$ for an arbitrary $R$ by testing $L(G \cap \bar R) = \emptyset$, but I don't see how you decide the inclusion $L(R) \subseteq L(G)$ even in the case that $L(R)$ is an infinite language contained in $a*$.
Noam Zeilberger
CC BY-SA 4.0
2024-12-06T10:36:08.027Z
@NoamZeilberger What I meant is that if other letters than $a$ do not appear in $L(G)$ (decidable property), you can rewrite $G$ as a grammar on $\Sigma=\{a\}$, and use Parikh's theorem to conclude on whether $L(G)=R$. But I haven't work out the details I might be missing some difficulty.
Denis
CC BY-SA 4.0
2024-12-06T11:38:01.613Z
The question is asking to decide if $L(G) = R$ for an arbitrary CFG $G$. So I agree that it is decidable in the case that $\Sigma$ is a singleton which forces $G$ to generate a regular language, but otherwise I don't see how to decide it for arbitrary grammars in the $R$ infinite case.
Noam Zeilberger
CC BY-SA 4.0
2024-12-15T20:43:16.777Z
@Denis I thought a bit more about this and now I see your point (sorry I missed it before).  I agree that the problem should be decidable in the case that $R$ is a language over a single letter $R \subseteq a^*$, even if $\Sigma|$ contains more letters, because as you wrote it is possible to decide if $L(G) \cap (\Sigma \setminus a^*) = \emptyset$, and then either reject (if $L(G)$ contains a word not in $a^*$) or else rewrite $G$ to an equivalent grammar over $\{a\}$ and reduce to the $|\Sigma| = 1$ case.
Noam Zeilberger
CC BY-SA 4.0
2024-12-15T20:50:21.550Z
I also realized that there is a simple argument for undecidability in the case that $R$ is cofinite, by reduction from the undecidable problem $P_{\Sigma^*}$. To decide if $L(G) = \Sigma^*$, we would just check if $\bar{R} \subseteq L(G)$ (decidable since $\bar{R}$ finite), and then form the intersection grammar $G' = G \cap R$ and test $L(G') = R$.  So the $P_R$ problem is undecidable for $R$ cofinite (assuming $R$ contains more than one letter).  But I don't see how to prove undecidability in the case that $R$ is neither finite nor cofinite.
Noam Zeilberger
CC BY-SA 4.0
2024-12-16T12:31:24.917Z
Intuitively we need to have the "space" to encode any TM run in the language $R$. For instance if the language $R$ is on alphabet $\{a,b\}$ but there is a bound on the number of $b$'s in words from $R$, I guess it will still be decidable, as it is "almost unary".
Denis
CC BY-SA 4.0
2024-12-16T12:45:43.493Z
If on the contrary $R$ is "large" enough, for instance if for any $u$ there exists $v$ with $uv$ in $R$, (on an alphabet with at least two letters) then it is undecidable.
Denis
CC BY-SA 4.0
2024-12-17T23:21:29.540Z
@Denis yes I agree on both counts.  For undecidability, I think it should be enough that $R$ contains a language of the form $u(x+y)^* v$, where $u,v \in \Sigma^*$ are arbitrary strings and $x\ne y \in \Sigma^n$ are two distinct strings of the same length $n > 0$.  This will be the case if the minimal automaton for $R$ has some state $q$ with two different cycles $q \to^n q$.
Noam Zeilberger
CC BY-SA 4.0
2024-12-18T15:19:03.863Z
@NoamZeilberger I guess the following conjecture is natural then: The problem is undecidable if and only if $R$ has exponential growth. (it corresponds to your property, and is equivalent to just asking $x$ and $y$ to be non-commuting instead of same length)
Denis
CC BY-SA 4.0
2024-12-18T15:42:50.920Z
And indeed the right-to-left direction (exponential growth => undecidability) seems ok, what could be trickier is to show that polynomial growth => decidability. Since polynomial growth regular languages are roughly a union of languages of the form $u_1^*u_2^*\dots u_k^*$, it might be possible to reduce to the unary case with some work.
Denis
CC BY-SA 4.0
2024-12-18T21:24:30.647Z
that's a nice conjecture.  I didn't know this fact about polynomial growth regular languages so I'm recording a couple papers that seem relevant for reference (happy to hear if you have any others): "Characterizing regular languages with polynomial densities" (Szilard, Yu, Zhang, Shallit, 1992, https://doi.org/10.1007/3-540-55808-X_48), "Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time" (Gawrychowski, Krieger, Rampersad, Shallit, 2008, https://doi.org/10.1007/978-3-540-85780-8_27).
Noam Zeilberger
<reference-request><fl.formal-languages><automata-theory><context-free><decidability>
Decidability of CFL Equivalence with Fixed Regular Language
Ryan Dougherty
# Decidability of CFL Equivalence with Fixed Regular Language

(Asked by: username_0 on 2024-12-03)

It is a well-known fact that the following problem is undecidable:

* Instance: DFA $D$, CFG $G$ over the same alphabet $\Sigma$
* Question: Is $L(D) = L(G)$?

This question is undecidable even when it is promised that $L(D) = \Sigma^\star$ when $|\Sigma| \ge 2$. However, this question is decidable given the promise that $L(D) = \emptyset$.

For each **fixed** regular language $R$ over a fixed alphabet $\Sigma$, does there always exist a proof of the decidability or undecidability of the following (modified) problem $P\_R$?

* Instance: CFG $G$ with alphabet $\Sigma$
* Question: Is $L(G) = R$?

If so, is there a characterization on which regular languages $R$ has $P\_R$ being decidable? (Of course, the answer is "yes" if we ask about Turing Machines instead of CFGs due to Rice's theorem.)

Based on comments, if $|\Sigma| = 1$ or the language of $R$ is finite, this modified question is decidable. Is it a necessary and sufficient condition for $R$'s language to be infinite and $|\Sigma| \ge 2$?

**Tags:** reference-request, fl.formal-languages, automata-theory, context-free, decidability

> **Comments:**
> **username_1**: If $R$ generates a finite language $L(R) = \{w_1,\dots,w_n\}$ then $P_R$ is decidable, since it suffices to test that $w_1,\dots,w_n \in L(G)$ and that $L(G \cap \bar{R}) = \emptyset$.  I wonder if it is enough for $L(R)$ to be infinite for $P_R$ to be undecidable.  
> **username_2**: You also need at least two letters for undecidability  
> **username_1**: @username_2 You mean that the case $|\Sigma| = 1$ is decidable, right?  (Since context-free = regular when $|\Sigma| = 1$, by Parikh's theorem.) But I don't see how to decide $L(G) = R$ even in the case that $|\Sigma| \ge 2$ but $R$ generates an infinite language of words over a single letter.  
> **username_2**: @NoamZeilberger I think the existence of a word generated by the grammar and containing some forbidden letter is decidable isn't it ? It looks like a variant of the emptiness problem. Then it boils down to the earlier case.  
> **username_1**: @username_2 But how do you use the existence of such a word to decide language equality? You can decide $L(G) \subseteq L(R)$ for an arbitrary $R$ by testing $L(G \cap \bar R) = \emptyset$, but I don't see how you decide the inclusion $L(R) \subseteq L(G)$ even in the case that $L(R)$ is an infinite language contained in $a*$.  
> **username_2**: @NoamZeilberger What I meant is that if other letters than $a$ do not appear in $L(G)$ (decidable property), you can rewrite $G$ as a grammar on $\Sigma=\{a\}$, and use Parikh's theorem to conclude on whether $L(G)=R$. But I haven't work out the details I might be missing some difficulty.  
> **username_1**: The question is asking to decide if $L(G) = R$ for an arbitrary CFG $G$. So I agree that it is decidable in the case that $\Sigma$ is a singleton which forces $G$ to generate a regular language, but otherwise I don't see how to decide it for arbitrary grammars in the $R$ infinite case.  
> **username_1**: @username_2 I thought a bit more about this and now I see your point (sorry I missed it before).  I agree that the problem should be decidable in the case that $R$ is a language over a single letter $R \subseteq a^*$, even if $\Sigma|$ contains more letters, because as you wrote it is possible to decide if $L(G) \cap (\Sigma \setminus a^*) = \emptyset$, and then either reject (if $L(G)$ contains a word not in $a^*$) or else rewrite $G$ to an equivalent grammar over $\{a\}$ and reduce to the $|\Sigma| = 1$ case.  
> **username_1**: I also realized that there is a simple argument for undecidability in the case that $R$ is cofinite, by reduction from the undecidable problem $P_{\Sigma^*}$. To decide if $L(G) = \Sigma^*$, we would just check if $\bar{R} \subseteq L(G)$ (decidable since $\bar{R}$ finite), and then form the intersection grammar $G' = G \cap R$ and test $L(G') = R$.  So the $P_R$ problem is undecidable for $R$ cofinite (assuming $R$ contains more than one letter).  But I don't see how to prove undecidability in the case that $R$ is neither finite nor cofinite.  
> **username_2**: Intuitively we need to have the "space" to encode any TM run in the language $R$. For instance if the language $R$ is on alphabet $\{a,b\}$ but there is a bound on the number of $b$'s in words from $R$, I guess it will still be decidable, as it is "almost unary".  
> **username_2**: If on the contrary $R$ is "large" enough, for instance if for any $u$ there exists $v$ with $uv$ in $R$, (on an alphabet with at least two letters) then it is undecidable.  
> **username_1**: @username_2 yes I agree on both counts.  For undecidability, I think it should be enough that $R$ contains a language of the form $u(x+y)^* v$, where $u,v \in \Sigma^*$ are arbitrary strings and $x\ne y \in \Sigma^n$ are two distinct strings of the same length $n > 0$.  This will be the case if the minimal automaton for $R$ has some state $q$ with two different cycles $q \to^n q$.  
> **username_2**: @NoamZeilberger I guess the following conjecture is natural then: The problem is undecidable if and only if $R$ has exponential growth. (it corresponds to your property, and is equivalent to just asking $x$ and $y$ to be non-commuting instead of same length)  
> **username_2**: And indeed the right-to-left direction (exponential growth => undecidability) seems ok, what could be trickier is to show that polynomial growth => decidability. Since polynomial growth regular languages are roughly a union of languages of the form $u_1^*u_2^*\dots u_k^*$, it might be possible to reduce to the unary case with some work.  
> **username_1**: that's a nice conjecture.  I didn't know this fact about polynomial growth regular languages so I'm recording a couple papers that seem relevant for reference (happy to hear if you have any others): "Characterizing regular languages with polynomial densities" (Szilard, Yu, Zhang, Shallit, 1992, https://doi.org/10.1007/3-540-55808-X_48), "Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time" (Gawrychowski, Krieger, Rampersad, Shallit, 2008, https://doi.org/10.1007/978-3-540-85780-8_27).  

---

## 1 answers

### Answer by username_3 on 2024-12-21. Score: 9 | Accepted answer

Fix an alphabet $\Sigma$.

A language $R$ is *bounded* if there exists words $w\_1, w\_2, \cdots, w\_k$ such that $R \subseteq w\_1^\* w\_2^\* \cdots w\_k^\*$.

For a regular language $R$, the problem $P\_R$ is decidable iff $R$ is bounded [1].

[1] J. E. Hopcroft: *On the equivalence and containment problems for context-free languages*, Mathematical Systems Theory 3 (1969), pp. 119–124, doi [10.1007/BF01746517](https://doi.org/10.1007/BF01746517).

> **Comments:**
> **username_1**: Nice. This also confirms username_2' conjecture in the comments that $P_R$ is decidable iff $R$ has polynomial growth, since according to the article by Gawrychowski et al cited in the comments (and also referenced in [this question](https://cstheory.stackexchange.com/questions/54931/characterizing-regular-tree-languages-of-polynomial-growth)), "a context-free language is bounded if and only if it has polynomial growth".  
> **username_4**: Oh, fun coincidence, I asked my question that you're linking to independently (without having seen your conversation with username_2 in the comments). The motivation was that for word languages, there's a reduction from language growth to NFA ambiguity ([which I'm interested in for other reasons](https://cstheory.stackexchange.com/questions/54930/deciding-polynomial-ambiguity-in-input-size-or-height-of-a-tree-automaton-al)) but it doesn't work over trees.  

---

