Циклический язык

В информатике , а точнее в теории формального языка , циклический язык — это набор строк, замкнутый относительно повторения, корня и циклического сдвига .

Определение

Если A — набор символов, а A ^* — это набор всех строк, построенных из символов в A , тогда набор строк L ⊆ A ^* называется языком над алфавитом A. формальным Язык L называется циклическим, если

∀ w ∈ A ^*. ∀ n >0. ш ∈ L ⇔ ш ^н ∈ L и
∀ v , w ∈ A ^*. vw ∈ L ⇔ wv ∈ L ,

где ш ^н обозначает n -кратное повторение строки w , а vw обозначает конкатенацию строк v и w . ^[1]^{: Защита 1}

Примеры

Например, используя алфавит A = { a , b }, язык

Л =	{		а ^пб ^{№ ₁}	а ^{№ ₂}б ^{№ ₂}	...	а ^{n_{и т. д.}}б ^{n_{и т. д.}}	а ^д	:	n _i ≥ 0 и p + q = n ₁ }
∪	{	б ^п	а ^{№ ₁}б ^{№ ₁}	а ^{№ ₂}б ^{№ ₂}	...	а ^{n_{и т. д.}} б ^д		:	n _i ≥ 0 и p + q = n _k }

является циклическим, но не регулярным . ^[1]^{: Пример 2}Однако L является контекстно-свободным , поскольку M = { a ^{№ ₁}б ^{№ ₁} а ^{№ ₂}б ^{№ ₂} ... а ^{n_{и т. д.}} б ^{n_{и т. д.}} : n _i ≥ 0 } есть, а контекстно-свободные языки закрываются при циклическом сдвиге ; L получается как круговой сдвиг M .

Ссылки

^ Перейти обратно: ^а ^б Мари-Пьер Беаль, Оливье Картон и Кристоф Ройтенауэр (1996). «Циклические языки и сильно циклические языки» (PDF) . Учеб. Симпозиум по теоретическим аспектам информатики . Конспекты лекций по информатике . Том. 1046. Спрингер. стр. 49–59.

Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее .

[Beal.Carton.Reutenauer.1996-1] Перейти обратно: ^а ^б Мари-Пьер Беаль, Оливье Картон и Кристоф Ройтенауэр (1996). «Циклические языки и сильно циклические языки» (PDF) . Учеб. Симпозиум по теоретическим аспектам информатики . Конспекты лекций по информатике . Том. 1046. Спрингер. стр. 49–59.

[1]