PrimitiveWordsContextFree < CoWiki

CoWiki Web>ImportantOpenProblems>PrimitiveWordsContextFree (2018-02-22, JeffreyShallit) (raw view)

A finite word _w_ is primitive if it is not a nontrivial power of another word, that is, if _w_ = <em>u<sup>k</sup></em> for _k_ &ge; 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, <em>Context-free languages and primitive words,</em> surveys the problem.

-- Main.JeffreyShallit - 13 Jul 2011

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

CoWiki

CoWiki Web
CoWiki Web Home
Changes
Index
Search

Webs
- AIMAS
- CERAS
- CF
- CoWiki
- CrySP
- External
- Faqtest
- HCI
- Himrod
- ISG
- Main
- Multicore
- Sandbox
- TWiki
- TestNewSandbox
- TestWebS
- UW

My links
- People
- CERAS
- WatForm
- Tetherless lab
- Ubuntu Main.HowTo
- eDocs
- RGG NE notes
- RGG
- CS infrastructure
- Grad images

Edit