Cyklický jazyk - Cyclic language

v počítačová věda, konkrétněji v teorie formálního jazyka, a cyklický jazyk je sada řetězců, která je uzavřena s ohledem na opakování, kořen a cyklický posun.

Definice

Li A je sada symbolů a A^* je sada všech řetězců vytvořených ze symbolů v A, pak sada řetězců L ⊆ A^* se nazývá a formální jazyk přes abeceda A.Jazyk L je nazýván cyklický -li

∀w∈A^*. ∀n>0. w ∈ L ⇔ wⁿ ∈ L, a
∀proti,w∈A^*. vw ∈ L ⇔ wv ∈ L,

kde wⁿ označuje n-násobné opakování řetězce w, a vw označuje zřetězení strun proti a w.^[1]^:Def.1

Příklady

Například pomocí abecedy A = {A, b }, jazyk

L =	{		A^strb^n₁	A^n₂b^n₂	...	A^n_kb^n_k	A^q	:	n_i ≥ 0 a str+q = n₁ }
∪	{	b^str	A^n₁b^n₁	A^n₂b^n₂	...	A^n_k b^q		:	n_i ≥ 0 a str+q = n_k }

je cyklický, ale ne pravidelný.^[1]^{:Příklad 2}Nicméně, L je bez kontextu, od té doby M = { A^n₁b^n₁ A^n₂b^n₂ ... A^n_k b^n_k : n_i ≥ 0} je a bezkontextové jazyky jsou uzavřeny pod kruhový posun; L se získá jako kruhový posun o M.

Reference

^ ^A ^b Marie-Pierre Béal a Olivier Carton a Christophe Reutenauer (1996). „Cyklické jazyky a silně cyklické jazyky“ (PDF). Proc. Sympózium o teoretických aspektech informatiky. Přednášky z informatiky. 1046. Springer. str. 49–59.

Tento počítačová věda článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[Beal.Carton.Reutenauer.1996-1] A ^b Marie-Pierre Béal a Olivier Carton a Christophe Reutenauer (1996). „Cyklické jazyky a silně cyklické jazyky“ (PDF). Proc. Sympózium o teoretických aspektech informatiky. Přednášky z informatiky. 1046. Springer. str. 49–59.

[1]