Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений
Подождите немного. Документ загружается.
4.5. Характеризации класса RE 181
обеспечивает то, что все вычисления в γ соответствуют кор-
ректным выводам в G. Завершить молекулу при вычислении
можно, использовав пары типов 3 или 4, в зависимости от чет-
ности шага. Это соответствует использованию S-правила из P ,
т. е. корректному началу вывода в G. Обратно, благодаря виду
правил из P , все выводы G можно смоделировать завершенны-
ми вычислениями из γ.
Ясно, что задержка γ равна 1 и никакое завершенное вычис-
ление в γ нельзя продолжить, следовательно, L
n
(γ) = L
1
(γ) =
L
p
(γ).
Определив слабое кодирование h как
h([X, a]
i
) = a для X ∈ N, i = 1, 2, 3, a ∈ T,
h([X, c]
i
) = λ для X ∈ N, i = 1, 2, 3,
очевидным образом получим, что h
L
n
(γ)
= L, завершая тем
самым доказательство.
Для произвольного семейства языков FL через CodW(FL)
обозначим семейство всевозможных языков вида h(L), где L —
язык из FL, а h — слабое кодирование.
Следствие 4. 8. CodW
SSL(b)
= LIN .
Доказательство. Включение SSL(b) ⊆ LIN следует из теоре-
мы 4.3. Семейство LIN замкнуто относительно произвольных
морфизмов, следовательно, CodW
SSL(b)
⊆ LIN . В преды-
дущей теореме доказано обратное включение.
4.5 Характеризации рекурсивно перечислимых
языков
С точки зрения молекулярных вычислений более интересна
возможность представления (а, значит, и характеризации)
рекурсивно перечислимых языков посредством склеивающих
языков. Мы уже упомянули такую возможность в конце разде-
ла 4.2. Там мы обсудили пример такой склеивающей системы
(обозначенной через γ
2
), что
h
L
n
(γ
2
)
= T S
V
,
182 4. Системы со склейкой
для некоторого слабого кодирования h. Комбинируя это с
теоремой 3.17 (слабое кодирование моделируется посредством
ОПМ), мы получаем следующий результат:
Теорема 4.10. Каждый язык L ∈ RE может быть пред-
ставлен в виде L = g(L
0
) для подходящих языка L
0
∈ ASL(n)
и детерминированного ОПМ-отображения g.
В силу результатов раздела 4.3 нельзя получить аналогич-
ное представление, в котором язык L
0
выбирался бы из одного
из семейств на рис. 4.5, отличных от ASL(n), ASL(p), SSL(n),
SSL(p), поскольку все остальные семейства состоят только
из линейных языков, а семейство LIN замкнуто относитель-
но произвольных ОПМ-отображений. Однако для семейства
SSL(n) — и даже для SSL(p) — имеет место результат о пред-
ставлении рекурсивно перечислимых языков, усиливающий
теорему 4.10.
Теорема 4.11. Каждый язык L ∈ RE может быть пред-
ставлен в виде L = h(L
0
) для подходящих языка L
0
∈ SSL(n) ∩
SSL(p) и слабого кодирования h.
Доказательство. Рассмотрим язык L ⊆ T
∗
, L ∈ RE. По теоре-
ме 3.16 существуют два λ-свободных морфизма h
1
, h
2
: V
∗
1
−→
V
∗
2
, регулярный язык R ⊆ V
∗
2
и проекция pr
T
: V
∗
2
−→ T
∗
для
T ⊆ V
2
, такие, что L = pr
T
h
1
EQ(h
1
, h
2
)
∩ R
.
Рассмотрим детерминированный конечный автомат M =
(K, V
2
, s
0
, F, δ), распознающий язык R.
Построим простую склеивающую систему
γ = (V, ρ, A, D),
в которой
(A) V = V
2
∪
V
2
∪ K ∪ {$, E, E
0
, C, Z},
(B) ρ = {(X, X) | X ∈ V },
(C) A =
n
s
0
λ
h
$
$
i
Z
λ
o
и
(D) D состоит из следующих пар домино:
1. Для каждого a ∈ V
1
такого, что h
1
(a) = b
1
. . . b
k
, k > 1,
и h
2
(a) = c
1
. . . c
m
, m > 1, где b
1
, . . . , b
k
, c
1
, . . . , c
m
∈ V
2
,
4.5. Характеризации класса RE 183
и для s
i
j
∈ K, 0 6 j 6 m, такого, что δ(s
i
j
, c
i
) = s
i
j+1
,
0 6 j 6 m, поместим в D пару
(
s
i
m
¯c
m
s
i
m−1
. . . s
i
2
¯c
2
s
i
1
s
i
1
¯c
1
s
i
0
λ
,
b
1
CZb
2
CZ . . . CZb
k
CZ
λ
).
(Слева от
h
$
$
i
строится развернутый образ некоторого
h
2
(a) для a ∈ V
1
, и одновременно запомин ается путь
движения по автомату M при чтении слова h
2
(a):
s
i
0
c
1
c
2
. . . c
m
=⇒
∗
s
i
m
. Справа строится образ a при h
1
,
причем символы h
1
(a) разделяются вспомогательными
символами CZ.)
2. (
E
0
s
f
λ
,
E
λ
) для s
f
∈ F . (Это п озвол ит установить
связь между принятием слова автоматом M и заверше-
нием построения левой части верхней строки.)
3. (
λ
ss
,
λ
Z
) для каждого s ∈ K. (Эти пары домино
проверяют корректность распознавания пути через ав-
томат M на стыках домино из первой группы. Если за
s
1
x =⇒
∗
xs
2
следует s
3
y =⇒
∗
ys
4
, то s
2
и s
3
должны
совпадать, в противном случае не будет комплементар-
ности после приклеивания блока
λ
ss
.)
4. (
λ
¯
b
,
λ
bC
), где b ∈ V
2
. (Проверяется соответствие
строки символов
¯
b, записанных в верхней нити слева
от
h
$
$
i
, строке символов b, записанных в верхней нити
справа от
h
$
$
i
. Заметим, что символы Z «поглощаются»
вместе с парами состояний из-за вида пар домино тре-
тьей группы. А теперь также «поглотятся» и символы
C, записанные в верхней строке справа от
h
$
$
i
.)
5. (
λ
E
0
,
λ
E
). (Только таким образом может быть завер-
шено построение молекулы.)
184 4. Системы со склейкой
Из приведенных выше объяснений можно понять, чт о каж-
дая построенная системой γ завершенная молекула имеет вид
E
0
s
f
s
f
¯c
t
s
t
s
t
. . . ¯c
2
s
1
s
1
¯c
1
s
0
s
0
E
0
s
f
s
f
¯c
t
s
t
s
t
. . . ¯c
2
s
1
s
1
¯c
1
s
0
s
0
$
$
Zb
1
CZb
2
CZ . . . CZb
t
CZE
Zb
1
CZb
2
CZ . . . CZb
t
CZE
,
где c
1
c
2
. . . c
t
= h
1
(w) = h
2
(w) = b
1
b
2
. . . b
t
для некоторого w ∈
V
∗
1
, и вдобавок s
0
c
1
. . . c
t
=⇒
∗
c
1
. . . c
t
s
f
в автомате M для s
f
∈
F , т. е. h
1
(w) ∈ R.
Никакое завершенное вычислен ие не может быть продол-
жено, поскольку верхние цепочки левых домино (в группах 1
и 2) имеют на правом конце цепочки только одну букву из K,
тогда как каждая нижняя нить лево й домино (в группах 3,
4, 5) либо состоит из двух таких букв подряд, либо вообще их
не содержит. Следовательно, L
n
(γ) = L
p
(γ).
Теперь рассмотрим слабое кодирование (точнее проекцию)
h, определяемую как
h(a) = a для a ∈ T,
h(¯a) = λ для a ∈ T,
h(s) = λ для s ∈ Q,
h(E) = h(E
0
) = h($) = h(C) = h(Z) = λ.
Ясно, что L = h
L
n
(γ)
, что и завершает доказательство.
Приведенная выше конструкция имеет интересное след-
ствие в классической теории формальных языков, а именно,
можно усилить результат следствия 3.3.
Следствие 4.9. Каждый рекурсивно перечислимый язык яв-
ляется проекцией пересечения двух минимальных линейных
языков.
Доказательство. Сохраняя обозначения из предыдущего до-
казательства, построим две минимальных линейных грамма-
тики G
i
= ({S}, V, S, P
i
), i = 1, 2, в которых
1. P
1
= {S → s
i
m
¯c
m
s
i
m
s
i
m
. . . s
i
2
¯c
2
s
i
1
s
i
1
¯c
1
s
i
1
Sb
1
CZb
2
C
. . . Zb
k
CZ | для b
1
. . . b
k
= h
1
(a), c
1
. . . c
m
= h
2
(a) для неко-
торых m > 1, a ∈ V
1
, и δ(s
i
j
, c
j
) = s
i
j+1
, 0 6 j 6 m − 1, где
b
1
, . . . , b
k
, c
1
, . . . , c
m
∈ V
2
} ∪ {S → E
0
s
f
SE | s
f
∈ F } ∪ {S →
s
0
$Z
,
4.6. Дальнейшие результаты о регулярных системах 185
2. P
2
= {S → ssSZ | s ∈ Q} ∪ {S →
¯
bSbC | b ∈ V
2
} ∪ {S →
E
0
SE, S → $}.
Легко видеть, что G
1
порождает строки верхних нитей, по-
строенных системой γ при использо вани и только пар из первой
и второй группы плюс центральная подстрока s
0
$Z, тогда как
G
2
порождает строк и нижних нитей, построенных системой γ
при использовании только пар из групп 3, 4 и 5 плюс ц ентр аль-
ная подстрока $. Взятие пересечения эквивалентно проверке
отношения комплементарности ρ, поскольку это просто отно-
шение равенства. Следовательно, L(G
1
) ∩ L(G
2
) = L
n
(γ), что
и завершает доказательство.
4.6 Дальнейшие результаты
о регулярных системах
Регулярные склеивающие системы порождают только регуляр-
ные языки, и следовательно, из них нельзя получить семейство
RE с использованием AFL-операций в качестве сжимающих
механизмов. С другой стороны, именно простые варианты та-
ких устройств особенно привлекательны и с математической, и
с биохимической точек зрения. Например, использование пар
домино, на которое существенным образом опиралось доказа-
тельство теоремы 4.11, не очень реалистично с практической
точки зрения. К процессу ренатурации, происходящему в про-
бирке, ближе использование отдельных домино, в силу чего
неоднократно выдвигалась и обсуждалась идея «самосборки»
вычислений. Встает важный вопрос о модификации определе-
ния простых склеивающих систем или задаваемых ими языков
таким образом, чтобы получить характеризации рекурсивно
перечислимых языков с помощью таких склеивающих систем.
Рассмотрим здесь два ограничения на язык, порожденный
простой регулярной склеивающей системой.
Поскольку мы работаем только с правостронними п арами
домино, мы можем забыть про их левый элемент, который все
равно пуст. Кроме того, разделим все домино на «верхние»
и «нижние». Тем самым мы представим простую регулярную
186 4. Системы со склейкой
склеивающую систему в виде
γ = (V, ρ, A, D
l
, D
u
),
где
1. V, ρ, A те же, что и ранее, а
2. D
l
⊆
λ
V
∗
, D
u
⊆
V
∗
λ
, причем множества D
l
и D
u
конеч-
ны.
Языки L
α
(γ) определяются также, как и в предыдущих разде-
лах для α ∈ {n, b, p}.
Рассмотрим два помечивания элементов из D
l
, D
u
элемен-
тами множества Lab, e
π
: D
π
−→ Lab, π ∈ {l, u}. Для завер-
шенного вычисления σ : x
1
=⇒ x
2
=⇒ . . . =⇒ x
k
в системе γ
определим контрольные слова e
π
(σ), π ∈ {l , u}, состоящие из
меток использованных в σ элементов из D
l
, D
u
, соответствен-
но. Формально говоря, для π ∈ {l, u} обозначим
δ(π, x =⇒ y) = e
π
(
w
1
w
2
), если на шаге x =⇒ y использовано
домино
w
1
w
2
∈ D
π
,
δ(π, x =⇒ y) = λ в противном случае.
Далее,
e
π
(σ) = δ(π, x
1
=⇒ x
2
)δ(π, x
2
=⇒ x
3
)
. . . δ(π, x
k−1
=⇒ x
k
), π ∈ {l, u}.
Скажем, что завершенное вычисление σ : x
1
=⇒
∗
x
k
, x
1
∈ A
является
чистым, если |e
l
(σ)| = |e
u
(σ)|,
связным, если e
l
(σ) = e
u
(σ).
В чистом вычислении используется одинаковое количество
верхних (из D
u
) и нижних (из D
l
) блоков. В связном вычис-
лении требуется, чтобы совпадали две последовательности из
меток, ассоциированн ых с верхними и нижними использован-
ными в вычислении блоками. Разумеется, каждое связное вы-
числение является чистым.
4.6. Дальнейшие результаты о регулярных системах 187
Обозначим через L
f
(γ), L
c
(γ) языки (состоящие из строк,
расположенных в верхних нитях молек ул из LM
n
(γ)), порож-
денные системой γ с применени ем только чистых вычислений
или только связных вычислений, соответственно. Получившие-
ся семейства языков обозначим через SRSL(f ), SRSL(c). Когда
кроме этого вычисления еще и примитивны, заменим в этих
обозначениях f и c на pf, pc, соответственно.
Условие связности снова приводит к представлению рекур-
сивно перечислимых языков.
Теорема 4.12. Каждый рекурсивно перечислимый язык яв-
ляется слабым кодированием языка из семейства SRSL(c)
или SRSL(pc).
Доказательство. Рассмотрим язык L ∈ RE , L ⊆ T
∗
. По тео-
реме 3.16 найдутся два алфавита V
1
и V
2
такие, что T ⊆ V
2
, два
λ-свободных морфизма h
1
, h
2
: V
∗
1
−→ V
∗
2
и такой регулярный
язык R ⊆ V
∗
2
, что L = pr
T
h
1
EQ(h
1
, h
2
)
∩ R
.
Допустим, что V
1
= {b
0
, b
1
, . . . , b
n−1
}, n > 1. Рассмотрим де-
терминированный конечный автомат M = (K, V
2
, s
0
, F, δ), рас-
познающий язык R. Пусть в нем K = {s
0
, s
1
, . . . , s
m−1
} для
некоторого m > 1.
Построим склеивающую систему
γ = (V, ρ, A, D
l
, D
u
),
в которой
1. V = V
2
∪ K ∪ {¯s | s ∈ F } ∪ {[s, j] | s ∈ K, 0 6 j 6 m − 1},
2. ρ = {(X, X) | X ∈ V
2
} ∪ {(s, s), ([s, j], s), (s, [s, k]),
([s, j], [s, k]) | s ∈ K, 0 6 j, k 6 m − 1} ∪ {(¯s, ¯s) | s ∈ F},
3. A = {
h
s
0
s
0
i
s
0
λ
},
4. D
l
= {
λ
[s
l
0
,j]a
1
s
l
1
s
l
1
a
2
s
l
2
s
l
2
...s
l
t
i
−1
s
l
t
i
−1
a
t
i
s
l
t
i
| a
1
a
2
. . . a
t
i
=
h
2
(b
i
), 0 6 i 6 n − 1, 0 6 j 6 m − 1, δ(s
l
k
, a
k+1
) = s
l
k+1
,
0 6 l
k
6 m − 1, 0 6 k < t
i
} ∪ {
λ
s
l
¯s
l
| s
l
∈ F },
188 4. Системы со склейкой
5. D
u
= {
a
1
[s
l
1
,j]s
l
1
a
2
s
l
2
s
l
2
...a
t
i
s
l
t
i
s
l
t
i
λ
| a
1
a
2
. . . a
t
i
= h
1
(b
i
), 0 6
i 6 n − 1, 0 6 j 6 m − 1, δ(s
l
k
, a
k+1
) = s
l
k+1
, 0 6 l
k
6
m − 1, 1 6 k < t
i
} ∪ {
¯s
l
λ
| s
l
∈ F }.
Для каждой тройки чисел 0 6 i 6 n − 1, 0 6 j, k 6 m − 1
обозначим через r
l
(i, j, k) элемент из D
l
, ассоциированный с
h
2
(b
i
), как показано выше, и имеющий в качестве первого сим-
вола нижней нити пару из состояния s
j
и числа k. Последова-
тельность
λ
s
j
¯s
j
из D
l
обозначим ч ерез r
l
(n, 0, j). Подобным
же образом для каждой тройки чисел 0 6 i 6 n − 1, 0 6 j,
k 6 m − 1 обозначим через r
u
(i, j, k) элемент из D
u
, ассоции-
рованный с h
1
(b
i
) как показано выше, и имеющий в качестве
первого символа нижней нити пару из состояния s
j
и числа k.
Последовательность
λ
s
j
¯s
j
из D
u
обозначим через r
u
(n, 0, j).
Ясно, что card(D
l
) = card(D
u
) = n·m
2
+card(F ). Определим
помечивания
e
l
: D
l
−→ {1, 2, . . . , card(D
l
)},
e
u
: D
u
−→ {1, 2, . . . , card(D
u
)}
поэлементно
r
d
(i, j, k)
= i · m
2
+ j · m + k + 1,
r
u
(i, j, k)
= i · m
2
+ k · m + j + 1.
Из приведенной выше конструкции легко увидеть, что u =⇒
∗
z
тогда и только тогда является завершенным вычислением в
γ, u ∈ A, когда существует такая последовательность
s
l
0
a
1
s
l
1
a
2
. . . s
l
t−1
a
t
s
l
t
,
что, во-первых, s
l
0
= s
0
, s
l
t
∈ F , a
k
∈ V
2
, и δ(s
l
k−1
, a
k
) = s
l
k
,
1 6 k 6 t, во-вторых, есть такое слово x ∈ V
∗
, что h
1
(x) =
h
2
(x) = a
1
a
2
. . . a
t
.
Теперь определим слабое кодирование h : WK
ρ
(V ) → T
∗
как
h(
X
X
) =
(
X , если X ∈ T,
λ, в противном случае,
4.6. Дальнейшие результаты о регулярных системах 189
h(
[s, j]
[s, k]
) = h(
s
[s, k]
) = h(
[s, j]
s
) = λ
для s ∈ K, 0 6 j, k 6 m − 1.
Проверим равен ство h
L
c
(γ)
= pr
T
h
1
EQ(h
1
, h
2
)
∩ R
.
(⊆). Пусть w ∈ h
L
c
(γ)
. Тогда найдется такой элемент
z ∈ WK
ρ
(V ), что w = h(z), и найдется вычисление в γ вида
σ : x =⇒
∗
z, x ∈ A, c
d
(σ) = c
u
(σ). После описания конструкции
γ отмечено, что есть такая последовательность
s
l
0
a
1
s
l
1
a
2
. . . s
l
t−1
a
t
s
l
t
,
в которой s
l
0
= s
0
, s
l
t
∈ F , δ(s
l
k−1
, a
k
) = s
l
k
, 1 6 k 6 t. Следова-
тельно, a
1
a
2
. . . a
t
∈ R. Из определени я D
l
и D
u
и того факта,
что e
l
(σ) = e
u
(σ), следует равенство a
1
a
2
. . . a
t
= h
1
(y) = h
2
(y)
для некоторого y ∈ V
∗
1
. Тогда a
1
a
2
. . . a
t
∈ h
1
EQ(h
1
, h
2
)
∩ R.
Ну и поскольку w = h(z) = pr
T
(a
1
a
2
. . . a
t
), получаем w ∈
pr
T
h
1
EQ(h
1
, h
2
)
∩ R
.
(⊇). Пусть w ∈ pr
T
h
1
EQ(h
1
, h
2
)
∩R
. Тогда существуют
такие x = b
i
1
b
i
2
. . . b
i
s
∈ EQ(h
1
, h
2
) и y = h
1
(x) = h
2
(x), что
y ∈ R и w = pr
T
(y). Пусть y = a
1
a
2
. . . a
t
, a
i
∈ V
2
, 1 6 i 6 t.
Кроме того, имеется такая последовательность
s
j
1
, s
j
2
, . . . , s
j
t+1
состояний из K, что s
j
1
= s
0
, s
j
t+1
∈ F и δ(s
j
k
, a
k
) = s
j
k+1
,
1 6 k 6 t. Заметим, что h
1
(x) = h
1
(b
i
1
) . . . h
1
(b
i
s
) = a
1
a
2
. . . a
t
.
Пусть h
1
(b
i
k
) = a
q
k
. . . a
q
k+1
−1
, 1 6 k < s, и h
1
(b
i
s
) = a
q
s
. . . a
t
.
Аналогично, пусть h
2
(b
i
k
) = a
p
k
. . . a
p
k+1
−1
, 1 6 k < s, и
h
2
(b
i
s
) = a
p
s
. . . a
t
. Тогда найдется вычисление σ, использую-
щее следующие блоки из D
l
:
r
l
(i
1
, j
p
1
, j
q
1
+1
), . . . , r
l
(i
s
, j
p
s
, j
q
s
+1
), r
l
(n, 0, i
t
),
и следующие блоки из D
u
:
r
u
(i
1
, j
q
1
+1
, j
p
1
), . . . , r
u
(i
s
, j
q
s
+1
, j
p
s
), r
u
(n, i
t
, 0).
Обозначим результат этого вычисления через z. По определе-
нию h получим w = h(z). Легко видеть, что e
l
(σ) = e
u
(σ),
следовательно, w ∈ h
L
c
(γ)
.
190 4. Системы со склейкой
Завершенное вычисление в γ невозможно продолжить, по-
скольку в любой паре блоков из D
l
и из D
u
первые символы не
будут комплементарны в смысле отношения ρ. Следовательно,
L
c
(γ) = L
pc
(γ), что и завершает доказательство.
В случае чистых вычислений мы получим нерегулярные
языки, но не получим характеризации рекурсивно перечисли-
мых языков.
Следующий результат мы получим, немного изменив кон-
струкцию из доказательства теоремы 4.8.
Следствие 4.10. Каждый регулярный язык является коди-
рованием языка из семейства SRSL(f ).
Доказательство. Для регулярной грамматики G = (N, T,
S, P ) построим простую регулярную склеивающую систему
γ = (V, ρ, A, D
l
, D
u
), в которой
1. V и ρ те же, что и в доказательстве теоремы 4.8,
2. D
l
состоит из таких домино
λ
y
, что (
λ
λ
,
λ
y
) ∈ D, а
3. D
u
состоит из таких домино
y
λ
, что (
λ
λ
,
y
λ
) ∈ D, где
D как в доказательстве теоремы 4.8, и кроме того
4. A = {
h
[S,a]
1
[S,a]
1
i
λ
[X,b]
2
| S → aX ∈ P , X → bY ∈ P ,
X , Y ∈ N, a, b ∈ T }
∪ {
h
[S,a]
1
[X,b]
2
[S,a]
1
[X,b]
2
i
λ
[Y,c]
1
| S → aX ∈ P , X → bY ∈ P ,
Y → cZ ∈ P , X, Y, Z ∈ N, a, b, c ∈ T }
∪ {
h
[S,a]
1
[S,a]
1
i
| S → a ∈ P , a ∈ T } ∪
{
h
[S,a]
1
[X,b]
2
[S,a]
1
[X,b]
2
i
| S → aX ∈ P , X → b ∈ P , X ∈ N, a, b ∈ T }
∪ {
h
[S,a]
1
[X,b]
2
[Y,c]
1
[S,a]
1
[X,b]
2
[Y,c]
1
i
| S → aX ∈ P, X → bY ∈ P , Y → c ∈ P ,
X , Y ∈ N, a, b, c ∈ T }.
Легко видеть, что у каждой строки из L(G) есть чистое
вычисление в γ. Действительно, можно выбрать из A ту ак-
сиому, которая гарантирует, что на последнем шаге будет ис-
пользован элемент из D
l
, тогда число блоков, присоединен-
ных к обеим цепочкам, будет одинаковым. Затем с помощью