Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений

Подождите немного. Документ загружается.

Глава 11

И вновь о сплетении

Наряду с разновидностями операции сплетения, обсуждавши-

мися в предыдущих главах (в особенности в главе 8), и раз-

личными основанными на сплетении порождающими механиз-

мами, в литературе исследовались и некоторые другие вариан-

ты таких операций и механизмов. Эти исследования касались

главным образом математических аспектов, не затрагивая за-

дачи построения (универсальных) вычислительных моделей. В

настоящей главе мы представим некоторые из таких вариантов

в надежде, что читателя может заинтересовать задачу постро-

ения соответствующих вычислительных моделей.

11.1 Ограниченное сплетение.

Неитеративный случай

В главе 8 мы рассматривали регулируемые варианты операции

сплетения, использующие разрешающие и запрещающие кон-

тексты, языки-мишени, отображения годности и порядки на

множестве правил спл етени я. Мы были вынуждены вводить

ограничения, поскольку иначе с помощью сплетений, действу-

ющих в соответствии с конечным множеством правил, выйти

за рамки регулярных языков невозможно.

Здесь мы введем для операции сплетения, точнее для `,

некие новые ограничения. Возврат к 1-сплетению вызван пре-

жде всего тем, что некоторые из этих вариантов не подходят

для 2-сплетения (|=). С другой стороны, здесь мы в большей

степени интересуемся математическими свойствами объектов,

поэтому предпочитаем находиться в наиболее общей матема-

тической ситуации, и зучая, как и в разделе 7.2, только неите-

ративный случай. Вопрос, приводят ли данные ограничения

462 11. И вновь о сплетении

к регулируемым H-системам, характеризующим семейство ре-

курсивно перечислимых языков, ждет своего исследователя.

Рассмотрим алфавит V и правило сплетения

r = u

над V . Для x, y ∈ V

∗

, мы определяем:

(x, y) `

z ⇐⇒ (x, y) `

z и x ∈ P ref(z), x 6= z,

(x, y) `

z ⇐⇒ (x, y) `

z и |z| > max{|x|, |y|},

(x, y) `

z ⇐⇒ (x, y) `

z и |z| > |z

| для всех z

∈ V

∗

таких, что (x, y) `

В первом случае результат сплетения должен быть нетриви-

альным продолжением первого терма сплетения, во втором —

строкой, строго более длинной, чем каждый из двух исходных

термов, в третьем случае результат должен оказаться одним

из самых длинных среди возможных. Обозначения pr, in, mi

означают «префикс» («preﬁx»), «возрастание» («increasing»),

«максимальное возрастание» («most increasing»).

Эти ограничения введены на уровне самой операции спле-

тения. Кроме того, мы можем определить ограниченные схе-

мы сплетения, где условия формулируются для целого множе-

ства правил или термов сплетения. К первому типу относится,

например, ограничение упорядочения, обсуждавшееся в конце

раздела 8.2. Мы введем здесь класс ограничений второго типа,

разрешающих сплетение только среди сходных строк. Могут

рассматриваться различные степени сходства.

Во всех случаях ниже мы и меем дело с H-схемами с конеч-

ными множествами правил.

H-схема с кластерами — это тройка

σ = (V, R, C),

где (V, R) — схема сплетения, а C — разбиение V

∗

. Для r ∈ R

и x, y, z ∈ V

∗

, мы пишем (x, y) `

z тогда и только тогда,

когда (x, y) `

z и x, y принадлежит одному и тому же классу

разбиения C.

11.1. Ограниченное сплетение 463

Если C — конечное множество регулярных языков, мы пи-

шем `

вместо `

. Если C состоит из одноэлементных клас-

сов, {x}, x ∈ V

∗

, мы пишем `

, а если C состоит из классов

= {x ∈ V

∗

| |x| = i}, i > 0, то мы пишем `

Мы обозначаем через D множество указателей {pr, in, mi,

rc, sf, sl}, для определенных выше вариантов операции спле-

тения. Для схемы сплетения σ с алфавитом V и множеством

правил R, и для L ⊆ V

∗

, g ∈ D, мы определяем

(L) = {z ∈ V

∗

| (x, y) `

z для x, y ∈ L, r ∈ R}.

Поскольку в разделе 7.2 мы уже занимались свободным

сплетением `, мы будем исследовать теперь связи между опе-

рациями `

, g ∈ D, и обычными операциями с языками. Наша

цель — установить свойства замкнутости относительно новых

операций ограниченного сплетения для семейств из иерархии

Хомского.

Лемма 11.1. Если семейство языков FL замкнуто относи-

тельно объединения с одноэлементными языками, приписыва-

ния символов, взятия левой производной, перетасовки симво-

лов и какой-нибудь операции сплетения из D − {in}, то FL

замкнуто относительно операции Suf взятия суффиксов.

Доказательство. Возьмем L ∈ FL, L ⊆ V

∗

, и рассмотрим сим-

волы a, b, не лежащие в V . Для схемы спл етени я

σ = (V ∪ {a, b}, {a#$b#}),

мы имеем

Suf(L) = ∂

(σ

)),

где

= {a} ∪ (L t⊥ {b})

для g ∈ {pr, mi}.

Действительно, единственно возможное сплетение должно

включать строку a и строку xby для xy ∈ L, x, y ∈ V

∗

. Суще-

ствует лишь одно место, где можно применить правило из σ, а

значит, и результат единственен, ay.

Указатель g может равняться и rc, если считать, что раз-

биение из σ состоит из одного кластера (V ∪ {a, b})

∗

464 11. И вновь о сплетении

Для случаев sf, sl мы заменяем L

на L

= {a}L t⊥ {b}.

Сплетая axby с ее же копией единственно возможным спосо-

бом, мы получаем ay. В общем случае для axby и ax

мы

имеем лишь одну возможность сплетени я, при которой полу-

чается ay

. Следовател ьно, мы можем получить все элементы

Suf(L) и только их.

Лемма 11.2. Если семейство языков FL замкнуто относи-

тельно объединения, приписывания символов, слабого кодиро-

вания и какой-нибудь операции сплетения `

, g ∈ D−{sf}, то

FL замкнуто относительно произведения.

Доказательство. Возьмем два языка L

, L

∈ F L, L

, L

⊆

∗

, рассмотрим два символа a, b, не лежащих в V , и схему

сплетения σ = (V ∪ {a, b}, {a#$#b}). Имеем

= h(σ

)),

где h — слабое кодирование, определяемое равенствами h(a) =

h(b) = λ и h(c) = c дл я c ∈ V ,

= L

{a} ∪ {b}L

а g ∈ {pr, in, mi}. Также как и в доказательстве леммы 11.1,

сюда легко включается и случай g = rc.

Для g = sl мы заменяем L

на

= L

{a}

∪ {b}

Начиная со строк xa

, b

y с n = |y| и m = |x|, мы получаем

|xa

| = |b

y| и (xa

n−i

, b

m−j

y) `

y для всех i, j > 1.

Таким образом, L

= h(σ

)).

Лемма 11.3. Если семейство языков FL замкнуто относи-

тельно приписывания символов, слабого кодирования и само-

сплетения, то FL замкнуто относительно дублирования

(операции, приводящей от L к d(L) = {xx | x ∈ L}).

Доказательство. Для L ∈ F L, L ⊆ V

∗

, и a, b /∈ V , рассмотрим

схему сплетени я σ = (V ∪ {a}, {b#$#a}). Мы получим d(L) =



({a}L{b})



при h, задаваемом равенствами h(a) = h(b) =

λ и h(c) = c дл я всех c ∈ V .

11.1. Ограниченное сплетение 465

Единственно возможное сплетение — (axb|, |axb) `

axbaxb, в силу чего и выполняется равенство.

Лемма 11.4. Если семейство языков FL замкнуто относи-

тельно объединения, приписывания символов, взятия правой

и левой производных и префиксного сплетения, то FL замкну-

то относительно пересечения.

Доказательство. Возьмем L

, L

∈ F L, L

, L

⊆ V

∗

, и рас-

смотрим не лежащие в V символы a, b, c. Для схемы сплетения

σ = (V ∪ {a, b, c}, {a#$b#})

имеем L

∩ L

= ∂



∂



)





, где L

= {a}L

{c} ∪

{b}L

{cc}. Действительно, из-за вида правила из σ возможно

только сплетение строки axc со строкой bycc при x ∈ L

y ∈ L

. Поскольку результат обязан продолжать вправо

axc, должно выполняться равенство x = y. Следовательно,

) = {a}(L

∩ L

){cc}.

Лемма 11.5. Если семейство языков FL замкнуто от-

носительно перетасовки, приписывания регулярных языков,

нестирающих ОПМ отображений и ограниченных морфизмов,

то FL замкнуто относительно возрастающих сплетений.

Доказательство. Возьмем язык L ∈ F L, L ⊆ V

∗

, и символ

c /∈ V . Для каждого a ∈ V рассмотрим новые символы a

, a

а также кодирование h

, определенное равенствами h

(a) =

, a ∈ V . Возьмем, кроме того, схему сплетения σ = (V, R). С

каждым правилом r ∈ R свяжем два символа d

, d

. Рассмот-

рим следующие регулярные языки:

= {xu

y | x, y ∈ V

∗

, r = u

∈ R },

= {xu

y | x, y ∈ V

∗

, r = u

∈ R }.

Положим также

= L

∩ (

[

r∈R

(L t⊥ {d

})),

= h

∩ (

[

r∈R

(L t⊥ {d

}))),

466 11. И вновь о сплетении

где h

продолжено согласно равенству h

) = d

. Оба этих

языка лежат в F L, поскольку кодирование h

, так же как и

пересечение с регулярными языками, может быть получено при

помощи нестирающих ОПМ отображений. Рассмотрим теперь

язык

= (L

∗

t⊥ c

∗

) ∩ L

где

= {ac | a ∈ V }

{ab

| a, b ∈ V }

∗

| r ∈ R}{ab

| a, b ∈ V }

∗

{ca

| a ∈ V }

Язык L

также лежит в F L. Пересечение с L

выберет из

∗

t⊥ c

∗

строки вида

c . . . a

k+1

. . . a

k+j

k+j+1

j+1

. . . a

k+j+i

j+i

j+i+1

. . . cb

j+i+l

, (∗)

(k > 1, j > 0, i > 0, l > 1), соответствующие строкам

x = a

. . . a

k+j+i

∈ L, y = b

. . . b

j+i+l

∈ L.

Имеем

(x, y) `

. . . a

k+j

j+1

. . . b

j+i+l

= z.

Длина полученных строк k + j + i + l, что строго больше, чем

|x| и |y|.

Мы можем легко построить ОПМ g, которая способно прой-

ти строку w вида (∗) и выполнить следующие операции:

1) оставить неизмененным префикс a

c . . . a

2) от последнего вхождения символа c в префиксе до d

оста-

вить неизмененными символы a

k+1

, . . . , a

k+j

, а каждый сим-

вол b

, . . . , b

заменить символом c,

3) заменить d

на cc,

4) от d

до следующего вхождения c заменить каждый a

k+j+1

. . . , a

k+j+i

на c, а каждый b

j+1

, . . . , b

j+i

на b

j+1

, . . . , b

j+i

со-

ответственно,

5) в суффиксе cb

j+i+1

. . . cb

j+i+l

заменить штрихованные сим-

волы их нештрихованными вариантами.

11.1. Ограниченное сплетение 467

Таким образом, мы получим строку z, перетасованную с |z| + 2

вхождениями символа c. С помощью ограниченного морфизма

мы можем стереть c, оставив другие символы неизмененны-

ми. Поэтому σ

(L) = h



g(L

)



, откуда σ

(L) ∈ F L.

Лемма 11.6. Если семейство языков FL замкнуто отно-

сительно произведения и произвольных ОПМ отображений,

то FL замкнуто относительно максимально возрастающих

сплетений.

Доказательство. Имеем σ

(L) = g(L{c}L) для ОПМ g, кото-

рое проверяет наличие подстрок u

, u

из правил σ в стро-

ках и з L{c}L, удаляет те части, которые должны быть удале-

ны, и в то же время следит, чтобы u

было взято из самой

правой возможной позиции перед c, а u

— из самой левой

возможной позиции после c, обеспечивая тем самым производ-

ство наибольшей строки. Детальное построение такого ОПМ

мы оставляем читателю.

Лемма 11.7. Если семейство языков замкнуто относитель-

но операции дублирования и произвольных ОПМ-отображе-

ний, то оно замкнуто относительно само-сплетения.

Доказательство. Для L ⊆ V

∗

, c /∈ V , и σ = (V, R) мы имеем

(L) = g



d(L{c})



где g — ОПМ, которое, как в предыдущем доказательстве, мо-

делирует применение правил из R.

Лемма 11.8. Если семейство языков FL замкнуто относи-

тельно перетасовки и произвольных ОПМ отображений, то

FL замкнуто относительно префикс-сплетения.

Доказательство. Возьмем σ = (V, R), L ⊆ V

∗

, L ∈ F L, и ко-

дирование h : V −→ {a

| a ∈ V }, определенное равенствами

h(a) = a

, a ∈ V. Возьмем язык

= L t⊥ h(L)

и построим ОПМ g, выполняющее следующие операции:

1) просмотреть префикс x

∈ V

∗

и оставить его неизмененным,

468 11. И вновь о сплетении

2) выбрать правило r = u

из R, u

, u

∈ V

∗

;

выделить строку u

и оставить ее неизмененной,

3) выделить подстроку h(y

) при y

∈ V

∗

и удалить ее,

4) проверить, что далее след ует строка вида a

. . . a

для a

∈ V , 1 6 i 6 k, таких, что a

. . . a

= u

при

некотором x

∈ V

∗

; при этом проверить, стоит ли a

. . . a

перед a

k+1

. . . a

k+s

, s > 1, такими, что a

. . . a

k+1

. . . a

k+s

= h(u

) для некоторого y

∈ V

∗

. Во время этой

фазы стереть все символы a

, а все a

заменить соо тветству-

ющими a

Конструкция g достаточно прозрачна.

Равенство σ

(L) = g(L

) оч евидн о. Для завершения дока-

зательства остается заметить, что кодирование h можно реа-

лизовать с помощью ОПМ.

Лемма 11.9. Если семейство языков замкнуто относитель-

но объединения, пересечения с регулярными множествами

и свободного сплетения, то оно также замкнуто и отно-

сительно кластерного сплетения при разбиении на конечное

число регулярных множеств.

Доказательство. Рассмотрим схему сплетения σ = (V, R, C) с

разбиением C = {C

, . . . , C

}, C

∈ REG, 1 6 i 6 n, заданным

на множестве V

∗

. Тогда для каждого L ⊆ V

∗

, L ∈ F L, мы

получаем

(L) =

[

i=1

(L ∩ C

Поскольку L ∩ C

∈ F L, имеем σ

(L ∩ C

) ∈ F L для всех i, и

значит, σ

(L) ∈ F L.

Теперь мы готовы установить свойства замыкания относи-

тельно `

, g ∈ D для семейств из иерархии Хомского.

Теорема 11.1. Выполняются свойства замкнутости из таб-

лицы 11.1, где для каждой пары (g, F L), g ∈ D, на пересечении

строки g и столбца F L проставлено наименьшее семейство

F L

(среди рассматриваемых здесь пяти семейств), для ко-

торого σ

(L) ∈ F L

при всех L ∈ F L. (Если F L

= F L, то

11.1. Ограниченное сплетение 469

семейство F L за мкнуто относительно сплетения типа g, и

наоборот, F L 6= FL

указывает на незамкнутость.)

Варианты сплетения REG LIN CF CS RE

pr REG RE RE RE RE

in REG CS CS CS RE

mi REG CF CF RE RE

rc REG CF CF RE RE

sf CS RE RE RE RE

sl LIN RE RE RE RE

Таблица 11.1. Свойства замыкания для семейств иерархии

Хомского.

Доказательство. Положительные ответы на вопрос о замкну-

тости REG возникают: для pr из леммы 11.8, для in из лем-

мы 11.5, для mi из леммы 11.6 и для rc из леммы 11.9.

Для CF они следуют: для mi из леммы 11.6, а для rc — из

леммы 11.9.

Единственный положительный ответ в случае CS, а имен но

замкнутость относительно сплетения, увеличивающего длину,

вытекает из леммы 11.5.

Замкнутость RE относительно всех указанных операций

следует либо из тезиса Черча–Тьюринга, либо из приведенных

нами лемм.

Существование языка L ∈ REG, для которого σ

(L) /∈ CF ,

установлено в лемме 11.3 (к примеру, d({a

| n, m > 1}) =

| n, m > 1} /∈ CF ). С другой стороны, если σ =

(V, R) и L ∈ REG, то σ

(L) ∈ CS. Это можно заметить сле-

дующим образом. Если L ∈ REG, то d(L{c}) является право-

линейным простым матричным языком (см. [66]). Это семей-

ство замкнуто относительно произвольных ОПМ-отображений

и строго включается в CS, следовательно, σ

(L) ∈ CS.

Если язык L ⊆ V

∗

обладает при всех n > 0 свойством

card(V

∩ L) 6 1 (такой язык называется тонким, см. [260]), а

σ — схема сплетения, то σ

(L) = σ

(L). Следовательно, благо-

даря лемме 11.3 мы приходим к заключению, что замкнутость

470 11. И вновь о сплетении

REG относительно sl-сплетения подразумевала бы выполне-

ние d(L) ∈ REG для всех тонких регулярных языков L. Это,

однако, не так: d({a

b | n > 1}) = {a

b | n > 1} /∈ REG,

в то в ремя как язык {a

b | n > 1} тонкий. Тем не менее, ес-

ли L ∈ REG, L ⊆ V

∗

, а σ = (V, R) — схема сплетения, то

(L) ∈ LIN. Действительно, возьмем a, c /∈ V и рассмотр им

язык

= (L{c}L t⊥ {a

| n > 1}) ∩ (V {a})

{cc}(V {a})

Он лежит в LIN, поскольку {a

| n > 1} линеен, L{c}L

регулярен, а LIN замкнуто и относительно перетасовки с ре-

гулярными множествами и относительно пересечения с регу-

лярными множествами. Все строки L

имеют вид

a . . . b

accd

a . . . d

при x = b

. . . b

∈ L, y = d

. . . d

∈ L. С помощью ОПМ

g мы можем теперь имитировать сплетение строк x, y ∈ L,

отобранных в L

, т. е. g(L

) = σ

(L). Следовательно, σ

(L) ∈

LIN .

Существование линейных языков L, для которых σ

(L) /∈

CF при g ∈ {pr, in, sf, sl}, д оказывается следующим образом:

для pr это следует из леммы 11.4 (есть языки L

, L

∈ LIN,

для которых L

∩ L

/∈ CF ), для sf — из леммы 11.3, для

sl — из леммы 11.3, примененной к тонким линейным языкам

аналогично случаю тонких регулярных языков (L = {a

n > 1} является тонким и ли нейн ым, но d(L) /∈ CF ). В случае

in мы рассмотрим новый пример.

Для σ = ({a, b, c}, {b#c$a#c}) и

L = {a

c | n > 1} ∪ {a

| n > 1}

мы получаем

(L) = {a

| 2 6 m < 2n}.

Действительно, возможно лишь сплетение типа

|c, a

) `