<p>What you're looking for is an old result of Ginsburg and Spanier actually related to one of the oldest open questions of the field.   See Ginsburg's book <em>The Mathematical Theory of CFLs.</em></p>

<p><strong><em>Defs</em></strong>. A <em>linear</em> set is a set of the form <span class="math-container">$\vec{v} + P^*$</span> where <span class="math-container">$\vec{v} \in \mathbb{N}^k$</span> and <span class="math-container">$P$</span> is a finite set of such vectors (<span class="math-container">$P^*$</span> denotes all linear combinations of the vectors in <span class="math-container">$P$</span>).  A linear set is <em>stratified</em> if :</p>

<ol>
<li><p>All the vectors in <span class="math-container">$P$</span> have at most two nonzero components;</p></li>
<li><p>For all <span class="math-container">$\vec{x}, \vec{y} \in P$</span>, the nonzero positions of <span class="math-container">$\vec{x}$</span> and <span class="math-container">$\vec{y}$</span> are not interleaved (this is related to the fact that <span class="math-container">$a^ib^ic^jd^j$</span> is CFL but not <span class="math-container">$a^ib^jc^id^j$</span>).</p></li>
</ol>

<p><strong><em>Theorem</strong>.</em> Let <span class="math-container">$w_1, \ldots, w_k$</span> be some words.  Any CFL <span class="math-container">$L \subseteq w_1^*\cdots w_k^*$</span> can be written as <span class="math-container">$L = \{w_1^{i_1}\cdots w_k^{i_k} \mid (i_1, \ldots, i_k) \in R\}$</span> where <span class="math-container">$R$</span> is an union of stratified sets.  Somewhat conversely, any language of that form with <span class="math-container">$R$</span> a union of stratified sets  is a CFL.</p>

<p>Naturally, there are languages that are CFL that can be written in the previous way with <span class="math-container">$R$</span> being quite arbitrary—e.g., with <span class="math-container">$w_1=w_2=a$</span> and <span class="math-container">$R = \{(2^i, j)\}.$</span> 
 However, if for instance all <span class="math-container">$w_i$</span>'s are different letters, then <span class="math-container">$R$</span> <em>has</em> to be a union of stratified sets for <span class="math-container">$L$</span> to be a CFL.</p>

<p>As for the open question I mentioned before, the following problem is not known to be decidable:</p>

<ul>
<li><em>Given</em>: A finite union of linear sets</li>
<li><em>Question</em>: Is this set presentable as a finite union of stratified sets?</li>
</ul>

CC BY-SA 4.0
2019-01-20T20:27:03.640Z
Wow. Does any modern monograph/textbook treat this theorem, stratified linear sets, or this open problem? There seems to be quite some "abandoned stuff" in formal language theory. Which is of course natural as the field matures - from what I've read, AFL theory was a mainstream line of research in TCS in the 1970s.
Hermann Gruber
CC BY-SA 4.0
2019-01-14T17:57:13.380Z
2019-01-14T17:57:13.380Z
Michaël Cadilhac
<p>Unless I'm mistaken, a language of the form <span class="math-container">$\{0^a10^b\mid R(a,b)\}$</span> is context-free if and only if <span class="math-container">$R$</span> is a finite union of linear (in)equalities involving integer constants and the variables <span class="math-container">$a$</span> and <span class="math-container">$b$</span> with some modulo conditions, e.g., <span class="math-container">$R(a,b)$</span> if and only if (<span class="math-container">$a&lt;2b+1$</span> and <span class="math-container">$a\equiv 2 \bmod 6$</span>) OR (<span class="math-container">$a-b=2$</span> and <span class="math-container">$a\equiv 2 \bmod 6$</span>) OR (<span class="math-container">$2a-3b&gt;5$</span> and <span class="math-container">$2a+b\equiv 3 \bmod 6$</span>).</p>

<p>Is there some similar characterization known when the language can contain only some fixed, bounded number of non-zero characters?</p>

<p>For example, for which <span class="math-container">$R$</span> is <span class="math-container">$\{0^a10^b10^c\mid R(a,b,c)\}$</span> context-free?</p>

<p>Related: I've discovered that this topic has been studied a lot for primitive words, see <a href="https://www.researchgate.net/profile/Laszlo_Kaszonyi/publication/266435445_Some_new_results_on_the_context-freeness_of_languages_Qab_n/links/59e5ffec0f7e9b0e1ab26501/Some-new-results-on-the-context-freeness-of-languages-Qab-n.pdf" rel="nofollow noreferrer">Kaszonyi-Katsura: Some new results on the context-freeness of languages</a>.</p>

CC BY-SA 4.0
2019-01-13T22:49:16.047Z
A necessary condition is that for each $L = \{0^a10^b10^c\mid R(a,b,c)\} \in CFL$, $\{ \langle a, b, c \rangle \}$, must be a semilinear set: apply closure under inverse homomorphism $0 \to \{s_a,s_b,s_c\}$ where $s_a, s_b, s_c$ are three new symbols, intersect with the regular $\{ s_a^*1s_b^*1s_c^* \}$ and apply Parikh's theorem. And clearly also $\{ \langle a + b, c \rangle\}$, $\{ \langle a + c, b \rangle \}$, $\{ \langle a, b +  c \rangle \}$, $\{ \langle a + b + c\rangle \}$ must be semilinear. The same argument is valid for more "fixed" symbols.
Marzio De Biasi
CC BY-SA 4.0
2019-01-13T23:53:57.337Z
... another condition (probably provable from the same Parikh's theorem) is that $R$ cannot contain cross-serial dependencies $\{ \langle a,b,f(a),f(b)\rangle\}$ (as long as $\{a\},\{f(a)\}, \{b\}, \{f(b)\}$ are not finite)
Marzio De Biasi
CC BY-SA 4.0
2019-01-14T00:08:16.857Z
Are stratified sets what you're asking for? Ginsburg and Spanier have you covered if that's the case—see Ginsburg's book "The Mathematical Theory of CFL" and the chapter on bounded languages.
Michaël Cadilhac
CC BY-SA 4.0
2019-01-14T09:41:20.817Z
@Michael Exactly, Theorem 5.4.2 on page 162! Would you convert your comment to an answer?
domotorp
CC BY-SA 4.0
2019-01-14T10:39:06.960Z
@Michael I've also added this to Wikipedia, I would be grateful if you could check that I didn't make any mistakes: https://en.wikipedia.org/wiki/Parikh%27s_theorem#Strengthening_for_bounded_languages
domotorp
<reference-request><fl.formal-languages><context-free>
For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?
domotorp
# For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

(Asked by: username_0 on 2019-01-13)

Unless I'm mistaken, a language of the form $\{0^a10^b\mid R(a,b)\}$ is context-free if and only if $R$ is a finite union of linear (in)equalities involving integer constants and the variables $a$ and $b$ with some modulo conditions, e.g., $R(a,b)$ if and only if ($a<2b+1$ and $a\equiv 2 \bmod 6$) OR ($a-b=2$ and $a\equiv 2 \bmod 6$) OR ($2a-3b>5$ and $2a+b\equiv 3 \bmod 6$).

Is there some similar characterization known when the language can contain only some fixed, bounded number of non-zero characters?

For example, for which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

Related: I've discovered that this topic has been studied a lot for primitive words, see [Kaszonyi-Katsura: Some new results on the context-freeness of languages](https://www.researchgate.net/profile/Laszlo_Kaszonyi/publication/266435445_Some_new_results_on_the_context-freeness_of_languages_Qab_n/links/59e5ffec0f7e9b0e1ab26501/Some-new-results-on-the-context-freeness-of-languages-Qab-n.pdf).

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

> **Comments:**
> **username_1**: A necessary condition is that for each $L = \{0^a10^b10^c\mid R(a,b,c)\} \in CFL$, $\{ \langle a, b, c \rangle \}$, must be a semilinear set: apply closure under inverse homomorphism $0 \to \{s_a,s_b,s_c\}$ where $s_a, s_b, s_c$ are three new symbols, intersect with the regular $\{ s_a^*1s_b^*1s_c^* \}$ and apply Parikh's theorem. And clearly also $\{ \langle a + b, c \rangle\}$, $\{ \langle a + c, b \rangle \}$, $\{ \langle a, b +  c \rangle \}$, $\{ \langle a + b + c\rangle \}$ must be semilinear. The same argument is valid for more "fixed" symbols.  
> **username_1**: ... another condition (probably provable from the same Parikh's theorem) is that $R$ cannot contain cross-serial dependencies $\{ \langle a,b,f(a),f(b)\rangle\}$ (as long as $\{a\},\{f(a)\}, \{b\}, \{f(b)\}$ are not finite)  
> **username_2**: Are stratified sets what you're asking for? Ginsburg and Spanier have you covered if that's the case—see Ginsburg's book "The Mathematical Theory of CFL" and the chapter on bounded languages.  
> **username_0**: @Michael Exactly, Theorem 5.4.2 on page 162! Would you convert your comment to an answer?  
> **username_0**: @Michael I've also added this to Wikipedia, I would be grateful if you could check that I didn't make any mistakes: https://en.wikipedia.org/wiki/Parikh%27s_theorem#Strengthening_for_bounded_languages  

---

## 1 answers

### Answer by username_2 on 2019-01-14. Score: 6 | Accepted answer

What you're looking for is an old result of Ginsburg and Spanier actually related to one of the oldest open questions of the field. See Ginsburg's book *The Mathematical Theory of CFLs.*

***Defs***. A *linear* set is a set of the form $\vec{v} + P^\*$ where $\vec{v} \in \mathbb{N}^k$ and $P$ is a finite set of such vectors ($P^\*$ denotes all linear combinations of the vectors in $P$). A linear set is *stratified* if :

1. All the vectors in $P$ have at most two nonzero components;
2. For all $\vec{x}, \vec{y} \in P$, the nonzero positions of $\vec{x}$ and $\vec{y}$ are not interleaved (this is related to the fact that $a^ib^ic^jd^j$ is CFL but not $a^ib^jc^id^j$).

***Theorem***. Let $w\_1, \ldots, w\_k$ be some words. Any CFL $L \subseteq w\_1^\*\cdots w\_k^\*$ can be written as $L = \{w\_1^{i\_1}\cdots w\_k^{i\_k} \mid (i\_1, \ldots, i\_k) \in R\}$ where $R$ is an union of stratified sets. Somewhat conversely, any language of that form with $R$ a union of stratified sets is a CFL.

Naturally, there are languages that are CFL that can be written in the previous way with $R$ being quite arbitrary—e.g., with $w\_1=w\_2=a$ and $R = \{(2^i, j)\}.$
However, if for instance all $w\_i$'s are different letters, then $R$ *has* to be a union of stratified sets for $L$ to be a CFL.

As for the open question I mentioned before, the following problem is not known to be decidable:

* *Given*: A finite union of linear sets
* *Question*: Is this set presentable as a finite union of stratified sets?

> **Comments:**
> **username_3**: Wow. Does any modern monograph/textbook treat this theorem, stratified linear sets, or this open problem? There seems to be quite some "abandoned stuff" in formal language theory. Which is of course natural as the field matures - from what I've read, AFL theory was a mainstream line of research in TCS in the 1970s.  

---

