A word w is primitive if it is not a nontrivial power of another word, that is, if w = uk 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.
-- JeffreyShallit - 13 Jul 2011
Topic revision: r1 - 2011-07-13 - JeffreyShallit
 |
|
Copyright © 2008-2025 by the contributing authors. All material on this collaboration platform is the property of the contributing authors. Ideas, requests, problems regarding TWiki? Send feedback