В информатике , в частности в теории формального языка , циклический язык - это набор строк, замкнутых по отношению к повторению, корню и циклическому сдвигу .
Определение
Если представляет собой набор символов, и * есть множество всех строк , построенные из символов в A , то строка множество L ⊆ * называется формальным языком над алфавитом A . Язык L называется циклическим, если
- ∀ w ∈ A * . ∀ п > 0. w ∈ L ⇔ w n ∈ L и
- ∀ v , w ∈ A * . vw ∈ L ⇔ wv ∈ L ,
где w n обозначает n- кратное повторение строки w , а vw обозначает конкатенацию строк v и w . [1] : По умолчанию 1
Примеры
Например, используя алфавит A = { a , b }, язык
L = | { | а п б н 1 | а н 2 б н 2 | ... | а н к б н к | а q | : | n i ≥ 0 и p + q = n 1 } | |
∪ | { | б п | а н 1 б н 1 | а н 2 б н 2 | ... | а н к б д | : | n i ≥ 0 и p + q = n k } |
является циклическим, но не регулярным . [1] : Exm.2. Однако L не зависит от контекста , поскольку M = { a n 1 b n 1 a n 2 b n 2 ... a n k b n k : n i ≥ 0}, а контекст -свободные языки закрываются при круговой смене ; Л получают в виде кругового сдвига М .
Рекомендации
- ^ a b Мари-Пьер Беаль, Оливье Картон и Кристоф Ройтенауэр (1996). «Циклические языки и строго циклические языки» (PDF) . Proc. Симпозиум по теоретическим аспектам информатики . Конспект лекций по информатике . 1046 . Springer. С. 49–59.