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

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

8.3. Языки-мишени 351

семейство RE с помощью H-систем с конечными множествами

правил сплетения.

Расширенная H-система с локальными мишенями — эт о

структура γ = (V, T, A, R), где V — алфавит, T ⊆ V (терми-

нальный алфавит), A — конечный язык над V (аксиомы), R —

конечное множество пар p = (r, Q

), где r = u

—

правило сплетения над V , а Q

— регулярный язык над V .

Для x, y, z, w ∈ V

∗

и p = (r, Q

) из R пишем (x, y) |=

(z, w)

тогда и только тогда, когда (x, y) |=

(z, w) и z, w ∈ Q

(резуль-

таты соединения по правилу r принадлежат Q

Если в такой расширенной H-системе γ = (V, T, A, R) для

любых p

= (r

, Q

), p

= (r

, Q

) из R имеем Q

= Q

, то

скажем, что γ — система с глобальной мишенью. Если Q —

язык-мишень, общий для всех правил из R, то будем запи-

сывать систему в виде γ = (V, T, A, R

, Q), где R

состоит из

правил сплетения из R.

Как обычно, мы обозначаем через EH

([n], lt[m]), n, m > 1,

семейство языков, порожденных расширенными H-системами

с локальными мишенями, имеющими самое большее n аксиом

и правила сплетения, радиусом не больше m. В случае гло-

бальных ми шеней мы вместо lt пишем gt. Если никаких огра-

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

заменяем [n] или [m] на F IN.

Из определений следует

Лемма 8.7. EH

([n], gt[m])⊆EH

([n], lt[m]) при всех n, m>1.

Лемма 8.8. R E ⊆ EH

(F IN, gt[2]).

Доказательство. Возьмем грамматику G = (N, T, S, P ) типа 0

в нормальной форме Куроды. Обозначим через P

множество

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

— множество

неконтекстно-свободных правил из P . Предпол ожим, что пра-

вила в P пр онумерова ны. Обозначим U = N ∪ T ∪ {B}, где

B — некий новый символ. Построим расширенную H-систему

с глобальной мишенью γ = (V, T, A, R, Q), в которой

V = N ∪ T ∪ {B, X, X

, X

, Y, Y

, Z, Z

}

∪ {Y

| α ∈ U} ∪ {Z

| r ∈ P }

352 8. Универсальность и конечные H-системы

∪ {Y

| r : CD → EF ∈ P

A = {XBSY, ZY, XZ, ZY

, X

Z, Z

}

∪ {ZY

, X

αZ | α ∈ U}

∪ {Z

xY | r : C → x ∈ P

}

∪ {ZY

, Z

EF Y | r : CD → EF ∈ P

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

локальные языки-мишени для того, чтобы сделать работу γ

более наглядной, а Q будет объединением всех этих локальных

языков.

Имитация : 1. #CY $Z

#x, Q

1,r

= XU

∗

Y ∪ {Z

CY }

для r : C → x ∈ P

2. C#DY $Z#Y

, Q

2,r

= XU

∗

∪ {ZDY },

3. #CY

#E, Q

3,r

= XU

∗

Y ∪ {Z

}

для r : CD → EF ∈ P

Переброска : 4. #αY $Z#Y

, Q

4,α

= XU

∗

∪ {ZαY },

5. X

α#Z$X#, Q

5,α

= X

∗

∪ {XZ},

6. #Y

$Z#Y

, Q

6,α

= X

∗

∪ {ZY

}

для α ∈ U,

7. X

#Z$X

#, Q

= X

∗

∪ {X

Z},

8. #Y

$Z#Y, Q

= X

∗

Y ∪ {ZY

9. X#Z$X

#, Q

= XU

∗

Y ∪ {X

Z}.

Завершение : 10. #Z

$XB#, Q

= T

∗

Y ∪ {XBZ

11. #Y $Z

#, Q

= T

∗

∪ {Z

Y }.

Тогда

Q =

[

r∈P

1,r

∪

[

r∈P

2,r

∪ Q

3,r

)

∪

[

α∈U

4,α

∪ Q

5,α

∪ Q

6,α

) ∪

[

i=7

Работа системы γ основана на идее имитации и переброски,

уже использовавшейся выше в аналогичных ситуациях, с неко-

8.3. Языки-мишени 353

торыми дополнительными предосторожностями на этапе пере-

броски. Как и раньше, мы начнем с аксиомы XBSY и будем

на каждом шаге сплетать строку вида XwY (в которой символ

X может быть заменен на X

или X

, а символ Y — на Y

, Y

α ∈ U, или Y

, r ∈ P

) с некоторой аксиомой (каждое прави-

ло спл етения содержит вхождение символов Z, Z

или Z

для

r ∈ P ). Вместе с языком-мишенью эти контрольные символы

регулируют работу системы γ так, чтобы обеспечить имитацию

в γ всех корректных выводов из G и, наоборот, предотвратить

образование терминальных строк, не лежащих в L(G).

Исследуем, например, как происходит п еребро ска. Начав со

строки XwαY при w ∈ U

∗

, α ∈ U, и воспользовавшись прави-

лами из групп 4–9, получим:

(Xw|αY, Z|Y

) |=

4,α

(XwY

, ZαY ),

α|Z, X|wY

) |=

5,α

αwY

, XZ),

αw|Y

, Z|Y

) |=

6,α

αwY

, ZY

|Z, X

|αwY

) |=

αwY

, X

Z),

αw|Y

, Z|Y ) |=

αwY, ZY

(X|Z, X

|αwY ) |=

(XαwY, X

Z).

Мы получили строку Xα wY — циклическую перестанов-

ку начальной строки XwαY . Язык-мишень не содержит строк

вида X

для r ∈ P

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

αwY не может всту-

пить в соединение в соответствии с правилами группы 2. Ис-

пользование правила из группы 1 также не приведет к воз-

никновению лишних строк. Никакая другая строка, стоящая

на первом месте в указанных парах, не может участвоват ь в

сплетениях согласно имитирующим правилам из R. Анал огич -

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

с завершающими правилами: возникающие строки не попада-

ют в T

∗

Y ∪T

∗

∪{XBZ

, Z

Y }. Что же касается «побочного про-

дукта», строк ZαY, XZ, ZY

, X

Z, ZY

, X

Z, — часть из них —

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

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

которые не приводят к появлению незаконных терминальных

354 8. Универсальность и конечные H-системы

строк. Например, строка X

Z, не являющаяся аксиомой, может

сплетаться с X

|Z, X

|Z) |=

Z, X

Z),

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

и X

Z, и X

Z лежат в Q).

Таким образом, можно заключить что L(γ) = L(G).

Лемма 8.9. EH

(F IN, gt[m]) ⊆ EH

([1], gt[m]), m > 1.

Доказательство. Предположим, γ = (V, T, A, R, Q) — расши-

ренная H-система с глобальной мишенью, и A = {w

, . . . , w

n > 2. Построим H-систему с глобальной мишенью

= (V ∪ {c}, T, {w}, R

, Q

где w = cw

. . . cw

c, R

= R ∪ {#c$c#},

= Q ∪ {w

, w

c · · · cw

c, cw

c · · · cw

i−1

cw,

wcw

i+1

c · · · cw

| 1 6 i 6 n}.

Утверждается, что L(γ) = L(γ

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

зовавшись правилом #c$c#, мы сможем отделить от w каждую

аксиому w

из γ:

(|w, cw

c · · · cw

i−1

c|w

c . . . cw

|= (w

c · · · cw

c, cw

c · · · cw

i−1

cw),

|cw

i+1

c · · · cw

c, w|) |= (w

, wcw

i+1

c · · · cw

c).

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

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

−Q. Следовательно, они должны быть либо аксиомами из A,

либо строками, содержащими добавочные вхождения c, и, сле-

довательно, составленными из блоков w

, 1 6 i 6 n, зажатых

между символами c. Это гарантирует включение L(γ

) ⊆ L(γ).

Обратное включение очевидно.

Заметим, что радиус правил и з R

− R равен 1, и значит,

rad(R

) = rad(R).

Теорема 8.4. RE = EH

([1], gt[2]) = EH

([1], lt[2]).

8.3. Языки-мишени 355

Доказательство. Включение RE ⊆ EH

([1], gt[2]) следует из

лемм 8.9, 8.10. Включение EH

([1], gt[2]) ⊆ EH

([1], lt[2]) от-

мечалось в лемме 8.7, а включение EH

([1], lt[2]) ⊆ RE может

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

па 0, имитирующей расширенную H-систему с локальными ми-

шенями, или выведено из тезиса Черча–Тьюринга.

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

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

является в языках-мишенях. Однако оказывается, что доста-

точно использовать информаци ю, заключенную в начальных и

конечных символах строк, получающихся при сплетении. Это

возвращает нас к условиям в стиле разрешающих-запрещаю-

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

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

Мы можем сформулировать эти условия в стиле теории

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

Рассмотрим отображение, оценивающее кач ество (пригод-

ность, реактивность) строк, и потребуем, чтобы строки с

низкой степенью годности не использовались в последующих

сплетениях.

Здесь мы рассмотрим булево отображение годности (преди-

кат).

Расширенная H-система с отображением годности — это

структура

γ = (V, T, A, R, f),

в которой V — алфавит, T ⊆ V (терминальный алфавит), A —

конечное подмножество в V

∗

(аксиомы), R — конечное множе-

ство правил сплетения над V , f : V

∗

−→ {0, 1} — отображение

годности.

Сплетение двух строк x, y ∈ V

∗

в соответствии с правилом

из R определено, если только f(x) = 1, f(y) = 1. Язык, порож-

даемый γ, определяется как обычно. Через EH

([n], fit[m]),

n, m > 1 мы обозначаем семейство языков, порождаемых та-

кими системами с не более чем n аксиомами и радиусом, не

превосходящим m.

356 8. Универсальность и конечные H-системы

Взяв в качестве f : V

∗

−→ {0, 1} отображение принадлеж-

ности подмножеству A ∪ Q из расширенной H-системы с гло-

бальной мишенью γ = (V, T, A, R, Q), мы по лучим расширен-

ную H-систему с отображением годности γ

= (V, T, A, R, f ),

такую, что L(γ) = L(γ

): результат сплетения не может всту-

пать в новое сплетение, если не лежит в A ∪Q. Таким образом,

мы получаем

Следствие 8. 2. RE = EH

([1], fit[2]).

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

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

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

подобных отображений. Естественно, например, рассмотреть

локальное определение отображения годности. Скажем, ч то f :

∗

−→ {0, 1} локально определено, если f(αxβ) = f(αx

β) для

всех α, β ∈ V , x, x

∈ V

∗

(т. е. значение f (αxβ) зависит не от x,

а лишь от ограничивающих его символов α, β). Мы обозначаем

через EH

([n], fit

[m]), n, m > 1, семейство языков, порожден-

ных расширенными H-системами с локально определенными

отображениями годности, имеющими не более, чем n аксиом, и

радиус, не превосходящий m. Если на число аксиом или радиус

никаких ограничений не накладывается, [n], [m] заменяются на

F IN. Теперь из доказательства следствия 8.1, определяя f так,

чтобы захватить ограничения, вытекающие из условий разре-

шающих контекстов (там проверяются только концы сплетаю-

щих строк), мы получаем

Следствие 8. 3. RE=EH

([1], fit

F IN)=EH

(F IN, fit

[2]).

Заметим, что фактически мы имеем особую форму локаль-

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

крайних символов.

Хотя следствия 8.2 и 8.3 получаются простой переформули-

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

кажутся более подходящими с «прак тич еской» точки зрения:

для того, чтобы реализовать H-системы с отображением год-

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

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

8.4. Программируемые и развертывающиеся системы 357

щью недетерминированного неограниченного сплетения. Кро-

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

только концы строк.

8.4 Программируемые и развертывающиеся

системы

Методы регулирования, изложенные в предыдущих разделах,

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

пользование правил сплетения: в любой момент применимо лю-

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

щих н еки м условиям. Однако и сами п рави ла могут менять-

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

всех доступных в данный момент строк. И строки (молеку-

лы ДНК), и правила сплетения (рестрикционные ферменты и

лигазы) соответствуют химическим комплексам, помещенным

вместе в данном пространстве (клетке или пр оби рке), следова-

тельно, осуществляется двустороннее взаимодействие: не толь-

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

очередь влияют на правила сплетения.

В общей постановке для языка L ⊆ V

∗

и множества R пра-

вил сплетения над V мы определяем:

1. Язык String(R, L) всех строк, по лученн ых при однократном

сплетении строк из L по правилам из R, применяемым, воз-

можно, в ограниченной форме.

2. Множество Rule(R, L) правил сплетения над V , получае-

мых из правил R под влиянием строк из L.

Далее, начиная с языка L

⊆ V

∗

и множеств а R

правил

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

, L

) = (Rule(R

i−1

, L

i−1

), String(R

i−1

, L

i−1

)), i > 1.

Для расширенной H-системы (возможно, с контролем ctr

при применении ее правил) γ = (V, T, A, R, ctr) с помощью

отображения String, зависящего от ctr, можно определить по-

следовательность (R

, L

), i > 0, начинающуюся с L

= A,

358 8. Универсальность и конечные H-системы

= R . Тогда язык, порождаемый γ, задается равенством:

L(γ) = (

[

i>0

) ∩ T

∗

Такая система γ на зывается развертывающейся.

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

предыдущих разделах, свободное сплетение или сплетения с

различными ограничениями. В качестве вариантов можно рас-

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

шени или отображения годности. В этом разделе мы обсужда-

ем возможности, предоставляемые отображением Rule.

Можно считать, что множество Rule(R

i−1

, L

i−1

) зави сит не

от языка L

i−1

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

переходе от L

i−2

к L

i−1

= String(R

i−2

, L

i−2

). Можно предпола-

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

ких» им строк, которые и сами могут измениться благодаря

этим правилам. В данных предп оложениях можно опред елять

Rule(R

i−1

, L

i−1

) в манере разрешений или запрещений, в зави-

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

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

разрешений–запрещений, регулирующие сплетение.

Можно считать, что основной класс развертывающихся

H-систем базируется на отображениях Rule(R, L), зависящих

только от R и не зависящих от текущего множества строк.

Это немедленно пр иводит к рассмотрению H-систем, ана-

логичных изменяющимся во времени или программируемым

грамматикам в теории регулируемых переписывающих систем.

Мы о ткла дываем изучение изменяющихся во времени H-си-

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

механизмов обладает распред еленн ой архитектурой и заслужи-

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

ленными H-системами. В программируемом случае мы сно ва

сможем охарактеризовать семейство RE.

Программируемая расширенная H-система — это структура

γ = (V, T, A, R, ), где V — алфавит, T ⊆ V (терминальный

алфавит), A — конечный язык над V (аксиомы), R — конечное

8.4. Программируемые и развертывающиеся системы 359

множество правил сплетения над V , а — отображение из R в

множество P(R) подмножеств множества R.

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

L(γ) =



A ∪ σ

(A) ∪ ρ(A)



∩ T

∗

где σ = (V, R) — основная H-схема в γ и

(A) — множество

таких элементов w из V

∗

, что существует последовательность

сплетений вида

, y

) |=

, y

), (x

, y

) |=

, y

. . . (x

, y

) |=

k+1

, y

k+1

таких, что k > 2, r

∈ (r

i−1

), 2 6 i 6 k, y

∈ V

∗

, 2 6 i 6 k + 1,

, y

∈ A, y

∈ A, 2 6 i 6 k, и w = x

k+1

Другими словами, язык L(γ) содержит все терминальные

строки из A, а также те строки, которые могут быть полу-

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

из A (множество σ

(A)), либо путем нескольких сплетений со

следующими свойствами: при первом сплетаются аксиомы; на

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

произведенных на предыдущем шаге, и одна аксиома. Прави-

ла, применяемые на последовательных шагах, определяются с

помощью отображения .

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

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

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

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

разделах доказательств работает таким образом, когда след у-

ет «правильными» путями, приводящими к строкам из порож-

даемого языка. Однако в тех системах допускались и сплете-

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

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

явно сформулировать это требование к термам сплетения.

Как обыч но, мы обозначаем через EH

([n], pr[m]), n, m > 1,

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

ренными H-системами с не более чем n аксиомами и р адиусами,

360 8. Универсальность и конечные H-системы

не превосходящими m. Если n, m не ограничены, мы заменя-

ем [n], [m] на F IN.

Теорема 8.5. RE = EH

(F IN, pr[2]).

Доказательство. Мы должны доказать только включение

RE ⊆ EH

(F IN, pr[2]).

Рассмотрим грамматику G = (N, T, S, P ) типа 0 в нормаль-

ной форме Куроды. Обозначим через P

множество контекст-

но-свободных правил из P , а через P

— множество неконтекст-

но-свободных п рави л из P . Предположим, что правила из P

пронумерованы. Построим программируемую H-систему

γ = (V, T, A, R, ),

где

1) V = N ∪ T ∪ {X, X

, Y, B} ∪ {Y

| p ∈ P

} ∪ {Z

| p ∈ P },

2) A = {X

BSY, ZY, XZ} ∪ {Z

xY | p : C → x ∈ P

} ∪

{ZY

, Z

EF Y | p : CD → EF ∈ P

} ∪

{XαZ | α ∈ N ∪ T ∪ {B}},

3) R содержит следующие правила сплетения:

Начало : s

= X

#B$X#Z.

Имитация : s

= #CY $Z

для p : C → x ∈ P

1,p

= C#DY $Z#Y

2,p

= #CY

для p : CD → EF ∈ P

Переброска : r

1,α

= #αY $Z#Y,

2,α

= X#$Xα#Z

для α ∈ N ∪ T ∪ {B}.

Завершение : t

= XB#$#ZY,

= #Y $ZY #,

4) отображение определяется следующим образом:

) = {s

| p ∈ P

) = {s

| p

∈ P

}