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

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

7.2. Неитеративное сплетение 291

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

∗

, L ∈ F L рассмотрим новый сим-

вол c /∈ V , и H-схемы

σ = (V ∪ {c}, {#α$c# | α ∈ V ∪ {c}}),

= (V ∪ {c}, {#c$α# | α ∈ V ∪ {c}}).

Имеем

Pref(L) = σ

(L{c}), Suf(L) = σ

({c}L).

Легко заметить, что при использовании правила r = #c$c# мы

получим (x|c, yc|) `

x, а для любого z ∈ P ref(x) − {x}, x ∈ L,

найдется правило вида r = #a$c# из σ, такое, что (xc, yc) `

Аналогично, для σ

и Suf.

Лемма 7.6. Пусть FL — семейство языков, замкнутое отно-

сительно подстановки λ-свободных регулярных языков и про-

извольных ОПМ-отображений. Тогда S

(REG, F L) ⊆ F L.

Доказательство. Из условия следует, что F L замкнуто также

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

гулярными языками (это напрямую вытекает из замкнутости

относительно ОПМ-отображений). Теперь замкнутость относи-

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

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

гулярными языками. Мы используем эти свойства ниже.

Возьмем L ⊆ V

∗

, L ∈ REG, и H-схему σ = (V, R) при R ∈

F L. Рассмотрим регулярную подстановку s : (V ∪ {#, $})

∗

−→

P((V ∪ {#, $})

∗

), определенную следующим образом:

s(a) = {a}, a ∈ V,

s(#) = {#},

s($) = V

∗

{$}V

∗

и построим язык L

= V

∗

s(R)V

∗

. Кроме того, рассмотрим язык

= (L t⊥ {#})$(L t⊥ {#}).

Поскольку L

∈ F L и L

∈ R EG, имеем L

∩ L

∈ F L. Строки

из L

∩ L

имеют вид

w = x

для x

∈ L, y

∈ L, и u

∈ R .

292 7. Системы сплетения

Если g — ОПМ, стирающее подстроку #z

# из строк

вида z

при z

∈ V

∗

, 1 6 i 6 4, то получаем σ

(L) =

g(L

∩ L

), следовательно, σ

(L) ∈ F L.

Лемма 7.7. Пусть FL — семейство языков, замкнутое отно-

сительно приписывания символов. Тогда для всех L

, L

∈ F L

имеем L

∈ S

(F L, F L).

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

, L

⊆ V

∗

, L

∈ F L и c /∈ V .

Для H-схемы

σ = (V ∪ {c}, {#xc$c# | x ∈ L

})

имеем L

= σ

{c}). Действительно, единственно воз-

можное сплетение строк в L

{c} имеет вид

c, yc|) `

для x

∈ L

, x

∈ L

, y ∈ L

где r = #x

c$c#.

Лемма 7.8. Пусть FL — семейство языков, замкнутое

относительно приписывания символов. Тогда для любых

L ∈ F L, L ⊆ V

∗

и c /∈ V имеем {c}L ∈ S

(REG, F L).

Доказательство. Для данных L и c рассмотрим H-схему

σ = (V ∪ {c, c

}, {cx#c

# | x ∈ L}),

где c

— новый доп олн итель ный символ. Очевидно, что она име-

ет тип F L. Тогда

{c}L = σ

({c}V

∗

}),

поскольку возможны лишь сплетения вида (cx|c

, cyc

|) `

при r = cx#c

#, x ∈ L, y ∈ V

∗

Лемма 7.9. Пусть FL — семейство языков, замкнутое от-

носительно приписывания символов и перетасовки c симво-

лами. Тогда для любых L ∈ F L, L ⊆ V

∗

и c /∈ V имеем

{c}P ref(L) ∈ S

(REG, F L).

Доказательство. Для данных L и c возьмем H-схему типа F L

σ = (V ∪ {c, c

}, {cxc

# | x ∈ L t⊥ {#}}),

где c

— новый дополнительный символ. Имеем

{c}P ref(L) = σ

({c}V

∗

{c}),

7.2. Неитеративное сплетение 293

F IN REG LIN CF CS RE

F IN F IN F IN F IN F IN F IN F IN

REG REG REG REG, LIN REG, CF REG, RE REG, RE

LIN LIN, CF LIN, CF RE RE RE RE

CF CF CF RE RE RE RE

CS RE RE RE RE RE RE

RE RE RE RE RE RE RE

Таблица 7.1. Размер семейств S

(F L

, FL

поскольку возможны только сплетения вида (cx

, cyc

|) `

для правил r = cx

#, x

∈ L, y ∈ V

∗

Сведем теперь предыдущие л еммы о семействах языков из

иерархии Хомского в один результат.

Теорема 7.1. Имеют место соотношения из таблицы 7.1, в

которой на пересечении строки, отмеченной F L

, и столбца,

отмеченного F L

, стоит либо семейство S

(F L

, F L

), либо

два семейства F L

, F L

, такие, что F L

⊂ S

(F L

, F L

) ⊂

F L

. Эти семейства F L

, F L

являются наилучшими воз-

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

сти семейств.

Доказательство. Ясно, что σ

(L) ∈ F IN для всех L ∈

F IN, каким бы ни было σ. Вместе с леммой 7.2 это дает

(F IN, F L) = F IN для всех семейств F L.

Лемма 7.3 показывает, что S

(REG, REG) ⊆ REG. Вме-

сте с леммой 7.2 это приводит к равенствам S

(REG, F IN) =

(REG, REG) = REG.

Из леммы 7.4 мы получаем S

(LIN, F IN) − LIN 6= ∅. Из

леммы 7.3 имеем S

(CF, REG) ⊆ CF . Следова тельн о, LIN ⊂

(LIN, F L) ⊆ CF = S

(CF, F L) для F L ∈ {F IN, REG}.

Включения S

(LIN, F L) ⊂ CF, F L ∈ {F IN, REG} явля-

ются собственными. Для того чтобы заметить это, рассмотрим

снова доказательство леммы 7.3. Если L ⊆ V

∗

, L ∈ LIN и

σ = (V, R) есть H-схема REG типа, то σ

(L) = g(L{c}L), где

c /∈ V , а g — ОПМ. Язык L{c}L имеет контекстно-свободный

индекс, меньший или равный 2.

294 7. Системы сплетения

В разделе 3.1 упоминалось о том, что семейство контекст-

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

AFL, значит, оно замкнуто относительно произвольных ОПМ-

отображений. Следовательно, для любого L ∈ S

(LIN, REG)

имеем ind

(L) < ∞. При этом существуют контекстно-

свободные языки бесконечного индекса, откуда следует, что

CF − S

(LIN, REG) 6= ∅.

Из теоремы 3.12 нам известно, что для каждого языка L ∈

RE над алфавитом V существуют символы c

, c

/∈ V и язык

∈ CS, L

⊆ L{c

}{c

}

∗

, такие, что для любого слова w ∈

L найдется такое i > 0, что wc

∈ L

. Возьмем еще один

дополнительный символ c

. Язык L

} все еще попадает в

CS. Для H-схемы

σ = (V ∪ {c

, c

}, {#c

#})

имеем

}) = {w | wc

∈ L

} для некоторого i > 0} = L.

Итак, RE ⊆ S

(CS, F IN). Поскольку S

(RE, RE) ⊆ RE (мож-

но доказать это напрямую или задействовать тезис Черча), по-

лучаем S

(CS, F L) = S

(RE, F L) = RE при всех F L.

Каждый язык L ∈ RE согласно теореме 3.13 может быть

представлен в виде L = L

для L

, L

∈ LIN. По лем-

ме 7.7 каждый язык L

с линейными L

, L

лежит в

(LIN, LIN). Следовательно, S

(LIN, F L) = S

(CF, F L) =

RE для всех F L ∈ {LIN, CF, CS, RE}.

По лемме 7.6 имеем S

(REG, F L) ⊆ F L при F L ∈ {LIN,

CF, RE}. Все эти включения являются собственными. Бо-

лее точно, существуют линейные языки, не лежащие в

(REG, RE). Таков, например, язык L = {a

| n > 1}.

Действительно, предположим, что L = σ

) при некото-

ром L

∈ REG, L

⊆ V

∗

и σ = (V, R). Возьмем для L

конеч-

ный автомат M = (K, V, s

, F, δ). Пусть m = card(K), и рас-

смотрим строку w = a

m+1

из L. Пусть x, y ∈ L

и r ∈ R та-

ковы, что (x, y) `

w, x = x

, y = y

, w = x

при r = u

. Имеем либо x

= a

m+1

z, либо u

7.2. Неитеративное сплетение 295

m+1

для некоторых z, z

∈ {a, b}

∗

. Рассмотрим первый слу-

чай, второй разбирается анал огич но. Итак, x = a

m+1

Проходя через префикс a

m+1

, автомат M использует дважды

некоторое состояние из K. Соответствующий цикл можно по-

вторять, поэтому L

содержит строки вида x

= a

m+1+ti

для t > 0 и произвольного i > 0. Для такой строки x

при i > 1

имеем

, y) `

m+1+ti

= a

m+1+ti

m+1

Полученная строка не лежит в L, противоречие. Это рассуж-

дение не зависит от типа R . (Сравните с леммой 7.8: L /∈

(REG, RE), но {c}L ∈ S

(REG, LIN).)

Согласно лемме 7.8, S

(REG, LIN) − REG 6= ∅ и S

(REG,

CF ) − LIN 6= ∅. Из леммы 7.9 имеем S

(REG, CS) − CS 6=

∅. (Следовательно, S

(REG, CF ) не сравнимо с LIN, и

(REG, CS), S

(REG, RE) не сравнимы с LIN, CF, CS.)

Все утверждения, пред ставленные в таблице, доказаны.

Сделаем несколько полезных замечаний по поводу резуль-

татов из таблицы 7.1:

1. Все семейства S

(F L

, F L

) принадлежат иерархии Хом-

ского, за исключением S

(REG, F L

), при F L

∈ {LIN,

CF, CS, RE}, и S

(LIN, F L

) при F L

∈ {F IN, REG},

занимающих строго промежуточные места среди семейств

иерархии Хомского. Свойства этих шести промежуточн ых

семейств (например, замкнутость относительно операций и

разрешимость) требуют дополнительного изучения.

2. Получена серия новых характеризаций семейства RE, от-

талкивающихся, что удивительно, от «простых» пар (F L

F L

). Особенно интересен случай (LIN, LIN ) в виду то-

го, что реальный язык последовательностей ДНК, по-ви-

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

свободным [44, 312]. Поэтому в соответствии с упомянутым

результатом этот язык не может быть ничем иным как ре-

Примечание переводчика. В [60] найдена характеризация семейства

(LIN, REG), из которой, в частности, следует, что оно совпадает с

(LIN, F IN).

296 7. Системы сплетения

курсивно перечислимым языком, т. е. языком наибольшей

сложности (в иерархии Хомского).

Мы завершим данный раздел рассмотрением возможного

расположения подсемейств из S

(LIN, F IN) в промежутке

между семействами LIN и CF .

Для H-схемы σ = (V, R) с конечным R определим радиус σ:

rad(σ) = max{|x| | x = u

, 1 6 i 6 4,

для некоторых u

∈ R }.

Далее, для p > 1 обозначим через S

(F L, [p]) семейство языков

(L) для L ∈ F L и H-схем σ, радиуса меньшего или равного p.

Заметим, что в доказательстве леммы 7.2 (а также лемм 7.4

и 7.5), как и при доказательстве включения RE ⊆ S

(CS, F IN)

в теореме 7. 1, используются схемы радиуса 1. Следовательно,

для F L ∈ {F IN, REG, CF, CS, RE} мы имеем

(F L, [1]) = S

(F L, [p]), для всех p > 1.

Таким образом, эта иерархия схлопывается. То же самое верно

и для F L = LIN , что вытекает из следующей леммы.

Лемма 7.10. Пусть семейство FL замкнуто относитель-

но λ-свободных ОПМ-отображений.Тогда S

(F L, F IN) ⊆

(F L, [1]).

Доказательство. Возьмем H-схему σ = (V, R) с конечным

R. Предположим, что правила в R пронумерованы, R = {r

. . . , r

}, r

= u

i,1

i,2

i,3

i,4

, 1 6 i 6 s. Легко постро-

ить связанную с R ОПМ g, переводящую каждую строку

w = x

i,1

i,2

в g(w) = x

i,1

i,2

и каждую строку

w = y

i,3

i,4

в g(w) = y

i,3

i,4

для x

, x

, y

∈ V

∗

указанного r

, где c

, c

— новые символы, связанные с r

. Рас-

смотрим теперь H-схему σ

= (V ∪ {c

, c

| 1 6 i 6 s}, {#c

# |

1 6 i 6 s}). Имеем g(L) ∈ F L для любого языка L ⊆ V

∗

L ⊆ F L, и, очев идн о, σ

(L) = σ

(g(L)). Остается завершить

доказательство, заметив, что rad(σ

) = 1.

Теорема 7.2. LIN ⊂ S

(LIN, [p]) = S

(LIN, F IN), p > 1.

7.3. Итеративное сплетение 297

Доказательство. Включения S

(LIN, [p]) ⊆ S

(LIN, [p +1]) ⊆

(LIN, F IN), p > 1, следуют из определений. По лемме 7.10

получаем также S

(LIN, F IN) ⊆ S(LIN, [1]). Включение же

LIN ⊂ S

(LIN, F IN) известно из теоремы 7.1.

7.3 Итеративное сплетение как операция

над языками

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

щают свое действие после однократного выполнения операции

разрезания или сшивки, а действуют повторно.

Для H-схемы σ = (V, R) и языка L ⊆ V

∗

определим

(L) = L,

i+1

(L) = σ

(L) ∪ σ

(σ

(L)), i > 0,

∗

(L) =

[

i>0

(L).

Следовательно, σ

∗

(L) есть замыкание L относительно сплете-

ния, обусловленного σ. Другими словами, L

— наименьший

язык, содержащий L и замкнутый относительно обусловленно-

го σ сплетения, т. е. σ

) ⊆ L

Заметим, что σ

(L) совпадает не с σ

(L), а с L ∪ σ

(L).

Для двух семейств языков F L

, F L

определим

(F L

, F L

) = {σ

∗

(L) | L ∈ F L

и σ = (V, R ) при R ∈ F L

Таким образом, семейства H

(F L

, F L

) соответствуют

семействам S

(F L

, F L

) из предыдущего раздела. Как и

для случая неитеративного сплетения, на H-схемах конечного

радиуса можно строить иерархию, рассматривая семейства

(F L, [p]) языков σ

∗

(L) при L ∈ F L и H-схемах σ радиуса,

меньшего или равного p.

Лемма 7.11. (i) Для любых семейств F L

, F L

из включений F L

⊆ F L

и F L

⊆ F L

следует H

(F L

F L

) ⊆ H

(F L

, F L

(ii) H

(F L, [p]) ⊆ H

(F L, [q]) для всех FL и p 6 q.

Доказательство очевидно в силу определений.

298 7. Системы сплетения

Лемма 7.12. F L ⊆ H

(F L, [1]) для всех семейств FL.

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

∗

, L ∈ F L рас-

смотрим символ c /∈ V и H-схему

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

Ясно, что σ

(L) = L для любого i > 0, следовательно, σ

∗

(L) =

(L) = L.

Лемма 7.13. Пусть F L

, FL

— семейства языков, та-

ких, что F L

и F L

замкнуты относительно перетасовки

символов, а F L

и F L

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

с регулярными языками. Тогда H

(F L

, F L

) ⊆ F L

влечет

(F L

, F L

) ⊆ F L

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

∗

, L ∈ F L

и H-схему

σ = (V, R ) при R ∈ F L

. Для c /∈ V рассмотрим язык

= L t⊥ {c}

и H-схему σ

= (V ∪ {c}, R

) при

= (R t⊥ {cc}) ∩ V

∗

#cV

∗

c#V

∗

Из свойств F L

, F L

получим L

∈ F L

, R

∈ F L

. Кроме того,

(L) = σ

∗

) ∩ V

∗

Действительно, σ

) = σ

) ∪ L

для всех i > 1 (любое

сплетение удаляет символ c из строк языка L

, следовательно,

использовать получаемые строки в качестве термов при следу-

ющем сплетении невозможно). Поэтому, если σ

∗

) ∈ F L

, то

(L) ∈ F L

Следствие 7.1. В условиях леммы 7.13 каждый яз ык L ∈

(F L

, F L

) может быть записан как L = L

∩ V

∗

при L

∈

(F L

, F L

Теперь мы пр едставим два ключевых результата в данной

области, имеющих исключительную важность для ДНК-вы-

числений, основанных на сплетении.

Лемма 7.14 (лемма о сохранении регулярности).

(REG, F IN) ⊆ REG.

7.3. Итеративное сплетение 299

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

∗

— регулярный язык, распо-

знаваемый конечным автоматом M = (K, V , s

, F, δ), а также

H-схему σ = (V, R) с конечным множеством

R ⊆ V

∗

Пусть R = {r

, . . . , r

}, r

= u

i,1

i,2

i,3

i,4

, 1 6 i 6 n,

n > 1. Кроме того, предположим, что u

i,1

i,4

= a

i,1

i,2

. . . a

i,t

при a

i,j

∈ V , 1 6 j 6 t

, t

> 0, 1 6 i 6 n. Для каждого i, 1 6 i 6

n, введем новые состояния q

i,1

, q

i,2

, . . . , q

i,t

, q

i,t

. Обозначим

их множество через K

и рассмотрим конечный автомат

= (K ∪ K

, V, s

, F, δ

где

(s, a) = δ(s, a), при s ∈ K, a ∈ V,

i,j

, a

i,j

) = {q

i,j+1

}, 1 6 j 6 t

, 1 6 i 6 n.

Начав с него, мы построим последовательность конечных

автоматов (с λ-переходами) M

= (K ∪ K

, V, s

, F, δ

), k > 1,

переходя от M

к M

k+1

, k > 0 по след ующим законам.

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

= u

i,1

i,2

i,3

i,4

1 6 i 6 n.

Если s — такое состояние из K ∪ K

, что

1) q

i,1

/∈ δ

(s, λ),

2) существуют s

∈ K ∪ K

и x

, x

∈ V

∗

, такие, что

s ∈ δ

, x

∈ δ

(s, u

i,1

i,2

, x

) ∩ F 6= ∅

(следовательно, x

i,1

i,2

∈ L(M

)), тогда положим

k+1

(s, λ) = {q

i,1

Скажем, что это — начальный переход уровня k + 1.

Кроме того, если состояние s

из K ∪ K

таково, что:

1) s

/∈ δ

i,t

, λ),

2) существуют s

∈ K ∪ K

и y

, y

∈ V

∗

, такие, что

∈ δ

, y

300 7. Системы сплетения

∈ δ

, u

i,3

i,4

, y

) ∩ F 6= ∅

(следовательно, y

i,3

i,4

∈ L(M

)), тогда полагаем

k+1

i,t

, λ) = {s

Мы говорим, что это — заключительный переход уровня k + 1.

Тогда δ

k+1

есть расширение δ

начальными и заключитель-

ными переходами уровня k + 1, в соответствии со всеми пра-

вилами сплетения из R и всеми внутренними состояниями s, s

из K ∪ K

Так как множество состояний фиксировано, указанная про-

цедура завершится не более чем через 2·n·card(K ∪K

) шагов.

Таким образом, найдется такое ц елое m, что M

m+1

= M

Докажем, что L(M

) = σ

∗

(L).

Поскольку σ

∗

(L) является наименьшим языком, содержа-

щим L и замкнутым относительно 1-сплетений, задаваемых σ,

достаточно доказать, что

i) L ⊆ L(M

ii) L(M

) замкнуто относительно 1-сплетений, задаваемых σ,

iii) L(M

) ⊆ σ

∗

(L).

Пункт i) очевиден в силу построения автомата M

Для того чтобы доказать пункт ii), рассмотрим п рави ло

сплетения r

= u

i,1

i,2

i,3

i,4

из R и две строки x, y ∈

L(M

), такие, что x = x

i,1

i,2

, y = y

i,3

i,4

. Существу-

ют два состояния s

, s

∈ K ∪ K

, такие, что

∈ δ

, x

), δ

, u

i,1

i,2

) ∩ F 6= ∅,

∈ δ

, y

i,3

i,4

), δ

, y

) ∩ F 6= ∅.

Из построения M

имеем

i,1

∈ δ

, λ) и s

∈ δ

i,t

, λ).

Отсюда следует x

i,1

i,4

∈ L(M

). (Эту ситуацию иллю-

стрирует рис. 7.3.) Следовательно, σ

(L(M

)) ⊆ L(M

Чтобы доказать, что каждая строка, распознаваемая авто-

матом M

, может быть получена из строк L с помощью итера-