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.[1]: Def.1 

Examples

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

L = { apbn1 an2bn2 ... ankbnk aq  : ni ≥ 0 and p+q = n1 }
∪ { bp an1bn1 an2bn2 ... ank bq  : ni ≥ 0 and p+q = nk }

is cyclic, but not regular.[1]: Exm.2  However, L is context-free, since M = { an1bn1 an2bn2 ... ank bnk : ni ≥ 0 } is, and context-free languages are closed under circular shift; L is obtained as circular shift of M.

References
  1. Marie-Pierre Béal and Olivier Carton and Christophe Reutenauer (1996). "Cyclic Languages and Strongly Cyclic Languages" (PDF). Proc. Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science. Vol. 1046. Springer. pp. 49–59.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.