3
$\begingroup$

(Note the overline denoting the complement.)

I know that, for every $k \geq 2$, the language $L_k = \overline{\{w^k \mid w \in \Sigma^*\}}$ is context-free. The proof is a simple generalization of the proof of the $k = 2$ case given here.

So I'm wondering if $L = \overline{\{w^k \mid w \in \Sigma^*, k \geq 2\}} = \bigcap_{k \geq 2} L_k$ is context-free?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Words which are not a proper power of a smaller word are called primitive. As far as I know, context-freeness of primitive words is an open problem, which has resisted years of research.

There is a book on the subject, Context-Free Languages And Primitive Words by Dömösi and Ito (2014).

A word is said to be primitive if it cannot be represented as any power of another word. It is a well-known conjecture that the set of all primitive words $Q$ over a non-trivial alphabet is not context-free: this conjecture is still open. In this book, the authors deal with properties of primitive words over a non-primitive alphabet, the language consisting of all primitive words and related languages.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ What about the language of words that are not of the form $w^k$ for $k$ in a given set $K$ ($\min K \geq 2$)? Is it also open whether that's a CFL whenever $|K| > 1$? $\endgroup$
    – zinc_11010
    Commented Oct 16 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.