computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

, more particularly in

formal language theory In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sy ...

, a cyclic language is a set of strings that is closed with respect to repetition, root, and

cyclic shift In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse ope ...

Definition

If ''A'' is a set of symbols, and ''A''^* is the set of all strings built from symbols in ''A'', then a string set ''L'' ⊆ ''A''^* is called a

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of s ...

over the

alphabet An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a s ...

''A''. The language ''L'' is called ''cyclic'' if # ∀''w''∈''A''^*. ∀''n''>0. ''w'' ∈ ''L'' ⇔ ''w''^''n'' ∈ ''L'', and # ∀''v'',''w''∈''A''^*. ''vw'' ∈ ''L'' ⇔ ''wv'' ∈ ''L'', where ''w''^''n'' denotes the ''n''-fold repetition of the string ''w'', and ''vw'' denotes the

concatenation In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatenat ...

of the strings ''v'' and ''w''.

Examples

For example, using the alphabet ''A'' = , the language is cyclic, but not

regular The term regular can mean normal or in accordance with rules. It may refer to: People * Moses Regular (born 1971), America football player Arts, entertainment, and media Music * "Regular" (Badfinger song) * Regular tunings of stringed instrum ...

. However, ''L'' is context-free, since ''M'' = is, and context-free languages are closed under

circular shift In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse op ...

; ''L'' is obtained as circular shift of ''M''.

References

Formal languages {{Comp-sci-stub