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

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

6.2. Характеризации языков из RE 251

(λ, c/λ, λ).

Ясно, что если ВУ-система γ корректно моделирует кон-

текстно-свободные правила из P

, то она порождает язык L(G).

Рассмотрим строку w ∈ (N ∪ T ∪ {c})

∗

. К ней можно приме-

нить лишь правила из группы B и правило типа 1 из группы A.

То есть ее подстроку Sc можно заменить на S[S, r]c, для неко-

торого r ∈ P

. Предположим, что w = w

Scw

(первоначально,

= w

= λ), и воспользуемся упомянутым выше правилом

для r : S → X

. . . X

, k > 1. Получим w

S[S, r]cw

. Из [S, r]

изготовим X

. . . X

. Поскольку X

6= c и k > 1, в w

S[S, r]cw

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

ше не может использоваться. Нам придется удалять символ S,

используя правила 2 и 3 (K — «киллер» стоящего перед ним

символа):

S[S, r]cw

=⇒ w

SK[S, r]cw

=⇒ w

[S, r]cw

Единственный путь продолжения состоит в использовании

правил типов 4, 5, 8, поскольку для внесения в строку сим-

вола K, необходимого для удаления символ ов [S, r], [X

, r, i],

1 6 i 6 k − 1, требуется, чтобы слева и справа от него по-

явились символы вида [S, r], [X

, r, i], 1 6 i 6 k − 1. Таким

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

[S, r]cw

=⇒ w

[S, r][X

, r, 1]cw

=⇒ w

[S, r][X

, r, 1][X

, r, 2]cw

=⇒ . . .

=⇒ w

[S, r][X

, r, 1] . . . [X

k−1

, r, k − 1][X

, r, k]cw

После этих шагов, сделанных возможно вперемежку с шагами

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

ных скобках мы должны вставить между [S, r] и [X

, r, 1] сим-

вол K, а между [X

, r, i] и [X

i+1

, r, i + 1], для каждого 1 6 i 6

k − 1, символ X

. Получим строку

, r]K[X

, r, 1]X

, r, 2]X

. . . [X

k−1

, r, k − 1]X

k−1

, r, k]cw

252 6. Системы вставки и удаления

Блок [S, r]K уже можно удалить. Это единственный спо-

соб удаления символа [S, r ]. Между [X

, r, i] и X

можно

вставить K, а затем удалить его вместе с [X

, r, i]. Это един-

ственный способ удаления символов [X

, r, i], 1 6 i 6 k − 1.

Таким образом, получим строку w

. . . X

k−1

, r, k]cw

Для того чтобы удалить [X

, r, k], нужно сначала вставить

символ F , а в его присутствии символ X

. . . X

k−1

, r, k]cw

=⇒ w

. . . X

k−1

, r, k]F cw

=⇒ w

. . . X

k−1

, r, k]X

F cw

Теперь [X

, r, k] можно удалить так же, как были удалены

остальные символы [X

, r, i], т. е. вставкой K между [X

, r, k]

и X

. Символ F можно удалить, введя перед ним символ K

убрав их вместе.

Отметим, что если S не входит в X

. . . X

, то никакое пра-

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

нии вывода. Если же в X

. . . X

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

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

пы A. Символ c можно удалить с помощью правила (λ, c/λ, λ)

группы B. Если сделать это тогда, когда еще присутствует

символ S, то его станет н евозможно удалить, а значит, станет

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

вательно, L(γ) = L(G).

Насколько велико семейство IN S

DEL

, неизвестно, но ка-

жется, что для порождения не контекстно-свободных языков,

надо потребовать, чтобы по крайней мере один из парамет-

ров m (максимум длины контекстов при вставке), p (максимум

длины удаляемой строки) или q (максимум длины контекстов

при удалении) был бол ьше единицы. В подтверждение этого

предположения можно привести следующий пример.

Теорема 6.4. INS

∗

DEL

⊆ CF.

Доказательство. Возьмем ВУ-систему γ = (V, T, A, R) веса (n,

1; 0, 0), для некоторого n > 1. Поскольку уд ален ия невозмож-

ны, можно убрать из A все аксиомы, не лежащие в T

∗

, а из

6.2. Характеризации языков из RE 253

R все правила, содержащие нетерминальные символы. Итак,

можно считать, что V = T .

Построим контекстно-свободную грамматику

G = (N, V, S, P ),

где

1. N = {S} ∪ {(λ, a), (a, b), (a, λ) | a, b ∈ V },

2. P = {S → (λ, a

)(a

, a

)(a

, a

) . . . (a

k−1

, a

)(a

, λ) | a

. . . a

∈ A, k > 1, a

∈ V , 1 6 i 6 k}

∪ {(a, b) → (a, a

)(a

, a

) . . . (a

, b) | (a, λ/a

. . . a

, b) ∈ R,

или (a, λ/a

. . . a

, λ) ∈ R, или (λ, λ/a

. . . a

, b) ∈ R,

или (λ, λ/a

. . . a

, λ) ∈ R, k > 1, a

∈ V , 1 6 i 6 k,

a, b ∈ V }

∪ {(λ, a) → (λ, a

)(a

, a

) . . . (a

k−1

, a

)(a

, a) | (λ, λ/a

. . . a

, a) ∈ R, или (λ, λ/a

. . . a

, λ) ∈ R, k > 1, a

∈ V ,

1 6 i 6 k, a ∈ V }

∪ {(a, λ) → (a, a

)(a

, a

) . . . (a

k−1

, a

)(a

, λ) | (a, λ/a

. . . a

, λ) ∈ R, или (λ, λ/a

. . . a

, λ) ∈ R, k > 1, a

∈ V ,

1 6 i 6 k, a ∈ V }

∪ {(λ, a) → a, (a, λ) → λ | a ∈ V }

∪ {(a, b) → b | a, b ∈ V }.

Правила S → x вместе с терминальными правилами из P

дают строки из A. Правила из R моделируются соответству-

ющими правилами из P . Символы (a, b) хранят «следы» пар

символов текущей стро ки (т. е. то, что можно получить из этих

пар при выводе), а символы (λ, a), (a, λ) дают возможность мо-

делировать действие правил (u, λ/x, v) с u = λ или v = λ в

начале или соответственно в конце текущей строки. Следова-

тельно, L(γ) = L(G), откуда L(γ) ∈ CF .

Это наилучший результат подобного типа, поскольку верна

Теорема 6.5. INS

DEL

содержит неполулинейные языки.

Доказательство. Рассмотрим следующую ВУ-систему веса

(2, 2; 0, 0):

γ = ({a, b, c, d, f, g}, {a, b, c, d, f, g}, {fabcdf}, R),

254 6. Системы вставки и удаления

в которой множество R состоит из следующих правил:

(f, λ/ga, ab), (aa, λ/b, bc), (bb, λ/c, cd),

(cc, λ/d, da), (dd, λ/a, ab), (cc, λ/d, df).

Начиная с подстроки fab текущей строки, эти правила по-

следовательно удваивают каждое из вхождений символов

a, b, c, d. Отметим, что все правила, за исключением перво-

го, имеют вид (u, λ/x, v), где u = αα , α ∈ {a, b, c, d}, а v

принадлежит множеству {ab, bc, cd, da}, кроме последнего

правила, в котором v = df. Пары ab, bc, cd, da назовем ле-

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

ки строки вида (abcd)

Ясно, что, начав со строки вида wf(abcd)

f (первона-

чально у нас w = λ и n = 1), мы можем дойти до строки

wfg(aabbccdd)

xy(abcd)

f, (∗)

в которой m > 0, p > 0, m + p + 1 = n, y — суффикс abcd,

т. е. abcd = zy, а x получен удвоением каждого символа z.

При m = n − 1 и y = λ получим строку wfg(aabbccdd)

т. е. длина строки, возникшей между g и f , равна 8n, что

вдвое больше длины первоначальной строки (abcd)

(g, λ/c, aa), (ca, λ/c, a), (ca, λ/d, bb),

(db, λ/d, b), (db, λ/a, cc), (ac, λ/a, c),

(ac, λ/b, dd), (bd, λ/b, d), (bd, λ/c, aa).

Начиная с подстроки gaa, т. е. со вставленного правилами

первой группы символа g, эти правила заменяют каждую

подстроку αα, α ∈ {a, b, c, d}, на βαβα, β ∈ {a, b, c, d}, таким

образом, чтобы все пары βα, αβ были нелегальны. Из того,

что все правила группы 2, за исключением первого, имеют

вид (u, λ/x, v), где u — нелегальная пара, следует, что эти

правила можно применять только слева направ о с соблюде-

нием порядка, в котором они выписаны. Поскольку в стро-

ке uv из каждого правила (u, λ/x, v) группы 2 содержится

6.2. Характеризации языков из RE 255

пара αα, α ∈ {a, b, c, d}, то применение правил группы 2

возможно лишь после применения прав ил группы 1. Следо-

вательно, из строки вида (∗) после использования правил

группы 2 можно получить либо строку вида

wfg(cacadbdbacacbdbd)

uv(aabbccdd)

xy(abcd)

f, (∗∗)

где 0 6 r 6 m, r + s + 1 = m, v — суффикс aabbccdd, т. е.

zv = aabbccdd, а строка u получена «трансляцией» строки z

с помощью правил второй группы, либо строку вида

wfg(cacadbdbacacbdbd)

y(abcd)

где строка x

получена из префикса x при «трансляции» по

приведенным выше правилам.

Заметим, что правила второй группы тоже удваивают

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

ются. Таким образом, из строки (∗) вида wf g(aabbccdd)

можно получить строку wfg(cacadbdbacacbdbd)

f, подстро-

ка которой, заключенная между g и f, имеет длин у 16n, что

вдвое боль ше длины (aabbccdd)

и вчетверо больше длины

первоначальной строки (abcd)

(b, λ/c, df), (d, λ/a, bc), (b, λ/c, da),

(c, λ/a, bc), (c, λ/d, ab), (a, λ/b, cd),

(a, λ/c, da), (b, λ/d, ab), (d, λ/b, cd),

(gc, λ/f, ab).

Все эти правила имеют вид (u, λ/x, v), где v — легальная па-

ра, или в первом правиле v = df. Более того, в каждом пра-

виле, за исключением последнего, v = αβ, где α, β ∈ {a, b,

c, d}, u ∈ {a, b, c, d}, и uα — нелегальная пара. Каждое пра-

вило вставляет между u и v символ x таким образом, что по-

лучается легальная пара xβ. Следов ательн о, правила груп-

пы 3 можно применять только слева направо с соблюдением

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

слева символа f по первому правилу, л ибо с край ней п ра-

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

256 6. Системы вставки и удаления

самом деле, только в этой пози ци и есть трехбуквенная под-

строка uαβ, в которой uα — нелегальная, а αβ — легаль-

ная пара. Используя приведенные выше правила, получим

только легальные пары, т. е. придем к строке, содержащей

подстроки abcd.

Из того, что правилам групп 1 и 2 для работы нужны

подстроки γγ, γ ∈ {a, b, c, d}, следует, что правила первой

группы можно применять лишь после «легализации» всех

пар символов. Таким образом, первое правило группы 1

можно применять только после использования последнего

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

вола f.

Применение правил третьей группы снова удваивает

длину строки. Сл едова тельн о, строка вида (∗∗) по этим

правилам перерабатывается в строку

wfgcf(abcd)

v(aabbccdd)

xy(abcd)

где u

получается из u описанным в ыше способом. Когда

строка wfg(aabbccdd)

f по правилам группы 2 пер ерабо та-

на в строку wf g(cacadbdbacacbdbd)

f, тогда правила тре-

тьей группы дают строку wfgcf(abcd)

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

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

используя вновь правила группы 1.

Описанная выше грамматика порождает неполулинейный

язык. Для доказательства этого воспользуемся следующим

вспомогательным результатом.

Утверждение 6.1. Если E ⊆ (N −{0})

— полулинейное мно-

жество, то для каждой пары (i, j), 1 6 i, j 6 n, выполняется

одно из двух следующих свойств:

(1) Существует такая константа k

i,j

, что

6 k

i,j

для всех

векторов (u

, . . . , u

) ∈ E.

(2) Существуют векторы (u

, . . . , u

) ∈ E, в которых одна

из компонент u

, u

зафиксирована, а другая может быть

подобрана сколь угодно большой.

6.2. Характеризации языков из RE 257

Это утверждение можно доказать следующим образом. Ес-

ли E =

t=1

, где E

⊆ (N − {0})

— линейные множества,

1 6 t 6 k, и

= {v

s=1

| x

, . . . , x

∈ N}

для некоторых векторов v

, 0 6 s 6 m

, то v

(r) > 0 для всех

1 6 r 6 n (в векторах из E нет нулевых компонент). Далее

(1) если v

(i) > 0, v

(j) > 0 для всех 1 6 s 6 m

, то для всех

, . . . , u

) ∈ E

имеем

6 k

(t)

i,j

для

(t)

i,j

max{v

(i) | 0 6 s 6 m

}

min{v

(j) | 0 6 s 6 m

}

;

(2) если, например, v

(j) = 0, v

(i) > 0 для данного s, 1 6 s 6

, то множество {v

+ v

x | x ∈ N} содержит в ектор а с

i-й компонентой, равной v

(i) + xv

(i), т. е. сколь угодно

большой, и j-й компонентой, равной v

(j).

Теперь, если для линейного множества E

выполняется

условие пункта 2 (т. е. свойство 2 из условия), то оно выпол-

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

для E выполняется свойство 1, взяв k

i,j

= max{k

(t)

i,j

| 1 6 t 6 k}.

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

ражение Париха Ψ

, ассоциированное с V = {g, a, b, c, d, f} (об-

ратите внимание на порядок). Приведенное выше утвержде-

ние не выполняется для множества Ψ



L(γ)



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

рассмотрим в шестерках из Ψ



L(γ)



первую и вторую пози-

ции (соответствующие символам g и a). Из приведенных выше

объяснений можно увидеть, что пра вил а групп 1, 2 и 3 могут

применяться только в этом порядке. В каждом таком цикле в

данную строку вставляется ровно один символ g и несколько

символов a, причем число символов a может увеличиться не

более чем в восемь раз. Следовательно, для каждой шестер-

ки (u

, . . . , u

) ∈ Ψ



L(γ)



можно написать u

6 u

6 8

причем для каждого u

в L(γ) есть такой вектор, в котором

258 6. Системы вставки и удаления

= 8

. То есть отношение

может быть сколь угодно ве-

лико, а при фиксированном u

компонента u

не может быть

произвольно большой. Из этого следует, что приведенное выше

утверждение не выполняется, а значит, Ψ



L(γ)



не является

полулинейным.

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

зывающий, что одна только операция вставки не «слишком

сильна».

Теорема 6.6. LIN − IN S

∗

DEL

6= ∅.

Доказательство. Язык L = {a

| n > 1} не лежит в семей-

стве INS

∗

DEL

. В са мом деле, ясно, что если бесконечный

язык L

попадает в INS

∗

DEL

, то бесконечное число строк

z ∈ L

можно так представить в виде z = uxv, что x 6= λ и

uv ∈ L

. Язык L не обладает таким свойством.

6.3 Односимвольные системы

вставки и удаления

Ограничение сверху длины контекстов при вставке и удалении

какой-либо малой величиной (н апр имер двумя, как в теоре-

мах 6.2 и 6.3) интересно с математической точки зрения, но не

очень важно с т очки зрения молекулярных вычислений: кон-

тексты (u, v) на рис. 6.1 и 6.2 должны быть «достаточно боль-

шими» для того, чтобы гарантировать стабильность получив-

шейся структуры. Биохимические же условия требуют нало-

жить иные ограничения. А именно, ограничимся вставкой и

удалением строк, состоящих из какого-то одного символа (та-

кого как У в случае РНК). Разумеется, мы не сможем рабо-

тать лишь с одним символом из н ашего алфавита, поскольку,

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

символьном алфавите приводит к экспоненциальному возрас-

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

троль за процессом вывода, поскольку контекст может пред-

ставлять собой любую достаточно длинную строку.

6.3. Односимвольные системы вставки и удаления 259

Необходим по крайней мере еще один допол нител ьный сим-

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

Следовательно, придется заранее запасти в рабочей области

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

можно вставлять и удалять. Вдобавок будем считать выход-

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

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

но остаются на месте.

Более того, поскольку нужно манипулировать только по-

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

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

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

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

ходе получались строки символов общего алфавита. Таким об-

разом, мы приходим к следующему варианту ВУ-системы.

Ограниченная ВУ-система — это конструкция

γ =



V, {a, c}, A, R, h



в которой

1. V — алфавит,

2. a, c — выделенные символы (не обязательно из алфавита V ),

3. A — конечное подмножество множества {a, c}

∗

4. R — конечное множество троек вида (u, α/β, v), где u, v ∈

{a, c}

∗

и α, β ∈ c

∗

, причем одна из строк α, β пуста, и, нако-

нец,

5. h : V

∗

−→ {a, c}

∗

— морфизм.

Вставлять и удалять можно лишь строки вида c

, i > 1, в каче-

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

обоих символов a и c. Отношения =⇒ оп редел яется на {a, c}

∗

как обычно. Теп ерь определим язык, порожденный системой γ,

как

L(γ) = h

−1



{w ∈ {a, c}

∗

| z(aca)

=⇒

∗

(aca)

для некоторых n, m > 0, z ∈ A}



260 6. Системы вставки и удаления

Таким образом, вывод начинается с аксиомы z ∈ A, к которой

справа пр ипи сано произвольное число «пробелов» aca. В про-

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

удаления. Затем отбрасываются «пробелы» на левом конце по-

лучившийся строки. И, наконец, к тому, что осталось, приме-

няется отображение h

−1

, которое выдает строку из V

∗

. Таким

образом, строки w, для которых h

−1

(w) не определено, удаля-

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

и при использовании специального терминального алфавита.

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

ми ВУ-системами произвольного веса, через 1INSDEL. По-

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

над {a, c}, невозможно огра нич ить (например, независимо от

мощности алфавита V ) вес используемых систем.

Следующий результат, вполне ожидаемый после тео-

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

помощью ДНК и РНК.

Теорема 6.7. RE = 1INSDEL.

Доказательство. Рассмотрим язык L ⊆ T

∗

, L ∈ RE, и по-

рождающую его грамматику G = (N, T, S, P ), заданную в нор-

мальной форме Куроды. Пусть N ∪ T = {α

, . . . , α

}, а α

= S.

В P могут быть правила следующих видов:

→ α

, (1)

→ λ, (2)

→ α

, (3)

→ α

. (4)

Рассмотрим новый специальный символ α

= #, обознача-

ющий пустое место, и будем считать, что вывод начинается не с

аксиомы S, а со строки S#

для некоторого s > 0. Тогда можно

заменить в P все правила видов на правила вида 4, следующим

образом:

→ α

для α

→ α

∈ P, (1)

→ α

для α

→ λ ∈ P, (2)