Is the set of all primitive words over {0,1} a context-free language? Almost certainly the answer is no, but no one knows how to prove this currently. It seems likely that new techniques for proving languages non-context-free are needed, since the usual methods (pumping lemma, Ogden's lemma, interchange lemma) do not work for this language.

A recent book by Dömösi and Ito, Context-free languages and primitive words, surveys the problem.

-- JeffreyShallit - 13 Jul 2011