TWiki> CoWiki Web>ImportantOpenProblems>PrimitiveWordsContextFree (2018-02-22, JeffreyShallit) EditAttach

A finite word *w* is primitive if it is not a nontrivial power of another word, that is, if *w* = *u*^{k} for *k* ≥ 1 implies that *k* = 1.

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

Topic revision: r3 - 2018-02-22 - JeffreyShallit

Copyright © 2008-2023 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback