Bi-catenation and shuffle product of languages |
| |
Authors: | HJ Shyr SS Yu |
| |
Affiliation: | (1) Department of Applied Mathematics, National Chung-Hsing University, Taichung, Taiwan , TW |
| |
Abstract: | 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 andB is the set . A non-empty word which is not a power of any other word is called a primitive word. A language is a prefix code if no word
in this language is a prefix of any other word in this language. This paper is devoted to the investigation of the elementary
properties of bi-catenation and shuffle product of languages. The families of prefix codes, disjunctive languages and languages
consisting of primitive words with respective to these two operations are studied. We characterize languages of which the
bi-catenation or the shuffle product with any non-empty word are prefix codes. We also derive that for any bifix code A, both and , , are disjunctive languages, where Q is the set of all primitive words over an alphabet X with more than one letter and . For the shuffle product case, surprisingly is a regular language, where a is a letter of the alphabet X.
Received: 22 September 1997 / 7 January 1998 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|