Cyclic language explained

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 ⇔ wⁿ ∈ L, and
2. ∀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]

Examples

For example, using the alphabet A =, the language

ALIGN=RIGHT	L =
ALIGN=RIGHT	∪

is cyclic, but not regular.^[1] 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.

Notes and References

1. Book: https://hal.science/hal-00619852 . Marie-Pierre Béal and Olivier Carton and Christophe Reutenauer . Cyclic Languages and Strongly Cyclic Languages . . Springer . . 1046 . 49 - 59 . 1996 .