Ygtjki

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 ($ (there's a whole nice recent book on it: Context-Free Languages and Primitive Words)


• 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?" on cstheory, which perhaps has been solved by domotorp, see his preprint)

Note: 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. $L_Goldbach = 1^2n mid 2n$ cannot be expressed as a sum of two primes$$). I'm not quite interested in such examples.

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

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 $0le a_1le a_2leldots$, 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_nle 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.