Top Qs
Timeline
Chat
Perspective
Cyclic language
Set of strings closed w.r.t. cyclic shift, repetition, and root From Wikipedia, the free encyclopedia
Remove ads
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.
This article needs additional citations for verification. (May 2020) |
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.[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.
Remove ads
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads