cyclic language
{{Short description|Set of strings closed w.r.t. cyclic shift, repetition, and root}}
{{More citations needed|date=May 2020}}
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 ⇔ wn ∈ L, and
- ∀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.{{cite book | contribution-url=https://hal.science/hal-00619852 | author=Marie-Pierre Béal and Olivier Carton and Christophe Reutenauer | contribution=Cyclic Languages and Strongly Cyclic Languages | title=Proc. Symposium on Theoretical Aspects of Computer Science | publisher=Springer | series=Lecture Notes in Computer Science | volume=1046 | pages=49–59 | year=1996 }}{{rp|Def.1}}
Examples
For example, using the alphabet A = {a, b }, the language
| ALIGN=RIGHT | L =
| { | | apbn1 | an2bn2 | ... | ankbnk | aq | : | ni ≥ 0 and p+q = n1 } |
| ALIGN=RIGHT | ∪
| { | bp | an1bn1 | an2bn2 | ... | ank bq | | : | ni ≥ 0 and p+q = nk } |
is cyclic, but not regular.{{rp|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.