title: Cyclic language
text: # 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^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 of the strings v and $w.^{:Def.1}$
  
  ## Examples
  
  For example, using the alphabet A = {a, b }, the language
  
  | L = | { | | $a^pb^{n1}$ | $a^{n2}b^{n2}$ | ... | $a^{nk}b^{nk}$ | $a^q$ | : | $n_i$ ≥ 0 and p+q = $n_1$ } |
  | - | - | - | - | - | - | - | - | - | - |
  | ∪ | { | $b^p$ | $a^{n1}b^{n1}$ | $a^{n2}b^{n2}$ | ... | $a^{nk}$ $b^q$ | | : | $n_i$ ≥ 0 and p+q = $n_k$ } |
  
  is cyclic, but not $regular.^{:Exm.2}$ However, L is context-free, since M = { $a^{n1}b^{n1}$ $a^{n2}b^{n2}$ ... $a^{nk}$ $b^{nk}$ : $n_i$ ≥ 0 } is, and context-free languages are closed under circular shift; L is obtained as circular shift of M.
  
  