Cyclic language

Uses your system voice; voice and rate in settings.

Snapshot

≈ 1 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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.

Examples

For example, using the alphabet A = {a, b }, the language is cyclic, but not regular. However, L is context-free, since M = { a n 1 b n 1 a n 2 b n 2 ... a n k b n k : n i ≥ 0 } is, and context-free languages are closed under circular shift; L is obtained as circular shift of M.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1240118877 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.