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. 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.
-- JeffreyShallit - 13 Jul 2011
Topic revision: r2 - 2011-07-19 - 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