Język cykliczny

W informatyce , a dokładniej w teorii języka formalnego , język cykliczny to zbiór łańcuchów, który jest zamknięty pod względem powtórzeń, pierwiastków i przesunięć cyklicznych .

Definicja

Jeśli A jest zbiorem symboli, a A ^* jest zbiorem wszystkich ciągów zbudowanych z symboli w A , to zbiór ciągów L ⊆ A ^* nazywany jest językiem formalnym nad alfabetem A . Język L nazywa się cyklicznym , jeśli

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

gdzie w ⁿ oznacza n -krotne powtórzenie łańcucha w , a vw oznacza konkatenację łańcuchów v i w .

Przykłady

Na przykład używając alfabetu A = { a , b }, język

L =	{		a p b n 1	za n 2 b n 2	...	a n k b n k	q _	:	n ja ≥ 0 i p + q = n 1 }
∪	{	b str	za n 1 b n 1	za n 2 b n 2	...	a n k b q		:	n ja ≥ 0 i p + q = n k }

jest cykliczny, ale nie regularny . Jednak L jest bezkontekstowe , ponieważ M = { a ^{n ₁} b ^{n ₁} a ^{n ₂} b ^{n ₂} ... a ^{n _k} b ^{n _k} : n _i ≥ 0 } jest, a języki bezkontekstowe są zamknięte w kółku zmiana ; L otrzymuje się jako przesunięcie kołowe M .