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

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

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

В случае увеличивающего длину режима мы должны иметь

2n + m > 2n + 1 (и значит, m > 2), а также 2n + m > 2m

(и значит, m < 2n). Данный язык контекстно-свободным не

является.

Все свойства незамкнутости CS следуют из леммы 11.1.

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

це 11.1, доказаны.

Стоит особо отметить следующие факты из таблицы 11.1:

1) две разновидности сплетения «прорывают» барьер регуляр-

ности и пять из них — барьер контекстной свободы,

2) ни одна из рассмотренных выше операций не сохраняет ли-

нейные языки; это, главным образом, происходит потому,

что с помощью сплетения (и полу-AFL операций, относи-

тельно которых LIN замкнуто) мы можем смоделировать

операцию произведения,

3) ни одна из предыдущих операций, за исключением спле-

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

языков; это, в основном, обусловлено тем, что с помощью

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

вольной длины.

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

ждения, касающиеся семейств LIN, CF в строках pr, sf и sl.

Более точно, непонятно, справедливы ли для данной схемы

сплетения σ и языка L ∈ LIN (или L ∈ CF ) отношения σ

(L) ∈

CS, g ∈ {pr, sf, sl}, или же, как и в таблице 11.1, выполняется

более слабое включение σ

(L) ∈ RE. Во всяком случае пред-

ставляется, что семейства S

(LIN, F IN) = {σ

(L) | L ∈ LIN},

g ∈ {pr, sf, sl}, очень велики.

Теорема 11.2. Каждый язык L ∈ RE может быть пред-

ставлен как образ языка из S

(LIN, F IN) при некотором

морфизме.

Доказательство. Благодаря следствию 3.3 мы знаем, что каж-

дый рекурсивно перечислимый язык L ⊆ V

∗

может быть пред-

ставлен в виде L = h

∩ L

), где h

— некоторый морфизм,

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

а L

, L

∈ LIN . Рассмотрим символы a, b, c, не лежащие в V .

Как и в доказательстве леммы 11.4, положим

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

= {a}L

{c} ∪ {b}L

{cc}.

Для L

= σ

) и h : (V ∪ {a, c})

∗

−→ V

∗

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

равенствами h(a) = h(c) = λ и h(d) = h

(d) при d ∈ V , мы

получаем L = h(L

Следствие 11.1. Для каждого семейства языков FL, стро-

го лежащего в RE и замкнутого относительно произвольных

морфизмов, выполняется S

(LIN, F IN) − F L 6= ∅.

Изучение расширенных H-систем, основанных на опреде-

ленных выше операциях `

, g ∈ D, остается темой для иссле-

дования. В частности, интересен случай g = rc, который мо-

жет иметь некие «реалистичные» интерпретации. К примеру,

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

отношением сходства, помогающим некоторым ферментам ра-

ботать со строками одного и того же класса.

11.2 Системы репликаций

В разделе 9.1 мы рассмотрели следующую операцию, произво-

дившую из циклической строки ˆx и линейной строки v линей-

ную строку w:

(ˆx, v) |=

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

x = x

v = v

w = v

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

, v

∈ V

∗

, и правила сплетения r =

над V . Иначе говоря, между u

, u

в v вставля-

лась строка, получаемая при рассечении ˆx между u

и u

. Это

было возможно, так как мы знали, что u

, u

описывают

парные липкие концы. Такую операцию можно рассмотреть

и для двух линейных строк, считая что строка-вставка —

11.2. Системы репликаций 473

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

потребуется сделать разрез в двух местах. Таким образом, мы

приходим к следующему общему определению.

Система репликаций степени n, n > 1 — это структур а

γ = (V, A, C

, C

, . . . , C

где

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

2. A — конечный язык над V , а

3. C

, 1 6 i 6 n , — конечные подмножества V

∗

Элементы языков A называются аксиомами, а элементы под-

множеств C

, 1 6 i 6 n , — разрезающими правилами.

Для x, y, z ∈ V

∗

и 1 6 i 6 n мы пишем

(x, y) B

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

x = x

y = y

z = x

при u

, u

∈ C

и x

, x

, y

∈ V

∗

Другими словами, мы вставляем подстроку v

строки

y между u

, v

в x, зная, что схемы u

, u

соответ-

ствуют при работе рестрикционных ферментов парным лип-

ким концам. На это указывает то, что три разрезающих пра-

вила берутся из одного множества C

Теперь мы можем продолжить, как и в случае операции

сплетения. Для системы репликаций γ = (V, A, C

, C

, . . . , C

)

и языка L ⊆ V

∗

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

σ(L) = {z ∈ V

∗

| (x, y) B

z, для x, y ∈ L, 1 6 i 6 n},

(L) = L,

i+1

(L) = σ

(L) ∪ σ(σ

(L)), i > 0,

∗

(L) =

[

i>0

(L).

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

Далее, язык, порожденный γ, определяется равенством

L(γ) = σ

∗

(A)

(мы начинаем с аксиом A и итеративно выращиваем строки с

помощью репликаций, использующих разрезающие правила из

, . . . , C

Скажем, что разрезающее правило u#v имеет радиус p, если

p = max{|u|, |v|}. Систему репликаций будем называть систе-

мой радиуса p, если p — максимальный радиус его разрезаю-

щих правил.

Мы обозначаем через REP

([m]) семейство языков, порож-

денных системами репликаций с не больше чем n компонента-

ми, n > 1, и радиуса не выше m, m > 1. Если число компонент

не ограничено, индекс n заменяется на ∗, если же не ограни чен

радиус, мы заменяем [m] на F IN. Таким образом,

REP

∗

(F IN) =

[

n>1

[

m>1

REP

([m])

[

n>1

REP

(F IN).

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

дующий результат.

Лемма 11.10. REP

∗

(F IN) ⊆ CS.

Системы репликаций γ = (V, A, C

, . . . , C

), такие, что

card(C

) = 1, 1 6 i 6 n, называются однородными. (Определяя

(x, y) B

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

для x, и для y: x = x

uvx

, y = y

uvy

и z = x

uvy

uvx

В определении отношения B делается два важных выбо-

ра: (1) строки для вставки и (2) места, где эта вставка осу-

ществляется. В каждом случае можно рассмотреть несколько

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

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

определенного выше. Здесь же мы исследуем лишь некоторые

возможности, появляющиеся при ответе на первый вопрос. А

именно, мы рассмотрим простые системы репликаций,, т. е.

11.2. Системы репликаций 475

однородные системы радиуса 1, степени 1 и обладающие лишь

одной аксиомой.

Итак, простая система репликаций — это структура

γ = (V, w, a#b),

где V — алфавит, w ∈ V

(аксиома) и a, b ∈ V . Более того, мы

разрешаем репликацию лишь для одинаковых строк, т.е. само-

репликацию (в любом случае на первом шаге работы системы

доступно только w, поэтому мы должны выполнить операцию

типа (w, w ) B z).

Специально для простой системы репликаций γ = (V, w,

a#b) и x, y ∈ V

∗

мы записываем

x y

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

(1) x = x

abx

, x

∈ V

∗

(2) y = x

azbx

при z = bz

= z

a, z

, z

∈ V

∗

(3) z ∈ Sub(x).

Никаких ограничений не накладывается ни на положение

подстроки ab в x (условие (1)), ни на способ выбора z из Sub(x)

(условие (3)). Мы обсуд им здесь десять возможностей, возни-

кающих при попытке уточнить условие (3).

Вместо (3) можно рассмотреть следующие более жесткие

условия (во всех случаях z = bz

= z

a):

1. z = x (тотально ; t),

2. z ∈ Pref(x) (произвольный префикс; ap),

3. z ∈ Pref(x) и z максимальный (если x = z

= bz

= z

a, то |z| > |z

|) (максимальный префикс; Mp),

4. z ∈ Pref(x) и z минимальный (если x = z

= bz

= z

a, то |z| 6 |z

|) (минимальный префикс; mp),

5. z ∈ Sub(x) и z самая левая (если x = u

, x = u

= bz

= z

a, то |u

| 6 |u

|) (произвольная самая

левая; al),

6. z ∈ Sub(x), z самая левая и максимальная (x = u

если x = u

, z

= bz

= z

a, то |u

| 6 |u

|; более того,

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

если x = u

= u

, z

= bz

= z

a, то |z| > |z

(максимальная самая левая; Ml),

7. z ∈ Sub(x), z самая левая и минимальная (x = u

если x = u

, z

= bz

= z

a, то |u

| 6 |u

|; более того,

если x = u

= u

, z

= bz

= z

a, то |z| 6 |z

(минимальная самая левая; ml),

8. z ∈ Sub(x) и z максимальная (если x = u

и x = u

= bz

= z

a, |u

| 6 |u

|, |u

| 6 |u

|, то z = z

)

(произвольная максимальная; aM),

9. z ∈ Sub(x) и z минимальная (если x = u

и x = u

= bz

= z

a, |u

| > |u

|, |u

| > |u

|, то z = z

)

(произвольная минимальная; am).

Отношение соответствует случаю

10. z ∈ Sub(x) (любая подстрока, свободная; af).

Мы обозначаем через D множество только что определен-

ных режимов выбора вставляемой строки {t, ap, Mp, mp, al,

Ml, ml, af, aM, am}. Еще раз подчеркнем, что во всех случаях

1 — 10, z — это строка вида z = bz

= z

a. (При a = b возможно

равенство z = a, но при a 6= b, |z| > 2.)

При репликации, выбирающей вставляемую строку в режи-

ме g ∈ D, мы пишем x

Через

∗

мы обозначаем рефлексивное и транзитивное за-

мыкание отношения

, g ∈ D. (Мы называем его репликаци-

онной цепочкой.) Далее, язык, порожденный системой репли-

каций γ = (V, w, a#b) в режиме g ∈ D, опред еляется равен-

ством

(γ) = {z ∈ V

∗

| w

∗

z}.

Через SREP (g) мы обозначаем семейство языков вида

(γ), где g ∈ D, а γ — простая система репли каций.

Возникает десять семейств языков. Мы кратко исследуем

соотношения между ними и связи с семействами Хомского.

Начнем с рассмотрения двух примеров.

Пример 11. 1. Рассмотрим репликационную систему

= ({a, b}, baba, a#b).

11.2. Системы репликаций 477

Во всех случаях получаемые строки содержатся в (ba)

: мы

начинаем с (ba)

при (ba)

y, вставляем строку b(ab)

i > 0, между двумя символами ab, и, следовательно, строка y

принимает вид (ba)

, m > n.

Имеем

(γ

) = (ba)

ba при g ∈ {ap, mp, al, ml , af , am}.

Действительно, при любом минимальном режиме (префикс, са-

мый левый, произвольный) мы должны вставить строку ba. Во

всех свободных режимах мы можем вставить ba. Следователь-

но, (ba)

ba ⊆ L

(γ

). Выше было отмечено обратное включе-

ние. Кроме того,

(γ

) = {(ba)

| n > 1} для g ∈ {Mp, Ml, aM , t}.

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

ка, максимальная подстрока) вида z = bz

a в строке (ba)

сов-

падает с (ba)

, а значит, x

y для указанного g означает

y = x

. Это и доказывает равенство.

Пример 11. 2. Рассмотрим теперь систему

= ({a, b}, abb, b#b).

Получаем

(γ

) =







b при g ∈ {al, ml, af, am},

abb при g ∈ {ap, mp, Mp, t},

{ab

| n > 1} при g ∈ {aM, M l }.

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

серию необходимых условий.

Лемма 11.11. (i) Любой репликационный язык либо одно-

элементен, либо бесконечен.

(ii) Для любого репликационного языка L ⊆ V

∗

имеем

card(Pref(L) ∩ V ) = 1, card(Suf(L) ∩ V ) = 1.

Доказательство. (i) Рассмотрим репликационную систему

γ = (V, w, a#b). Если к w невозможно применить операцию

репликации (либо в w нет подстроки ab, либо w не содержит

подходящей подстроки z = bz

= z

a), тогда L

(γ) = {w}.

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

Если w

, то w = w

abw

, и в Sub(w) имеется z =

= z

a, удовлетворяющая соответствующему g условию, и

= w

azbw

Ясно, что w

снова содержит подстроку ab, так же как и

подстроки, начинающиеся с b, а заканчивающиеся a (такова,

например, z). Следовательно, мы снова можем провести ре-

пликацию. Это очевидно при всех режимах g ∈ {al, ml, Ml, af,

am, aM}.

Если z ∈ Pref(w), и значит, w = zw

, то w

= w

azbw

и найдется x ∈ Pref(w

), такой, что x = bx

= x

a. Действи-

тельно, так как z = bz

∈ Pref(w) и w

a ∈ Pref(w), мы имеем

b ∈ Pref(w

a) ⊆ Pref(w

). Поскольку z = z

a и w

= w

abw

префикс w

a оканчивается на a. Следовательно, можно сно-

ва повторить репликацию в любом режиме g ∈ {ap, mp, Mp}.

В случае t мы имеем w = z и w

= w

awbw

. Как и раньше,

мы получаем w

= bw

a. Следовательно, повторная реплика-

ция возможна и в этом случае.

Этот процесс может повторяться во всех режимах, следо-

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

(ii) Непосредственно из определений операций репликации

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

изменяются, они остаются теми же, что и у аксиомы.

Лемма 11.12. Если L ∈ SR EP (g) для g ∈ {ap, mp, M p, t} —

бесконечный язык с b = Pref(L) ∩ V , то для каждого n > 1

существует x ∈ L, такой, что |x|

> n.

Доказательство. Возьмем γ = (V, w, a#b) с бесконечным

(γ) = L для g указанного типа. Поскольку L бесконечно,

существует такая строка w

, что w

. Отсюда следует,

что w начинается с b, и значит, b = Pref(L) ∩ V . Более того,

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

на каждом шаге префикс текущей строки (или строку целиком

в случае g = t). При каждой репликации вводится дополни-

тельный экземпляр символа b: если x

y, x = x

abx

, то

y = x

azbx

при z ∈ Pref(x), z = bz

. Следо ватель но, число

вхождений символа b неограниченно.

11.2. Системы репликаций 479

Лемма 11.13. Если L ∈ SREP (t) — бесконечный яз ык, то

для a = Suf(L) ∩V , b = Pref(L) ∩ V и каждого n > 1, найдется

x ∈ L, такой, что |x|

> n, |x|

> n.

Доказательство. Мы поступ аем в точ ности так, как и в

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

символы w (репликация оставляет их на своих местах, а

количество их вхождений в текущей строке неограниченно

возрастает).

Лемма 11.14. Для любого бесконечного языка L ∈ SREP (t)

с V = alph(L) имеем Ψ

(L) = {π · 2

| n > 0} при некотором

π ∈ N

, k = card(V ).

Доказательство. Если L = L

(γ) для некоторой γ =

(V, w, a#b), и L бесконечный, то существуют сколь угодно

длинные репликационные цепочки

ρ : w = w

. . .

Ясно, Ψ

i+1

) = 2 · Ψ

), i > 1. Значит, Ψ

) = 2

i−1

), i > 1, и это верно для всех цепоч ек ρ. Следовательно,

(L) = {Ψ

(w) · 2

| n > 0}, т. е. π в лемме суть Ψ

(w).

Лемма 11.13 является очевидным следствием леммы 11.14.

Лемма 11.15. Для любого бесконечного языка L ∈ SREP (g),

g ∈ {Mp, Ml, aM}, с V = alph(L), существуют π

, π

∈ N

k = card(V ), такие, что Ψ

(L) = {π

+ π

· 2

| n > 0}.

Доказательство. Возьмем γ = (V, w, a#b), такую, что

L = L

(γ), и исследуем репликационную цепочку произ-

вольной длины

ρ : w = w

. . .

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

= x

abx

, w

= x

для z

мак-

симальной в w

вида z

= bz

= z

a. Это означает, что в

= y

подстрока z

начинается с самого левого в w

сим-

вола b, а заканчивается самым правым в w

символом a.

Если w

= y

и это — самое левое в w

вхождение b, то

снова w

= y

. Действительно, если место вставки распо-

ложено справа от этого символа b, то префикс y

b строки w

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

появляется в w

неизмененным. Если же оно находится слева

от b, то, поскольку этот символ b самый левый, вставка осу-

ществляется сразу перед ним. Следовательно, y

оканчивается

на a, и мы получаем w

= y

, т. е. префикс y

опять же сохраняется.

Аналогично, если символ a из w

= y

— самый правый

в w

, то суффикс ay

появляется и в w

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

= y

, w

= y

, где строка z

на-

чинается с b, заканчивается a, и является максимальной с эти-

ми свойствами в w

. Кроме того,

| = |w

| − |y

| = |w

| − |y

= |y

| + |z

| − |y

| = 2|z

Таким образом, на каждом шаге ρ мы получаем строку вида

с Ψ

i+1

) = 2 · Ψ

), i > 1. При π

= Ψ

) и

= Ψ

), выполняется утверждение леммы (ясно, что если

∈ Pref(w

), то z

i+1

∈ Pref(w

i+1

)).

Контраст с двумя предыдущими леммами составляет

Лемма 11 .16 . Для любого g ∈ {af, am, ap, mp, al, ml} и беско-

нечного языка L ∈ SREP (g) существует такая константа k,

что для лю бого x ∈ L можно подобрать y ∈ L, при котором

y и |x| < |y| 6 |x| + k.

Доказательство. Возьмем γ = (V, w, a#b) и z ∈ Sub(w), такое

что w

, w = w

abw

, w

= w

azbw

. При g =af мы можем

снова вставить z. При g = am мы можем вставить z, если z —

минимум, или более короткую строку в противном случае.

Если z ∈ Pref(w), то z ∈ Pref(w

az) ⊆ Pref(w

), и значит,

при g = ap мы снова можем использовать z, а для g = mp

можем использовать z или более короткий префикс.

Такие же утверждения будут верны и при самых левых ва-

риантах выбора строки для вставки.

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

дом шаге x

y при w

∗

x мы имеем |x| < |y| 6 |x| + |w|.

Полагая k = |w|, приходим к требуемому утверждению.