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

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

6.4. Использование только вставки 271

Обозначим через M множество строк α#$ для α ∈ N ∪ T .

Каждой строке w ∈ M поставим в соответствие символ b

Пусть W — множество всех таких символов. Определим мор-

физм

h :



W ∪ T ∪ {c}



∗

−→



N ∪ T ∪ {#, $, c}



∗

следующим образом:

h(b

) = w, w ∈ M,

h(a) = a, a ∈ T,

h(c) = c.

Кроме того, рассмотрим слабое кодирование

g :



W ∪ T ∪ {c}



∗

−→ T

∗

определяемое как

g(b

) = λ, w ∈ M,

g(c) = λ,

g(a) = a, a ∈ T.

Получаем L(G) = g



−1



L(γ)





Смысл описанной выше конструкции состоит в следующем.

Правила вставки типа 1 моделируют контекстно свободные

правила из G, а правила типа 2 моделируют не контекстно сво-

бодные пр авил а из G. Правила типа 3 применяются для того,

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

ния правил типа 2. Это делается следующим образом.

Символы #, $ назовем метками. Будем называт ь нетерми-

нальный символ #-помеченным, если за ним следует символ #,

за которым стоит символ, отличный от $. Скажем, что нетер-

минальный символ $-помечен, если за ним следует символ $. И

наконец, скажем, что нетерминальный символ #$-помечен, ес-

ли за ним следует пара символов #$. Далее, #-, $-, или #$-по-

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

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

состоящую из непомеченных символов множества N ∪T ∪{c} и

из блоков α #$, в которых α ∈ N ∪ T , будем считать лега льной.

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

Например, c

(аксиома из γ) легальна, и строка

cX#$XaY #$c

тоже легальна. В последней строке первое вхождение X и сим-

вол Y помечены (точнее #$-помечены), тогда как второе вхо-

ждение X и все символы c и a непомечены. Напротив, строка

cX$XaY #$c

легальной не будет, поскольку первое вхождение символа X

является $-помеченным, а не #$-помеченным.

По правилам типа 3 можно переместить непомечен ный

нетерминальный символ X через блок X#$, расположенный

непосредственно справа от X. Таки м способом можно создать

пару XY , которая необходима для моделирования контекстно

зависимых правил из G.

Помеченные символы вместе с метками и символами c

можно считать «невидимым мусором». Подразумевается, что

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

ет сентенциальной форме в G. Действительно, по определению

h и g, этот «невидимый мусор» стирается из каждой легальной

строки, порожденной γ. Поскольку в образе h

−1

нет непоме-

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

терминальная строка.

Чтобы доказать р авенств о L(G) = g



−1



L(γ)





, сперва

покажем, что c помощью правил групп 1, 2, 3 из R можно

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

чение ⊆), затем покажем, что с помощью этих правил ничего

большего не добиться (т. е. верно и включение ⊇).

Утверждение 6.2. Перед применением правила

(α

X , λ/#$x, α

)

типа 1 вхождение символа X в обрабатываемой части строки

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

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

лов слова x.

6.4. Использование только вставки 273

Тот факт, что X не помечено в строке, к которой применя-

ется правило, подтверждается тем, что α

отлично от # и $.

Поскольку получается подстрока X#$xα

, очевид ны и осталь-

ные утверждения.

Утверждение 6.3. Перед применением группы правил (2.r.i),

1 6 i 6 3, ассоциированных с правилом r : XY → UZ из P ,

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

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

того, появляется непомеченные U Z.

В текущей строке подстрока, к которой применимо прави-

ло (2.r.1), имеет вид

XY α

где α

/∈ {#, $}, значит, X и Y не помечены. Затем возникает

строка

X$U ZY α

к которой применимо правило (2.r.2), приводящее к

X$U ZY #$α

Далее, по третьему правилу получается

X#$U ZY #$α

Видно, как третье прав ило завершает #$-помечивание симво-

ла X, а символ Y оказался #$-помечен еще на втором шаге.

Ясно, что U Z помеченными быть не могут. Таким образом, из

непомеченного блока XY получается подстрока с единствен-

ным непомеченным блоком U Z (если не обращать внимание

на подстроки α

и α

Утверждение 6.4. Применение правил третьей группы к ле-

гальной строке производит замену подстроки XY #$α (т. е.

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

N{#$} и оканчивающуюся на Xα (опять с непомеченным X).

Правило (3.XY.1) можно применить к строке

xα

XY #$α

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

Оно изготовит из нее строку

xα

XY #$X#α

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

xα

X#$Y #$X#α

Наконец, третье правило вырабатывает строку

xα

X#$Y #$X#$Xα

Следовательно, подстрока XY #$ оказалась замененной на

строку X#$Y #$X#$X, у которой в крайней правой позиции

стоит непомеченный символ X.

Таким образом, если работа начинается с легальной строки

(первоначально у нас c

), то правила из R могут смоделиро-

вать работу правил из G, вновь вырабатывая при этом легаль-

ную строку. Более того, если обозначить через umk(x) строку

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

то выполняется

Утверждение 6.5. (i) Если вывод x =⇒

∗

y выполнен при-

менением правила группы 1 или всех трех правил (2.r.i),

1 6 i 6 3, ассоциированных с не контекстно-свободным

правилом r из G, то вывод umk(x) =⇒ umk(y) выполня-

ется применением соответствующего правила из G.

(ii) Если вывод x =⇒

∗

y выполнен применением трех пра-

вил группы 3, ассоциированных с одними и теми же X, Y

из N, то umk(x) = umk(y).

Утверждение 6.6. Если x = g



−1

(y)



для некоторого y ∈

L(γ), то y — легальная строка и x = umk(y), y ∈ T

∗

. Обратно,

если y ∈ L(γ) и umk(y) ∈ T

∗

, то umk(y) = g



−1

(y)



Это утверждение непосред ственн о следует из определений

морфизмов g и h.

Эти утверждения доказывают включение

L(G) ⊆ g



−1



L(γ)





Покажем теперь, что лишь опи санн ые выше процессы вы-

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

6.4. Использование только вставки 275

Утверждение 6.7. После применения правила (2.r.1) с

нетерминальными символами X, Y , U, Z не может ра-

ботать никакое правило, кроме (2.r.2). А после (2.r.2) можно

применить только правило (2.r.3).

Действительно, рассмотрим подслово α

XY α

, ис-

пользуемое правилом (2.r.1) для r : XY → UZ ∈ P . После

применения (2.r.1) получаем α

X$U ZY α

. Теперь отме-

тим следующие факты:

1. Никакое правило типа (1.q) нельзя применить ни для какой

из четырех букв X, Y, U, Z из-за символов β

, 1 6 i 6 10 в

правилах (β

X , λ/#$x, β

) типа (1.q), q :

X → x ∈ P . (Например, β

/∈ N{$}N, значит, к букве Z

нельзя применить правило (1.q), соответствующее q : Z →

x ∈ P .)

2. Никакое правило (2.q.1) нельзя применить ни для пары

UZ, ни для пары ZY из-за символов β

в правилах

(β

X , λ/$Y Z, Uβ

) типа (2.q.1), ассоциированных с q :

XU → Y Z ∈ P .

3. Нельзя применить никакое правило (2.q.2), q 6= r. Это оче-

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

X$U ZY , которое однозначно выделяет правило r из P .

4. Нельзя применить никакое правило (2.q.3), поскольку дл я

этого необходима подстрока X$UZY #$, а появившаяся вы-

ше буква α

отлична от #.

5. Нельзя применить никакое правило (3.CD.1), поскольку на-

ша строка не содержит подстроки CD#$. По тем же сооб-

ражениям нельзя применить правила (3.CD.2) и (3.CD.3)

для любых C, D ∈ N.

Применив правило (2.r.2), получим строку

X$U ZY #$α

Ничего не изменилось ни слева от подстроки X$U ZY , ни внут-

ри нее. Более того, теперь символ Y стал #$-помеченным. Как

и прежде видно, что никакое правило, кроме (2.r.3), нельзя

применить к этой строке. Например:

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

1. Никакое правило (3.ZY.1) нельзя применить к паре ZY

(единственной паре, за которой следует #$), поскольку

слово β

в правиле этого типа (β

ZY #$, λ/Z#,

) не может совпадать с X$U .

2. Нельзя применить никакое правило (3.CD.2), поскольку в

нашей строке нет ни одного #-помеченного символа C. По

тем же соображениям нельзя применить правило (3.CD.3),

C, D ∈ N.

Утверждение 6.8. После применения правила (3.XY.1),

с нетерминальными символами X, Y не может работать

никакое правило, кроме (3.XY.2). А после (3.XY.2), можно

применить только правило (3.XY.3).

Правило (3.XY.1) заменяет подстроку α

XY #$α

на w = α

XY #$X#α

. Теперь отметим следующие

факты:

1. Никакое правило

(β

X , λ/#$x, β

)

типа (1.q) нельзя применить (X — единственный непо-

меченный символ в нашей строке) из-за того, что слово

не может совпадать с Y #$X#α

2. Нельзя применить никакое правило типа (2.q.1), поскольку

в w нет двух непомеченных символов.

3. Нельзя применить никакое правило типов (2.q.2) и (2.q.3),

поскольку в w нет ни одного $-помеченного символа.

4. Нельзя применить никакое правило (3.CD.1):

(β

CD#$, λ/c$, β

Единственная возможность применения правила (3.XY.1)

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

благодаря слову β

5. Нельзя применить никакое правило (3.CD.2), в котором

XY 6= CD, поскольку нет необходимых для него симво-

лов C и D.

6.4. Использование только вставки 277

6. Нельзя применить никакое правило (3.CD.3), посколь-

ку для него нужна подстрока вида $D#$C#, а такой

подстроки в w нет.

Следовательно, придется применить правило (3.XY.2).

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

X#$Y #$X#α

. Здесь нет непо-

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

видов (1.r), (2.q.1), (2.q.2), (2.q.3), (3.CD.1), (3.CD.2). Пра-

вило (3.CD.3) можно применить, если только XY = CD.

Утверждение 7 доказано.

Следовательно, нельзя смешивать правила из групп (1.r)

(для контекстно-свободных правил r из P ), (2.r.i), 1 6 i 6 3

(для не контекстно-свободных правил r из P ) и (3.XY.i), 1 6

i 6 3 (для X, Y ∈ N), а внутри этих групп необходимо при-

менять правила в порядке возрастания индекса i от 1 до 3.

Следовательно, система γ может лишь моделировать выводы

в G на непомеченных символах. Это означает, что если h

−1

определено на y ∈ L(γ), то c

=⇒

∗

umk(y) в грамматике G

и g



−1

(y)



∈ L(G), что доказывает включение



−1



L(γ)





⊆ L(G).

Отметим, что система γ имеет вес (4, 7; 0, 0) (4 достигается в

правилах типа (1.r), а 7 достигается в правилах типа (3.XY.1)).

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

следующим образом.

1. Запишем L =

a∈T

(∂

(L){a}) и для каждого языка ∂

(L)

рассмотрим грамматику G

= (N

, T, S

, P

). Будем счи-

тать, что алфавиты N

, a ∈ T попарно не пересекаются.

2. Работа начинается с множества аксиом {c

ca | a ∈ T }.

3. К правилам приведенной выше конструкции, ассоциирован-

ным с P

, a ∈ T , добавим правила с суффиксами-«свидете-

лями» типа α

. . . α

, оканчивающимися символом c. Напри-

мер, вместе с

(α

X , λ/#$x, α

) (1.r)

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

рассмотрим также правила, в которых α

за-

менено на

c для α

∈ {#, $},

c, для α

, α

∈ N ∪ { $},

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

в суффиксах которых есть символы α.

Эти укороченные правила можно применять к концу те-

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

торые порождают строки, не лежащие в языках ∂

(L).

4. Кроме того, позволим терминальным символам мигриро-

вать вправо по правилам третьей группы, т. е. разрешим в

правилах группы 3 символам X и Y быть терминальными,

а Y разрешим быть и буквой c.

5. Добавим следующие правила:

(ac, λ/#$a#, b), a, b ∈ T, (4.a.1)

(a, λ/#$, c#$a#b), a, b ∈ T, (4.a.2)

($c#$a#, λ/$ca, b), a, b ∈ T. (4.a.3)

Заметим, что при действии этих правил символ c становит-

ся #$-помеченным, и, кроме того, вместе с перемещенным

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

ный символ c. Шаг вывода имеет вид

xacbx

=⇒ xac#$a#bx

=⇒ xa#$c#$a#bx

=⇒ xa#$c#$a#$cabx

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

рядом с символом b.

6.4. Использование только вставки 279

6. Добавим еще правило

($c#$a#, λ/$da, b), a, b ∈ T, (4.a.4)

где d — новый символ, добавленный к алфавиту γ.

Правило (4.a.1) использует непомеченный символ c, а

если применить вместо (4.a.3) правило (4.a.4), то нового

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

(4.a.i) бол ьше нельзя будет применять. Следовательно, для

регулярного языка

= {α#$ | α ∈ (N ∪ T ∪ {c})

∗

}{d}

выполняется равенство L = L

\L(γ).

Действительно, это деление на L

слева выделяет из

L(γ) строки, содержащие символ d, перед которым стоят

только #$-помеченные символы. Это означает, что все

нетерминальные символы были заменены на терминаль-

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

что справа от d остались их копии.

Таким образом, получаем

Следствие 6.1. Каждый язык L ∈ RE можно представить в

виде L = L

, где L

— регулярный язык, а L

∈ INS

DEL

Вопрос, можно ли заменить здесь числа 4 и 7 на мень-

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

IN S

∗

DEL

⊆ CF и того факта, что семейство CF замкнуто

относительно обратных морфизмов и относительно произ-

вольных морфизмов, следует, что верхний индекс 7 нельзя

заменить ни на 0 ни на 1.

Можно сделать весьма интересное заключение о размерах

семейств IN S

DEL

Следствие 6.2. Каждое семейство INS

DEL

, n > 4, m >

7, не сравнимо ни с одним из семейств F L таким, что LIN ⊆

F L ⊂ RE, и FL замкнуто относительно слабых кодирований

и обратных морф измов или относительно левых делений на

регулярные языки.

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

Доказательство. Поскольку LIN − INS

∗

DEL

6= ∅, пол уча-

ем F L−IN S

∗

DEL

6= ∅. Так как F L, замкнутое относит ельно

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

ся в RE, включение IN S

DEL

⊆ F L не может выполняться.

(иначе RE ⊆ F L ⊂ RE, противоречие).

В качестве примеров семейств языков, обладающих свой-

ствами упомянутых выше семейств F L, можно привести се-

мейства MAT

и ET 0L.

6.5 Комментарии к библиографии

Системы вставки (без использования операций удаления)

впервые рассматривались в [1]. Такие системы исследовались

в [236, 237, 317]. Системы вставки и удаления были рассмотре-

ны в [162], после систематического изучения операций вставки

и удаления в [155] (где, однако, в основном рассматривались

комбинаторные свойства и свойства разрешимости нескольких

вариантов этих операций, а не основанные на них порож-

дающие механизмы). Теорема 6.1 взята из [210] (подобный

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

ством). Теоремы 6.2 и 6.7 взяты из [161]. Теорема 6.3 новая.

Теорема 6.4 основана на аналогичном доказательстве из [1].

Доказательство теоремы 6.8 основано на доказательстве из [80]

(где работа происходит не с системами вставки, а с контексту-

альными грамматиками). Теорема 6.10 и ее следствия взяты

из [210]. Более подробно с семействами IN S

DEL

можно

познакомится как по упомянутым выше статьям, так и по

монографии [249].

Обсуждения того, как операции вставки и удал ения появ-

ляются при работе с ДНК и РНК, можно най ти в [315] и соот-

ветственно в [23].