<p>How about the language <span class="math-container">$L_{TP}$</span> of twin primes? I.e., all pairs of natural numbers <span class="math-container">$(p,p')$</span> (represented, say, in unary), such that <span class="math-container">$p,p'$</span> are both prime and <span class="math-container">$p'=p+2$</span>? If twin primes conjecture is true, then <span class="math-container">$L_{TP}$</span> is not context-free; otherwise, it's finite.</p>

<p>Edit: Let me give a quick proof sketch that the twin primes conjecture implies that <span class="math-container">$L_{TP}$</span> is not context-free. Associate to any language <span class="math-container">$L$</span> its <em>length sequence</em> <span class="math-container">$0\le a_1\le a_2\le\ldots$</span>, where the integer <span class="math-container">$\ell$</span> appears in the sequence iff there is a word of length <span class="math-container">$\ell$</span> in <span class="math-container">$L$</span>. It is a consequence of the pumping lemma(s) that for <span class="math-container">$L$</span> that are regular or CFL, the length sequence satisfies the bounded differences property: there is an <span class="math-container">$R&gt;0$</span> such that <span class="math-container">$a_{n+1}-a_n\le R$</span> for all <span class="math-container">$n$</span>. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.</p>

CC BY-SA 4.0
2019-04-05T13:54:41.757Z
Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
Marzio De Biasi
CC BY-SA 4.0
2019-04-05T14:04:22.897Z
If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?
Aryeh
CC BY-SA 4.0
2019-04-05T14:33:58.853Z
I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
Marzio De Biasi
CC BY-SA 4.0
2019-04-05T14:48:42.460Z
If there are infinitely many twin primes, how do you show that $L_{TP}$ is not context-free?
Emil Jeřábek
CC BY-SA 4.0
2019-04-05T15:17:47.290Z
@EmilJeřábek: I also thought about that aspect. But probably if you pick the language $\{ 1^p \mid p, p+2 \text{ are primes}\}$ then you can use the usual equivalence of unary CF with REG (then apply pumping lemma and hit a composite number not in the language)
Marzio De Biasi
CC BY-SA 4.0
2019-04-05T15:21:49.247Z
@EmilJeřábek I edited my answer to include a brief proof sketch.
Aryeh
CC BY-SA 4.0
2019-04-05T15:28:24.907Z
Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
Emil Jeřábek
CC BY-SA 4.0
2019-04-05T17:21:54.350Z
On the contrary, Emil, the "standard" proof that the primes in binary are not context-free easily suffices to prove that every infinite set of primes is not context-free.  So if there are infinitely many twin primes, the result is immediate.
Jeffrey Shallit
CC BY-SA 4.0
2019-04-05T12:26:44.303Z
2019-04-05T15:21:31.350Z
2019-04-05T15:21:31.350Z
Aryeh
<p>Another good one is the complement of the set <span class="math-container">$S$</span> of contiguous subwords (aka "factors") of the Thue-Morse sequence <span class="math-container">${\bf t} = 0110100110010110 \cdots $</span>.  To give some context, <a href="https://dl.acm.org/citation.cfm?id=8012" rel="noreferrer">Jean Berstel proved</a> that the complement of the set <span class="math-container">$T$</span> of <em>prefixes</em> of the Thue-Morse word is context-free (and actually something more general than that).  But the corresponding result for subwords is still open.</p>

CC BY-SA 4.0
2019-04-05T19:00:01.840Z
Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
Marzio De Biasi
CC BY-SA 4.0
2019-04-05T17:25:26.637Z
2019-04-05T17:25:26.637Z
Jeffrey Shallit
<p>I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.</p>

<blockquote>
  <p>Is there a recent survey on the subject or an open problem section from a recent conference ?  </p>
  
  <p>Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.</p>
</blockquote>

<p>The examples I found are:</p>

<ul>
<li>the well known language of <em>Primitive words</em> <span class="math-container">$Q = \{ w \mid w \neq u^i (|u| &gt; 1) \}$</span> (there's a whole nice recent book on it: <a href="https://www.worldscientific.com/worldscibooks/10.1142/7265" rel="nofollow noreferrer">Context-Free Languages and Primitive Words</a>)</li>
<li>the <em>Base-k representations of the co-domain of a polynomial</em> (see question "<a href="https://cstheory.stackexchange.com/q/41863/3247">Base-k representations of the co-domain of a polynomial - is it context-free?</a>" on cstheory, which perhaps has been solved by domotorp, see <a href="https://arxiv.org/abs/1901.03913" rel="nofollow noreferrer">his preprint</a>)</li>
</ul>

<p><strong>Note</strong>: as showed by Aryeh in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. <span class="math-container">$L_{Goldbach} = \{ 1^{2n} \mid 2n$</span>  cannot be expressed as a sum of two primes<span class="math-container">$\}$</span>). I'm not quite interested in such examples.</p>

CC BY-SA 4.0
2019-04-07T16:22:27.373Z
For your second example, I wrote a paper from my answer which is under review (and the first feedback was positive): https://arxiv.org/abs/1901.03913
domotorp
CC BY-SA 4.0
2019-04-07T16:26:33.380Z
There are many variants of the first example that are not known to be context-free, I don't know if you want to include them as separate examples; see Chapter 10 of the linked book (Kászonyi-Katsura Theory).
domotorp
CC BY-SA 4.0
2019-04-07T17:27:14.657Z
@domotorp: I just gave it a look (I'm still reading chapter 2) ... they seem to me more technical attempts to attack the main problem.
Marzio De Biasi
<reference-request><big-list><context-free>
Languages that we cannot (dis)prove to be Context-Free
Marzio De Biasi
# Languages that we cannot (dis)prove to be Context-Free

(Asked by: username_0 on 2019-04-05)

I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.

> Is there a recent survey on the subject or an open problem section from a recent conference ?
>
> Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.

The examples I found are:

* the well known language of *Primitive words* $Q = \{ w \mid w \neq u^i (|u| > 1) \}$ (there's a whole nice recent book on it: [Context-Free Languages and Primitive Words](https://www.worldscientific.com/worldscibooks/10.1142/7265))
* the *Base-k representations of the co-domain of a polynomial* (see question "[Base-k representations of the co-domain of a polynomial - is it context-free?](https://cstheory.stackexchange.com/q/41863/3247)" on cstheory, which perhaps has been solved by username_1, see [his preprint](https://arxiv.org/abs/1901.03913))

**Note**: as showed by username_2 in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. $L\_{Goldbach} = \{ 1^{2n} \mid 2n$ cannot be expressed as a sum of two primes$\}$). I'm not quite interested in such examples.

**Tags:** reference-request, big-list, context-free

> **Comments:**
> **username_1**: For your second example, I wrote a paper from my answer which is under review (and the first feedback was positive): https://arxiv.org/abs/1901.03913  
> **username_1**: There are many variants of the first example that are not known to be context-free, I don't know if you want to include them as separate examples; see Chapter 10 of the linked book (Kászonyi-Katsura Theory).  
> **username_0**: @username_1: I just gave it a look (I'm still reading chapter 2) ... they seem to me more technical attempts to attack the main problem.  

---

## 2 answers

### Answer by username_4 on 2019-04-05. Score: 15

Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence ${\bf t} = 0110100110010110 \cdots $. To give some context, [Jean Berstel proved](https://dl.acm.org/citation.cfm?id=8012) that the complement of the set $T$ of *prefixes* of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding result for subwords is still open.

> **Comments:**
> **username_0**: Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).  

---

### Answer by username_2 on 2019-04-05. Score: 13

How about the language $L\_{TP}$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is true, then $L\_{TP}$ is not context-free; otherwise, it's finite.

Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L\_{TP}$ is not context-free. Associate to any language $L$ its *length sequence* $0\le a\_1\le a\_2\le\ldots$, where the integer $\ell$ appears in the sequence iff there is a word of length $\ell$ in $L$. It is a consequence of the pumping lemma(s) that for $L$ that are regular or CFL, the length sequence satisfies the bounded differences property: there is an $R>0$ such that $a\_{n+1}-a\_n\le R$ for all $n$. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.

> **Comments:**
> **username_0**: Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)  
> **username_2**: If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?  
> **username_0**: I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.  
> **username_3**: If there are infinitely many twin primes, how do you show that $L_{TP}$ is not context-free?  
> **username_0**: @EmilJeřábek: I also thought about that aspect. But probably if you pick the language $\{ 1^p \mid p, p+2 \text{ are primes}\}$ then you can use the usual equivalence of unary CF with REG (then apply pumping lemma and hit a composite number not in the language)  
> **username_2**: @EmilJeřábek I edited my answer to include a brief proof sketch.  
> **username_3**: Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)  
> **username_4**: On the contrary, Emil, the "standard" proof that the primes in binary are not context-free easily suffices to prove that every infinite set of primes is not context-free.  So if there are infinitely many twin primes, the result is immediate.  

---

