Lenguaje cíclico

Conjunto de cadenas cerradas respecto del desplazamiento cíclico, la repetición y la raíz

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

Definición

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 denomina lenguaje formal sobre el alfabeto A. El lenguaje L se denomina 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 -vez de la cadena w , y vw denota la concatenación de las cadenas v y w . ^{[1] : Def.1}

Ejemplos

Por ejemplo, utilizando el alfabeto A = { a , b }, el idioma

es cíclico, pero no regular . ^{[1] : Ej. 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 } es, y los lenguajes libres de contexto están cerrados bajo un desplazamiento circular ; L se obtiene como un desplazamiento circular de M .

Referencias

1. Marie-Pierre Béal y Olivier Carton y Christophe Reutenauer (1996). "Lenguajes cíclicos y lenguajes fuertemente cíclicos". Actas del Simposio sobre aspectos teóricos de la informática . Apuntes de clase en informática . Vol. 1046. Springer. págs. 49–59.