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

∀w∈A^*. ∀n>0. w ∈ L ⇔ wⁿ ∈ L, and
∀v,w∈A^*. vw ∈ L ⇔ wv ∈ L,

where wⁿ denotes the n-fold repetition of the string w, and vw denotes the concatenation of the strings v and w.^[1]^: Def.1

Examples

For example, using the alphabet A = {a, b }, the language

L =	{		a^pb^n₁	a^n₂b^n₂	...	a^n_kb^n_k	a^q	:	n_i ≥ 0 and p+q = n₁ }
∪	{	b^p	a^n₁b^n₁	a^n₂b^n₂	...	a^n_k b^q		:	n_i ≥ 0 and p+q = n_k }

is cyclic, but not regular.^[1]^: Exm.2 However, L is context-free, since M = { a^n₁b^n₁ a^n₂b^n₂ ... a^n_k b^n_k : n_i ≥ 0 } is, and context-free languages are closed under circular shift; L is obtained as circular shift of M.