Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений
Подождите немного. Документ загружается.
9.1. Варианты операции сплетения 401
6
-
?
-
?
6
v
v
1
u
1
u
2
v
2
u
3
u
4
v
3
=⇒
|=
4
v
1
u
1
u
4
v
3
w
u
2
v
2
u
3
@
@R
v
v
1
u
3
u
4
v
2
ˆx
x
1
u
1
u
2
=⇒
|=
3
w
v
1
u
3
u
4
v
2
x
1
u
1
u
2
'
&
$
%
?
66
?
x
1
ˆx
u
1
u
2
x
2
u
3
u
4
=⇒
|=
2
'
&
$
%
'
&
$
%
x
1
ˆy
u
1
u
2
ˆz
x
2
u
3
u
4
'
&
$
%
'
&
$
%
-
-
ˆx
ˆy
x
1
u
1
u
2
u
3
u
4
y
1
=⇒
|=
1
'
&
$
%
x
1
ˆz
u
1
u
4
y
1
u
2
u
3
H
H
H
H
H
H
H
H
Рис. 9.1. Сплетение циклических строк (I).
Заметим, что во всех случаях, так же как и в предыдущих
главах, используется только одно правило сплетения: мы дела-
ем разрез в сайтах u
1
u
2
, u
3
u
4
, а затем рекомбинируем лип кие
концы так, чтобы получить подстроки u
1
u
4
, u
3
u
2
.
Для алфавита V , подмножество L в V
∗
∪ V
называется
смешанным языком. Для обычной H-схемы σ = (V, R) с R ⊆
V
∗
#V
∗
$V
∗
#V
∗
и смешанного языка L ⊆ V
∗
∪ V
определим
смешанный язык σ
∗
mix
(L) как наименьший смешанный язык,
содержащий L и замкнутый относительно всех четыр ех опре-
402 9. Сплетение циклических строк
деленных выше операций |=
i
, i = 1, 2, 3, 4,. При использовании
только некоторых из операций мы будем писать σ
∗
M
(L), где
M ⊆ {1, 2, 3, 4} — множество индексов i, участвующих в рабо-
те операций |=
i
.
Рассмотрим несколько примеров.
σ = ({a, b}, {a#b$b#a}),
L = {Cir(ab)}.
Нетрудно увидеть, что
σ
∗
{1}
(L) = {Cir(a
n
b
n
) | n > 1},
σ
∗
{1,2}
(L) = {ˆy | y = a
n
, или y = b
n
, или y = a
n
b
n
, n > 1},
σ
∗
{1}
(L) = σ
∗
M
(L) для всех M = {1} ∪ M
0
, M
0
⊆ {3, 4},
σ
∗
{1,2}
(L) = σ
∗
M
(L) для всех M = {1, 2} ∪ M
0
, M
0
⊆ {3, 4}.
Для той же H-схемы и L
0
= {ba, Cir(ba)}, получаем
σ
∗
{3}
(L
0
) = {Cir(ba)} ∪ {b
n
a
n
| n > 1}.
Следовательно, во всех этих случаях конечные H-схемы при-
водят конечные языки к нерегулярным (обычным или цикли-
ческим) языкам. Это не так в случае линейных строк (лем-
ма 7.14), что делает сплетение циклических строк интересным
с точки зрения ДНК-вычислений: неогр ани ченн ое сплетение в
соответствии с конечным множеством правил, даже начинаю-
щееся с конечных языков, приводит к нерегулярным языкам.
В случае смешанного сплетения результат о сохранении ре-
гулярности можно получить для дл я особого класса H-схем.
Более точно, H-схема σ = (V, R) называется рефлексивной, ес-
ли вместе с u
1
#u
2
$u
3
#u
4
∈ R всегда u
1
#u
2
$u
1
#u
2
∈ R и
u
3
#u
4
$u
3
#u
4
∈ R .
Доказательство следующего аналога леммы 7.15 можно
найти в [139].
Теорема 9.1. Пусть FL является полным AFL, замкну-
тым относительно циклической перестановки. Тогда, если
σ = (V, R) — рефлексивная H-схема с конечным множеством
9.2. Еще один вариант 403
R, а L — такой смешанный язык над V, что L ∩ V
∗
∈ F L и
L ∩ V
∈ F L
, то σ
∗
mix
(L) ∩ V
∗
∈ F L и σ
∗
mix
(L) ∩ V
∈ F L
.
Таким образом, чтобы получать более сильные, нежели ко-
нечные автоматы, модели вычислимости, основанные на нере-
гулируемом смешанном сплетении, мы д олжн ы использовать
нерефлексивные H-схемы.
Если в приведенном выше примере мы к σ добавим правила
a#b$a#b и b#a$b#a, то получим H-схему σ
0
, такую, что
σ
0
∗
{1}
(L) = {ˆy | y ∈ {a, b}
+
, |y|
a
= |y|
b
},
σ
0
∗
{1,2}
(L) = {ˆy | y ∈ {a, b}
+
}.
Используя только отношение |=
1
, мы все еще получаем
нерегулярный циклический язык, но в другом случае, благо-
даря равенству σ
0
∗
{1,2}
(L) = σ
0
∗
mix
(L) (σ
0
не содержит ни одной
линейной строки) применима теорема 9.1, согласно которой
циклический язык σ
0
∗
{1,2}
(L) регулярен.
Точное описание возможностей основанных на сплетении
циклических строк (расширенных) H-систем различных рас-
сматривавшихся выше типов или (расширенных) H-систем,
основанных на смешанном сплетении — важная тема для
исследования.
9.2 Еще один вариант и его возможности
Идея еще одной операции сплетения циклических строк п ро-
диктована двумя соображениями.
Первое из низ идет от идеи переброски и имитации, кото-
рая используется при доказательстве некоторых характериза-
ций RE в предыдущих главах. На этапах переброски мы на-
чинаем со строк XwαY при w ∈ V
∗
, α ∈ V для данного ал-
фавита V и двух специальных символов X, Y . Мы удаляем α
с правого конца, получая XwY
0
(обычно, Y
0
= Y
α
для запо-
минания удаляемого символа), затем мы добавляем α с левого
конца, создавая XαwY
0
; наконец, мы возвращаем Y вместо Y
0
,
производя XαwY . Поскольку Cir(wα) = Cir(αw), мы можем
считать, что не α перебрасывается в Cir(XwαY ), а блок Y X
404 9. Сплетение циклических строк
переставляется с α при помощи перестановки вида
αY X → Y Xα.
Таким образом, можно одинаково относиться и к имитируемым
нами правилам грамматики u → v, и к перебрасывающим ша-
гам: и в тех и в других некая подстрока циклической строки
заменяется на другую. Для сохранения контролирующего бло-
ка Y X, возможно, в качестве единого символа, нам понадобят-
ся переставляющие правила αY X → Y Xα. Но на самом деле
умение заменять одни подстроки циклической строки др угими
позволяет вообще отказаться от переброски. Правда, нам по-
требуется дополнительный шаг линеаризации или соглашение
о «линейном» прочтении циклических строк.
Другая мотивировка для рассмотрения операции сплете-
ния, способной производить подстановку в циклических стро-
ках, скрыта в характеризации семейства RE с помощью итери-
рованных ОПМ. Итерация ОПМ нужна для того, чтобы после
разбора строки перейти от последнего символа к первому и
снова запустить данный проц есс. В циклическом же случае на-
чало и конец строки соединены, так что можно считать, что
ОПМ просто продолжает разбор, двигаясь вдоль ц ик лич еской
строки.
Операцию замены подстрок в циклической строке, которая
требуется в приведенных ситуациях, можно определить следу-
ющим образом. Для правила сплетен ия r = u
1
#u
2
$u
3
#u
4
над
некоторым алфавитом V и ˆx, ˆy ∈ V
, z, w ∈ V
∗
, пишем
(ˆx, z) |=
5
r
(ˆy, w)
тогда и только тогда, когда
x = x
1
u
1
u
2
x
2
u
3
u
4
, z = u
2
z
1
u
3
,
y = x
1
u
1
u
2
z
1
u
3
u
4
, w = u
2
x
2
u
3
при некоторых x
1
, x
2
, z
1
∈ V
∗
.
Эту операцию иллюстрирует рис. 9.2. Видно, как строки ˆx и
z меняются подстроками x
2
и z
1
. Циклическая строка разреза-
ется в двух местах, при этом из нее высвобождается подслово
u
2
x
2
u
3
. Концы линейной строки соответствуют концам о став-
9.2. Еще один вариант 405
'
&
$
%
'
&
$
%
z
u
2
z
1
u
3
u
2
x
2
u
3
w
=⇒
|=
5
ˆx
u
1
u
2
x
2
u
3
u
4
x
1
x
1
ˆy
u
2
u
1
z
1
u
3
u
4
Z
Z
Рис. 9.2. Сплетение циклических строк (II).
шейся части цик ли ческой строки, поэтому можно произвести
новую циклическую строку.
Взяв эту операцию за основу, определим порождающий
языки механизм.
Расширенная циклическая H-система — это структура
γ = (V, T, A
1
, A
2
, R
1
, R
2
),
в которой V — алфавит, T ⊆ V (терминальный алфавит),
A
1
⊆ V
, A
2
⊆ V
∗
— конечные множества (аксиом), а R
1
, R
2
—
конечные множества правил сплетения над V .
Для такой системы и L
1
⊆ V
, L
2
⊆ V
∗
мы определяем
σ
{5}
(L
1
, L
2
) = (L
0
1
, L
0
2
)
где
L
0
1
= {ˆy | (ˆx, z) |=
5
r
(ˆy, w)
при некоторых ˆx ∈ L
1
, z ∈ L
2
, r ∈ R
1
},
L
0
2
= {w | (ˆx, z) |=
5
r
(ˆy, w)
при некоторых ˆx ∈ L
1
, z ∈ L
2
, r ∈ R
1
}.
Далее,
σ
0
{5}
(L
1
, L
2
) = (L
1
, L
2
),
σ
i+1
{5}
(L
1
, L
2
) = σ
i
{5}
(L
1
, L
2
) ∪ σ
{5}
(σ
i
{5}
(L
1
, L
2
)), i > 0,
σ
∗
{5}
(L
1
, L
2
) =
[
i>0
σ
i
{5}
(L
1
, L
2
),
406 9. Сплетение циклических строк
где объединение производится покомпонентно. Для правила
r = u
1
#u
2
$u
3
#u
4
из R
2
и ˆx ∈ V
, y, z ∈ V
∗
, мы пишем
ˆx |=
6
r
(y, z)
тогда и только тогда, когда
x = x
1
u
1
u
2
x
2
u
3
u
4
, y = u
4
x
1
u
1
, z = u
2
x
2
u
3
при некоторых x
1
, x
2
∈ V
∗
. (Циклическая строка разрезается
на участках u
1
u
2
, u
3
u
4
и возникают две линейные строки.)
Затем для L ⊆ V
мы определяем
σ
{6}
(L) = {y ∈ V
∗
| ˆx |=
6
r
(y, z) или ˆx |=
6
r
(z, y),
при некоторых ˆx ∈ L и r ∈ R
2
}.
Язык, порождаемый γ, задается равенством
L(γ) = σ
{6}
(L
1
) ∩ T
∗
,
где σ
∗
{5}
(A
1
, A
2
) = (L
1
, L
2
) при некотором L
2
⊆ V
∗
.
Таким образом, начав с двух множеств аксиом, мы итера-
тивно сп летаем циклические строки с линейн ыми с помощью
операции |=
5
по правилам из R
1
. После этого полученные цик-
лические строки разрезаются с помощью операции |=
6
по п ра-
вилам из R
2
. В порождаемом языке содержатся только строки,
составленные из терминальных символов.
Мы не знаем, насколько мощными являются расширенные
циклические H-системы. Но простое ограничение операций
сплетения |=
5
, |=
6
приводит по модулю некоторой проек-
ции к характеризации RE. Эта проекция стирает служебные
маркеры, используемые в процессе порождения строки.
Скажем, что γ = (V, T, A
1
, A
2
, R
1
, R
2
) — ограниченная рас-
ширенная циклическая H-система, если с правилами r ∈ R
1
∪R
2
ассоциированы строки v
r
∈ V
∗
( мы пр едставляем прави ла в
виде пар (r, v
r
)), а операции |=
5
, |=
6
определены следующим
образом: для r = u
1
#u
2
$u
3
#u
4
, (r, v
r
) ∈ R
1
∪ R
2
, и ˆx, ˆy ∈ V
,
z, w ∈ V
∗
, записываем
(ˆx, z) |=
5
0
r
(ˆy, w) тогда и только тогда, когда x = x
1
u
1
u
2
x
2
u
3
u
4
,
z = u
2
z
1
u
3
, y = x
1
u
1
u
2
z
1
u
3
u
4
, w = u
2
x
2
u
3
, при некоторых
x
1
, x
2
, z
1
∈ V
∗
, таких, что v
r
∈ Sub(x
2
), а u
1
u
2
x
2
u
3
u
4
не
9.2. Еще один вариант 407
может быть записана в виде x
0
1
u
1
u
2
x
0
2
u
3
u
4
x
0
3
при |x
0
2
| < |x
2
|,
v
r
∈ Sub(x
0
2
),
ˆx |=
6
0
r
(y, z) тогда и только тогда, когда x = x
1
u
1
u
2
x
2
u
3
u
4
, y =
u
4
x
1
u
1
, z = u
2
x
2
u
3
при некоторых x
1
, x
2
∈ V
∗
, таких, что
v
r
∈ Sub(x
2
) и u
1
u
2
x
2
u
3
u
4
не может быть записано в виде
x
0
1
u
1
u
2
x
0
2
u
3
u
4
x
0
3
при |x
0
2
| < |x
2
|, v
r
∈ Sub(x
0
2
).
Иначе говоря, участки u
1
u
2
, u
3
u
4
должны располагаться в x во-
круг подстроки x
2
, в которую по крайней мере один раз входит
строка v
r
, и x
2
— минимал ьная с этим свойством, т. е. ни од-
на собственна я подстрока в x
2
, содержащая v
r
, не может быть
ограничена участками u
1
u
2
, u
3
u
4
. Таким образом, строки v
r
иг-
рают для правил сплетения роль «якорей», влияние которых
проявляется локально от первого слева от них вхождения u
1
u
2
до первого справа после них вхождения u
3
u
4
.
Использование такой информации о строке x
2
, заменяемой
на z
1
при помощи операции |=
5
0
, — весьма мощный фактор:
благодаря этой операции мы снова сможем охар актер изова ть
рекурсивно перечислимые языки.
Обозначим через EH
2
(cF IN, rF IN) семейство языков, по-
рожденных ограниченными расширенными циклическими H-
системами («c» перед первым FIN указывает на то, что мы на-
чинаем с циклических аксиом, а «r» перед вторым FIN — на
то, что сплетения ограничены в смысле, определенном выше).
Теорема 9.2. Каждый рекурсивно перечислимый язык есть
проекция подходящего языка из семейства EH
2
(cF IN, rF IN).
Доказательство. Рассмотрим язык L ∈ RE, L ⊆ T
∗
. В силу
теоремы 3.14 этот язык можно записать в виде L = g
∗
(a
0
)∩T
∗
,
для некоторых ОПМ g = (K, V, V, s
0
, F, P ) и a
0
∈ V .
Мы построим следующую ограниченную расширенную цик-
лическую H-систему
γ = (V
0
, T
0
, A
1
, A
2
, R
1
, R
2
).
Рассмотрим новый символ E и добавим к P все правила вида
s
f
E → Es
0
для s
f
∈ F . Полученн ое таким способом множество
обозначим через P
0
. Предположим, что P
0
= {r
1
, . . . , r
n
}, где
408 9. Сплетение циклических строк
r
i
: q
i
b
i
→ c
i,1
. . . c
i,t
i
q
0
i
, при t
i
> 0, q
i
, q
0
i
∈ K, b
i
∈ V ∪ {E},
c
i,1
∈ V ∪ {E}, c
i,j
∈ V , 2 6 j 6 t
i
, 1 6 i 6 n.
Рассмотрим также новые символы d
0
, d
1
, . . . , d
n
. Положим
V
0
= V ∪ K ∪ {E, d
0
, d
1
, . . . , d
n
},
T
0
= T ∪ {d
0
, d
1
, . . . , d
n
},
A
1
= {Cir(d
1
d
2
. . . d
n
d
0
s
0
d
0
a
0
d
1
d
2
. . . d
n
d
0
E)},
A
2
= {d
i+1
. . . d
n
d
0
c
i,1
d
1
d
2
. . . d
n
d
0
c
i,2
d
1
d
2
. . . d
n
d
0
. . . c
i,t
i
d
1
d
2
. . . d
n
d
0
q
0
i
d
0
| 1 6 i 6 n},
R
1
= {(d
1
d
2
. . . d
i
#d
i+1
. . . d
n
d
0
$d
0
#, q
i
d
0
b
i
) | 1 6 i 6 n},
R
2
= {(#d
1
d
2
. . . d
n
d
0
$d
0
#, q
f
d
0
E) | q
f
∈ F }.
Посмотрим, как работает эта система.
Пусть имеется циклическая строка ˆx для некоторого
x = x
1
bd
1
d
2
. . . d
n
d
0
qd
0
ad
1
d
2
. . . d
n
d
0
cx
2
при x
1
, x
2
∈ (V ∪ {d
0
, d
1
, . . . , d
n
})
∗
, a, b, c ∈ V ∪ {E}, q ∈ K.
Первоначально x
1
= λ, x
2
= λ, q = s
0
, a = a
0
, c = E, а
b отсутствует. Если qa соответствует правилу r
i
из P
0
, т. е.
q = q
i
, a = b
i
, то в R
1
существует правило сплетения d
1
d
2
. . . d
i
#d
i+1
. . . d
n
d
0
$d
0
#. Благодаря ограниченной форме при-
менения этих правил мы вырезаем из x подстроку x
3
= d
i+1
. . . d
n
d
0
q
i
d
0
b
i
d
1
. . . d
n
d
0
(в x
3
появляется подстрока q
i
d
0
b
i
и
x
3
минимальная с эт им свойством). В A
2
есть только одна
строка, начинающаяся с d
i+1
. . . d
n
d
0
и заканчивающаяся d
0
,
а именно d
i+1
. . . d
n
d
0
c
i,1
d
1
d
2
. . . d
n
d
0
c
i,2
. . . c
i,t
i
d
1
d
2
. . . d
n
d
0
q
0
i
d
0
.
Подставляя ее в x вместо вырезанной ранее строки x
3
, мы
получаем циклическую строку ˆy, где
y = x
1
bd
1
. . . d
n
d
0
c
i,1
d
1
. . . d
n
d
0
c
i,2
. . . c
i,t
i
d
1
. . . d
n
d
0
q
0
i
d
0
cx
2
.
Таким образом, все циклические строки ˆx, возникающие при
использовании правил из R
1
, обладают такими свойствами:
1) лишь одно состояние q ∈ K появляется в x в подстроке вида
qd
0
a, при a ∈ V ∪ {E},
2) каждые два последовательных вхождения символов из V ∪
{E} разделены блоком d
1
d
2
. . . d
n
d
0
,
9.2. Еще один вариант 409
3) q также отделен от его левого соседа из V ∪ {E} блоком d
1
d
2
. . . d
n
d
0
.
Предыдущая операция сплетения имитировала применение
правила r
i
на циклической строке. Попутно возникающая ли-
нейная строка x
3
может быть использована только как неде-
лимая вставка в циклическую строку при сплетении по тому
же правилу (d
1
. . . d
i
#d
i+1
. . . d
n
d
0
$d
0
#, q
i
d
0
b
i
). При этом ни
циклическая строка, ни строка x
3
не меняются.
Следовательно, применяя правила из R
1
, мы можем имити-
ровать работу g, начав с a
0
и итерируя ОПМ благодаря нали-
чию в P
0
правил q
f
E → Es
0
. При возникновении циклической
строки ˆx с x вида
x = x
1
ad
1
d
2
. . . d
n
d
0
q
f
d
0
Ed
1
d
2
. . . d
n
d
0
bx
2
при x
1
, x
2
∈ (V ∪ {d
0
, d
1
, . . . , d
n
})
∗
, a, b ∈ V ∪{λ}, q
0
∈ F , можно
применить соответствующее правило из R
2
.
Мы получим две линейные строки
y = d
1
d
2
. . . d
n
d
0
q
f
d
0
Ed
1
d
2
. . . d
n
d
0
,
z = bx
2
x
1
a.
В первой строке есть нетерминальные символы q
f
и E. Вто-
рая же допускается языком L(γ), если содержит только сим-
волы из T ∪ {d
0
, d
1
, . . . , d
n
}. Мы рассекли цик лич ескую строку
ˆx, руководствуясь положением маркера E, отмечающим конец
строки из g
∗
(a
0
). Поэтому полученная строка — это строка из
g
∗
(a
0
) в правильной циклической перестановке, но с символа-
ми, разделенными блоками d
1
d
2
. . . d
n
d
0
.
Рассмотрим теперь проекцию
pr
T
: (T ∪ {d
0
, d
1
, . . . , d
n
})
∗
−→ T
∗
,
определяемую равенствами
pr
T
(a) = a пр и a ∈ T,
pr
T
(d
i
) = λ при 0 6 i 6 n.
Получаем L = pr
T
(L(γ)), что и завершает доказательство.
410 9. Сплетение циклических строк
Способ реализации ограниченных операций сплетения ти-
па |=
5
0
из предыдущей системы γ мог бы быть следующим.
Рассмотрим кодирование h : (V ∪K ∪{E})
∗
−→ {А, Ц, Г, Т}
∗
(элементов из V ∪ K ∪ {E} строками над алфавитом ДНК).
Для каждого правила r
i
∈ R
1
мы рассматриваем ре-
стрикционный фермент enz
i
, характеризуемый схемой
h
u
i
z
i
v
i
¯u
i
¯z
i
¯v
i
i
.
(Здесь вновь используются обозначения, в веденн ые в гла-
ве 4.) Согласно этой схеме, последовательность, содержащая
подпоследовательность
h
u
i
z
i
v
i
¯u
i
¯z
i
¯v
i
i
, будет разрезана так, чтобы
возникли липкие концы
h
u
i
¯u
i
i
λ
¯z
i
и
z
i
λ
h
v
i
¯v
i
i
соответственно.
Обозначим через α
i
строку u
i
z
i
v
i
, появляющуюся в верхней
цепочке схемы, ассоциированной с enz
i
, 1 6 i 6 n .
Возьмем еще один рестрикционный фермент enz
0
, характе-
ризуемый схемой
h
u
0
z
0
v
0
¯u
0
¯z
0
¯v
0
i
. Обозначим, α
0
= u
0
z
0
v
0
. Последова-
тельности α
i
соответствуют символам d
i
, 0 6 i 6 n.
Далее, элементы γ строятся следующим образом:
(I) циклическая аксиома:
circ(h(s
0
)α
0
h(a
0
)α
1
α
2
. . . α
n
α
0
h(E)α
1
α
2
. . . α
n
α
0
)
λ
,
(II) для каждого прав ила r
i
: sa → xs
0
∈ P или r
i
: s
f
E →
Es
0
, 1 6 i 6 n , мы вводим
1) вспомогательную строку w
i
=
λ
¯u
i
¯z
i
¯v
i
λ
¯u
i+1
z
i+1
λ
λ
¯v
i+1
. . .
λ
¯u
n
z
n
λ
λ
¯v
n
λ
¯u
0
z
0
λ
λ
¯v
0
λ
h(s)¯u
0
z
0
λ
λ
¯v
0
λ
h(a)¯u
1
z
1
λ
λ
¯v
1
. . .
λ
¯u
n
z
n
λ
λ
¯v
n
λ
¯u
0
¯z
0
¯v
0
,
2) аксиому xs
0
при x = b
1
b
2
. . . b
k
, b
i
∈ V , 1 6 i 6 k,
k > 1, в виде w
0
i
=
z
i
v
i
λ
α
i+1
...α
n
α
0
h(b
1
)α
1
...α
n
α
0
h(b
2
)α
1
λ
. . .
α
n
α
0
...α
o
h(b
k
)α
1
...α
n
α
0
h(s
0
)
λ
h
u
0
¯u
0
i
λ
¯z
0
,
w
00
i
=
z
i
v
i
λ
α
i+1
...α
n
α
0
h(s
0
)
λ
h
u
0
¯u
0
i
λ
¯z
0
, если x = λ,
(III) для каждого s
f
∈ F также вводится вспомогательная
строка w(s
f
) =
λ
¯u
1
¯z
1
¯v
1
λ
¯u
2
z
2
λ
λ
¯v
2
. . .
λ
¯u
n
z
n
λ