Cyclic language


In computer science, more particularly in formal [language theory], a cyclic language is a set of strings that is closed with respect to repetition, root, and cyclic shift.

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 over the alphabet A.
The language L is called cyclic if
  1. ∀w∈''A*. ∀n''>0. w ∈ L ⇔ wn ∈ L, and
  2. ∀v,''w∈A''*. vw ∈ L ⇔ wv ∈ L,
where wn denotes the n-fold repetition of the string w, and vw denotes the concatenation of the strings v and w.

Examples

For example, using the alphabet A =, the language
is cyclic, but not regular.
However, L is context-free, since M = is, and context-free languages are closed under circular shift; L is obtained as circular shift of M.