\(d\)-words and \(d\)-languages (Q1127815)

Let \(X\) be a finite alphabet containing more than one letter. Let \(X^*\) be the free monoid generated by \(X\). Any element of \(X^*\) is called a word and we call any subset of \(X^*\) a language. A \(d\)-primitive word \(u\) over \(X\) is a nonoverlapping word in the sense that no prefix of \(u\) is a suffix of it. \(D(1)\) is the set of all \(d\)-primitive words over \(X\) and \(D\) is the set of all positive powers of all words in \(D(1)\). Every language contained in \(D\) will be called a \(d\)-language. This paper studies some algebraic properties of \(d\)-primitive words and \(d\)-languages relative to formal language theory and codes. A word \(u\) is square-free if no two consecutive segments of \(u\) are identical. We show that there are infinitely many cyclic-square-free words over alphabet with three letters and this gives another proof of the fact that there are infinitely many square-free words over three letter alphabet. It is well known that the set \(\{u,v\}\) is a code if and only if \(uv\neq vu\). Up till now there is no characterization for three element code. We obtained a characterization for three element codes in \(D(1)\). In this paper we also prove that every regular component in \(D(1)\) is either a prefix code or a suffix code.