En ciencias de la computación , más particularmente en la teoría del lenguaje formal , un lenguaje cíclico es un conjunto de cadenas que está cerrado con respecto a la repetición, raíz y 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 una , a continuación, un juego de cuerdas L ⊆ A * se llama un lenguaje formal sobre el alfabeto A . El lenguaje L se llama cíclico si
- ∀ w ∈ A * . ∀ n > 0. w ∈ L ⇔ w n ∈ L , y
- ∀ v , w ∈ A * . vw ∈ L ⇔ wv ∈ L ,
donde w n 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
Ejemplos de
Por ejemplo, usando el alfabeto A = { a , b }, el idioma
L = | { | a p b n 1 | a n 2 b n 2 | ... | a n k b n k | una q | : | n i ≥ 0 y p + q = n 1 } | |
∪ | { | b p | a n 1 b n 1 | a n 2 b n 2 | ... | a n k b q | : | n yo ≥ 0 y p + q = n k } |
es cíclico, pero no regular . [1] : Ejemplo 2 Sin embargo, L no tiene contexto , ya que M = { a n 1 b n 1 a n 2 b n 2 ... a n k b n k : n i ≥ 0} es, y contexto -Los idiomas libres se cierran en turnos circulares ; L se obtiene como desplazamiento circular de M .
Referencias
- ↑ a b Marie-Pierre Béal y Olivier Carton y Christophe Reutenauer (1996). "Lenguajes cíclicos y lenguajes fuertemente cíclicos" (PDF) . Proc. Simposio sobre Aspectos Teóricos de la Informática . Apuntes de conferencias en Ciencias de la Computación . 1046 . Saltador. págs. 49–59.