Lenguaje cíclico

En informática , más concretamente en la teoría del lenguaje formal , un lenguaje cíclico es un conjunto de cadenas que es cerrado con respecto a la repetición, la raíz y el desplazamiento cíclico .

Si A es un conjunto de símbolos y A ^* es el conjunto de todas las cadenas construidas a partir de símbolos en A , entonces un conjunto de cadenas L ⊆ A ^* se llama lenguaje formal sobre el alfabeto A . El lenguaje L se llama cíclico si

1. ∀ w ∈ A ^* . ∀ n >0. w ∈ L ⇔ w ⁿ ∈ L , y
2. ∀ v , w ∈ A ^* . vw ∈ L ⇔ wv ∈ L ,

donde w ⁿ denota la repetición n veces de la cadena w , y vw denota la concatenación de las cadenas v y w . ^{[ 1 ] : Def.1}

Por ejemplo, usando el alfabeto A = { a , b }, el lenguaje

es cíclico, pero no regular . ^{[ 1 ] : Exm.2} Sin embargo, L es libre de contexto , ya que M = { a ^{n ₁} b ^{n ₁} a ^{n ₂} b ^{n ₂} ... a ^{n _k} b ^{n _k}  : n _i ≥ 0 } lo es, y los lenguajes libres de contexto son cerrados bajo desplazamiento circular ; L se obtiene como desplazamiento circular de M.