Misplaced Pages

Cyclic language

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Set of strings closed w.r.t. cyclic shift, repetition, and root
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Cyclic language" – news · newspapers · books · scholar · JSTOR (May 2020) (Learn how and when to remove this message)

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 ⇔ w ∈ L, and
  2. ∀v,w∈A. vw ∈ L ⇔ wv ∈ L,

where w 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

L = { ab ab ... ab a : ni ≥ 0 and p+q = n1 }
∪ { b ab ab ... a b : ni ≥ 0 and p+q = nk }

is cyclic, but not regular. However, L is context-free, since M = { ab ab ... a b : 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". Proc. Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science. Vol. 1046. Springer. pp. 49–59.


Stub icon

This computer science article is a stub. You can help Misplaced Pages by expanding it.

Categories: