Circular Shift - Applications

Applications

Cyclic codes are a kind of block code with the property that the circular shift of a codeword will always yield another codeword. This motivates the following general definition: For a string s over an alphabet Σ, let shift(s) denote the set of circular shifts of s, and for a set L of strings, let shift(L) denote the set of all circular shifts of strings in L. As already noted, if L is a cyclic code, we have L = shift(L). The operation shift(L) has been studied in formal language theory. For instance, if L is a context-free language, then shift(L) is again context-free. Also, if L is described by a regular expression of length n, there is a regular expression of length O(n³) describing shift(L).