Bi-catenation and shuffle product of languages (Q1127816)

Let \(X^*\) be a free monoid generated by a finite alphabet \(X\) with more than one letter. Any element of \(X^*\) is called a word and any subset of \(X^*\) is called a language. Let \(X^+= X^*\setminus \{1\}\) where 1 is the empty word. The shuffle product of two words consists of all words obtained by inserting one word into another word sparsely. The shuffle product of two languages is the union of all the shuffle products of two words taken one from each of these two languages. The bi-catenation of two languages \(A\) and \(B\) is the set \(A*B= AB\cup BA\). This paper is devoted to the investigation of the elementary properties of bi-catenation and shuffle product of languages. A word in \(X^+\) is primitive if it is not a power of any other word. \(Q\) is the set of all primitive words over \(X\). A language \(A\subset X^+\) is a prefix (suffix) code if \(A\cap AX^+= \emptyset\) \((A\cap X^+A= \emptyset)\). A bifix code is both a prefix code and also a suffix code. The families of prefix codes, disjunctive languages and languages consisting of primitive words with respect to these two operations are concerned. We characterize languages of which the bi-catenation or the shuffle product with any non-empty word are prefix codes. We also obtained that for any bifix code \(A\), both \(A*Q\) and \(A*Q^{(n)}\), \(n>2\), are disjunctive languages, where \(Q(n)= \{f^n\mid f\in Q\}\). For the shuffle product case surprisingly \(a\diamondsuit Q\) is a regular language, where \(a\) is a letter of the alphabet \(X\).