Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений
Подождите немного. Документ загружается.
4.6. Дальнейшие результаты о регулярных системах 191
кодирования h, взятого из доказательства теоремы 4. 8, полу-
чим L(G) = h
L
f
(γ)
.
С другой стороны, даже наложив условие чистоты, мы мо-
жем получать нерегулярные языки.
Теорема 4.13. SRSL(f) − REG 6= ∅.
Доказательство. Рассмотрим склеивающую систему
γ = ({a, b}, {(a, a), (b, b)}, A, D
l
, D
u
),
A = {
h
a
a
i
a
λ
},
D
l
= {
λ
a
,
λ
bb
},
D
u
= {
aa
λ
,
b
λ
}.
Аксиома только одна. Если использовать домино
λ
a
, то по-
лучим не чистое завершенное вычисление. Его можно продол-
жить любым элементом из D
l
и D
u
. В силу отношения компле-
ментарности (под которым здесь понимается равенство), после
каждого появления символа b возникает продолжение из доми-
но
λ
bb
и
b
λ
снова до появления прямого конца.
Если пересечь язык L
f
(γ) с регулярным языком a
+
b
+
, то
получится язык, состоящий из всех строк вида a
2n+2
b
m
, где
n > 0, m > 1, построенных при вычислениях, в которых
1) первый элемент из D
l
использовался 2n + 1 раз,
2) второй элемент из D
l
использовался m/2 раз,
3) первый элемент из D
u
использовался n раз,
4) второй элемент из D
u
использовался m раз.
Поскольку m/2 целое, запишем m = 2k, k > 1. Используя усло-
вие чистоты, получим 2n + 1 + k = n + 2k, ч то эквивалент-
но n = k − 1.
Язык L
f
(γ) ∩ a
+
b
+
= {a
2k
b
2k
| k > 1} не регулярен, следо-
вательно и L
f
(γ) тоже не регулярен.
Теорема 4.14. SRSL(f) ⊆ MAT
λ
.
192 4. Системы со склейкой
Доказательство. Рассмотрим склеивающую систему γ =
(V, ρ, A, D
l
, D
u
). Определим
1. V
0
= {a
0
| a ∈ V },
2. L(A) = {[a
1
, b
0
1
] . . . [a
k
, b
0
k
]a
k+1
. . . a
k+r
| k > 1, r > 0,
h
a
1
...a
k
b
1
...b
k
i
a
k+1
...a
k+r
λ
∈ A, a
i
, b
i
∈ V для всех i}
∪ {[a
1
, b
0
1
] . . . [a
k
, b
0
k
]b
0
k+1
. . . b
0
k+r
| k > 1, r > 0,
h
a
1
...a
k
b
1
...b
k
i
λ
b
k+1
...b
k+r
∈ A, a
i
, b
i
∈ V для всех i},
3. L(D
l
) = {b
0
1
. . . b
0
k
| k > 1,
λ
b
1
...b
k
∈ D
l
, b
i
∈ V , 1 6 i 6 k},
4. L(D
u
) = {a
1
. . . a
k
| k > 1,
a
1
...a
k
λ
∈ D
u
, a
i
∈ V , 1 6 i 6 k}.
Введем новые символы s, d, d
0
и построим языки
L
1
= {xd
0
| x ∈ L(D
l
)}
+
,
L
2
= {xd | x ∈ L(D
u
)}
+
,
L
0
1
= L
1
t⊥ c
+
,
L
0
2
= L
2
t⊥ c
+
,
L
3
= (L(A)L
0
1
t⊥ L
0
2
) ∩ {[a, b
0
] | a, b ∈ V }
∗
(V V
0
∪ {cd
0
, dc})
∗
.
Ясно, что L
1
, L
2
— регулярные языки, следовательно, и L
3
тоже
регулярный, поскольку семейство REG замкнуто относительно
операций перетасовки и пересечения языков.
Рассмотрим ОПМ g, которая:
1) оставляет символы [a, b
0
] без изменений, a, b ∈ V ,
2) заменяет каждую па ру ab
0
на [a, b
0
], a, b ∈ V,
3) заменяет каждую пару cd
0
на [c, d
0
] и каждую пару dc
на [d, c].
Язык g(L
3
) в алфавите U = {[a, b
0
] | a, b ∈ V } ∪ {[c, d
0
], [d, c]}
тоже регулярен.
Пусть G = (N, U, S, P ) — регулярная грамматика, задаю-
щая g(L
3
). Построим матричную грамматику
G
0
= (N
0
, V, S
0
, M),
в которой
1. N
0
= N ∪ U ∪ {S
0
},
4.7. Комментарии к библиографии 193
2. M = {(S
0
→ S)} ∪ {(r) | r ∈ P } ∪ {([a, b
0
] → a) | a, b ∈ V }
∪ {([c, d
0
] → λ, [d, c] → λ)}.
Легко видеть, что L(G
0
) состоит из всех таких строк w ∈ V
∗
,
что
u
1
u
2
h
x
1
x
2
i
v
1
v
2
=⇒
∗
w
w
0
в γ,
u
1
u
2
h
x
1
x
2
i
v
1
v
2
∈ A, причем
этот вывод чистый, поскольку матрица ([c, d
0
] → λ, [d, c] → λ)
проверяет, совпадают ли количества символов d и d
0
.
Следовательно, L
f
(γ) ∈ MAT
λ
.
Поскольку семейство MAT
λ
строго содержится в RE и за-
мкнуто относи тельн о произвольных ОПМ-отображений, невоз-
можно получить характеризации RE на основе языков из се-
мейства SRSL(f) с использованием кодирований, морфизмов
или ОПМ-отображений в качестве сжимающих механизмов.
Проблема. Содержится ли семейство SRSL(f) в CF (или в
LIN )?
4.7 Комментарии к библиографии
Системы со склейкой были введены в [159], где изучались про-
стые регулярные системы. Кроме того, в [159] рассмотрены
примитивные, сбалансированные, связные и чистые вычисле-
ния. Из этой статьи взяты результаты раздела 4.6; в ней со-
держатся также результаты, сходные с теоремой 4.1, следстви-
ем 4.1 и теоремами 4.4 и 4.8, но несколько более сла бые. Про-
стые системы со склейкой, удлиняющие цепочки в обе сторо-
ны, введены в [97]. В той же статье введено понятие огра-
ниченной задержки и получены равенства ASL(b) = LIN и
OSL(b) = REG. Теорема 4.11 и следствие 4.9 также взяты
из [97].
Общие системы со склейкой (использующие домино произ-
вольной формы) исследовались в [256], где результаты, не упо-
мянутые в предыдущем абзаце, появляются сразу в общности,
принятой также в данной главе.
Глава 5
Автоматы Уотсона–Крика
В этой главе и сследуются автоматы, соответствующие ск леи-
вающим системам из предыдущей главы. Мы рассмотрим но-
вую разновидность автоматов, работающих со сдвоенной лен-
той, на которой записываются двойные цепочки комплемен-
тарных символов, подобные молекулам ДНК (такая структура
данных называется лентой Уотсона–Крика). Автомат читает
каждую из двух дорожек ленты по отдельности, но в то же вре-
мя координирует процесс чтения. Кроме того, он может иметь
конечное число состояний для контроля за передвижениями
головки и/или вспомогательную память в виде еще одной лен-
ты Уотсона– Крика с доступом по типу очереди. Комбинируя
эти возможности, мы получаем несколько типов автоматов. В
большинстве случаев, дополняя эти автоматы такими сжима-
ющими механизмами, как слабые кодирования и детермини-
рованные последовательные преобразователи, мы приходим к
характеризации рекурсивно перечислимых языков.
Отметим существенное отличие ра ссматрив аемых здесь ав-
томатов от обычных, состоящее в структурах данных, с кото-
рыми они оперируют. Обычные автоматы работают с одномер-
ными строками символов, а наши ав томаты работают с двой-
ными строками. Эти двой ные строки подобны молекулам ДНК
в следующем смысле. Парные буквы (подобно нуклеотидам)
комплементарны, причем отношение комплементарности раз-
бивает буквы основного алфавита на пар ы, подобно компле-
ментарным по Уотсона–Крика парам (А, Т) и (Г, Ц) из ал-
фавита ДНК. Наиболее важно предположение о том, что та-
кие структуры данных — двойные строки, удовлетворяющие
упомянутому условию комплементарности, — предоставляют-
ся нам «даром» в том смысле, что нам не нужно проверять,
5.1. Конечные автоматы Уотсона–Крика 195
что отвечающие друг другу буквы действительно комплемен-
тарны.
В силу условия комплементарности такие автоматы назы-
вают автоматами Уотсона–Крика. Наиболее интересен основ-
ной вариант, при котором автомат читает каждую из двух до-
рожек ленты по отдельности, координи руя процесс чтения. Од-
нако мы исследуем и другие варианты, такие как преобразова-
тели и автоматы со вспомогательной лентой.
Автоматы Уотсона–Крика используют лишь один из двух
существенных «вычислительных козырей» молекул ДНК, а
именно, комплементарность Уотсона–Крика (что дает порож-
дающую силу языка перетасованных копий), но не многочис-
ленность молекул ДНК, вносящую в выч ислен ия массирован-
ный параллелизм. Пока остаются открытыми как проблема
моделирования этого второго аспекта, так и проблема постро-
ения модели молекулярных вычислений, учитывающей оба
названных преимущества молекул ДНК.
5.1 Конечные автоматы Уотсона–Крика
Определим один из кл ассов автоматов, анонсированных выше.
Эти автоматы соответствуют обычным конечным автоматам
(они используют состояния для контроля за переходами, как
это принято в теории автоматов), но о тличаются тем, что рабо-
тают на лентах Уотсона–Крика, т. е., на элементах множества
WK
ρ
(V ) для некоторого алфавита V и отношения комплемен-
тарности на нем ρ ⊆ V × V . (Используются обозначения, вве-
денные в предыдущей главе.)
Конечный автомат Уотсона–Крика представляет собой
конструкцию
M = (V, ρ, K, s
0
, F, δ),
в которой V и K — непересекающиеся алфавиты, ρ ⊆ V × V —
симметричное отношение, s
0
∈ K, F ⊆ K, δ : K ×
V
∗
V
∗
−→
P(K) — такое отображение, что δ(s,
x
y
) 6= ∅ лишь для ко-
нечного числа троек (s, x, y) ∈ K × V
∗
× V
∗
.
196 5. Автоматы Уотсона–Крика
Элементы множества K называются состояниями, V —
(входной) алфавит, ρ — отношение комплементарности на V ,
s
0
— начальное состояние, F — множество заключительных со-
стояний, а δ — функция переходов. Выражение s
0
∈ δ(s,
x
1
x
2
)
нужно понимать так: в состоянии s автомат прочитал x
1
в
верхней цепочке и x
2
в ниж ней цепочке и перешел в состоя-
ние s
0
.
Как и в случае конечных автоматов, можно записывать пе-
реходы M как переписывающие правила вида
s
x
1
x
2
→
x
1
x
2
s
0
;
такое правило означает то же самое, что и запись
s
0
∈ δ(s,
x
1
x
2
).
Замечание 5.1. В отличие от случая конечных автоматов в
описаниях автоматов Уотсона–Крика алфавит V и отношение
комплементарности ρ пишутся перед множеством состояний K
для того, чтобы подчеркнуть важность роли, играемой парой
(V, ρ) в таких машинах. Основным отличием конечных авто-
матов Уотсона–Крика от традиционных конечных автоматов
является работа с двойными цепочками
Переход в автомате Уотсона–Крика можно определить так:
для таких
x
1
x
2
,
u
1
u
2
,
w
1
w
2
∈
V
∗
V
∗
, что
h
x
1
u
1
w
1
x
2
u
2
w
2
i
∈ WK
ρ
(V )
и s, s
0
∈ K, запишем
x
1
x
2
s
u
1
u
2
w
1
w
2
=⇒
x
1
x
2
u
1
u
2
s
0
w
1
w
2
тогда и только тогда, когда s
0
∈ δ(s,
u
1
u
2
).
Через =⇒
∗
обозначим рефлексивное и транзитивное замы-
кание отношения =⇒.
Как и в случае склеивающих систем, мы исследуем здесь
язык строк, записанных в верхних цепочках лент Уотсона–
5.1. Конечные автоматы Уотсона–Крика 197
Крика, принимаемых данным автоматом, т. е. язык
L
u
(M) = {w
1
∈ V
∗
| s
0
w
1
w
2
=⇒
∗
w
1
w
2
s
f
, для s
f
∈ F,
и w
2
∈ V
∗
,
w
1
w
2
∈ WK
ρ
(V )}.
Замечание 5.2. Конечно, можно рассмотреть и язык строк,
записанных в нижних цепочках лент Уо тсона– Крика, и язык
молекул, но мы здесь такие языки не обсуждаем (они связаны
с L
u
(M) отношением ρ; когд а ρ инъективно, все три этих языка
изоморфны).
Другой важный пример языка, связанн ого с автоматом
Уотсона–Крика, получается, если вместо принимаемых слов
взять списки переходов.
Для конечного автомата Уотсона–Крика M = (V, ρ, K, s
0
,
F, P ) (в котором переходы задаются переписывающими пра-
вилами) рассмотрим помечивание e : P −→ Lab правил из
P элементами множества Lab. Через e(σ) обозначим после-
довательность меток правил, использованных при вычислении
σ : s
0
w =⇒
∗
ws
f
, где w ∈ WK
ρ
(V ), s
f
∈ F . Тем самым получим
язык
L
ctr
(M) = {e(σ) | σ : s
0
w =⇒
∗
ws
f
, w ∈ WK
ρ
(V ), s
f
∈ F }.
Замечание 5.3. Контрольное слово e(σ), ассоциированное с
вычислением σ на конечном автомате Уотсона–Крика, может
оказаться особенно полезным в молек улярных вычислениях,
где мы имеем дело со словами над заранее фиксированным
алфавитом и, следовательно, должны кодировать символы
б´ольших алфавитов, возникающих в тех задачах, которые
мы должны решить. Вспомним, например, самый первый
эксперимент по молекулярным вычислениям, разобранный в
разделе 2.1. Свяжем с исходным графом автомат Уотсона–
Крика, используя при определении переходов коды ребер на
верхнем уровне и коды вершин на нижнем ур овне. Пометим
каждый переход именем соответствующей вершины или реб-
ра. Тогда контрольное слово вычисления будет перетасовкой
198 5. Автоматы Уотсона–Крика
описания пути, ассоциированного с нашим вычислением, за-
писанным одновременно как последовательность ребер и как
последовательность вершин. С помощью слабого кодирова-
ния можно извлечь из контрольного слова описание нужного
нам пути. Таким образом, в этом случае контрольное сло-
во вычисления дает более ясную картину, чем принимаемая
последовательность. В частности, можно, как в опыте Эдл-
мана, за пускать автомат на недетерминировано выбранных
последовательностях, а затем отбирать интересующие нас
контрольные слова.
Будем говорить, что языки L
α
(M), α ∈ {u, ctr} распозна-
ются конечным автоматом Уотсона–Крика M .
Отметим еще раз, что работа автоматов Уотсона–Крика
определена только для элементов из WK
ρ
(V ), т. е. для д вой-
ных строк элементов из V , попарно связанных отношением
комплементарности ρ. Можно считать, что такая машина со-
стоит и з двойной ленты, на которой написаны элементы из
WK
ρ
(V ), конечной памяти, которая хранит номер состояния
из некоторого конечного множества, и двух головок чтения,
каждая из которых просматривает свой уровень ленты, од-
на — верхний, а другая — ниж ний . В начале работ ы каждая
головка расположена напротив первого символа своего уров ня,
и машина находится в состоянии s
0
. Две головки смещаются
вправо, в соответствии с текущим состоянием машины и функ-
цией перехода (правилами перехода). Шаг перехода состоит в
перемещении обеих головок через блоки, определяемые кон-
кретным правилом перехода. Остановка и принятие данной
последовательности происходят, если обе головки достига-
ют правого края последовательности, записанной на ленте,
а машина приходит в заключительное состояние. Рис. 5.1
иллюстрирует это представление.
Рассмотрим несколько вид ов автоматов Уотсона–Крика.
Скажем, что M = (V, ρ, K, s
0
, F, P ) является:
автоматом без состояний, если K = F = {s
0
};
всефинальным автоматом, если F = K;
5.1. Конечные автоматы Уотсона–Крика 199
s
?
-
6
-
Рис. 5.1. Конечный автомат Уотсона–Крика.
простым автоматом, если для всех s
x
1
x
2
→
x
1
x
2
s
0
∈ P вы-
полняется либо x
1
= λ, либо x
2
= λ;
1-ограниченным автоматом, если для всех
s
x
1
x
2
→
x
1
x
2
s
0
∈ P
выполняется |x
1
x
2
| = 1.
В автоматах без состояний можно опустить компоненты
K, s
0
, F , т. е. такой автомат можно записать в виде M = (V,
ρ, P ). Правила перехода для таких автоматов можно записать
в виде
x
1
x
2
.
Обозначим через AWK(α), NWK(α), F WK(α), SWK(α),
1WK(α), NSWK(α), N1WK(α), F SWK(α), F 1WK(α), семей-
ства языков вида L
α
(M), α ∈ {u, ctr}, распознаваемых конеч-
ными автоматами Уотсона–Крика с соответствующими допол-
нительным свойствами. Две последние буквы всех аббревиатур
соответствуют пер вой и последней букве одинарной цеп очк и
«W A T S O N C R I C K». Первые буквы аббревиатур озна-
чают, соответственно, (A) — произвольные автоматы, (N) —
автоматы без состояний, (F) — всефинальные автоматы, (S) —
простые автоматы, (1) — 1-ограниченные автоматы, (NS) —
простые автоматы без состояний, (N1) — 1-ограниченные авто-
маты без состояний, (FS) — простые всефинальные автоматы,
(F1) — 1-ограниченные всефинальные автоматы. Общий тер-
мин WK-семейства будет использоваться для ссылок на все
эти семейства языков.
200 5. Автоматы Уотсона–Крика
5.2 Соотношения между WK-семействами
В этом разделе исследуются соотношения между семействами
языков из предыдущего раздела, а также соотношения между
ними и семействами языков из иерархии Хомского.
Непосредственно из определений получаем:
Лемма 5.1. XWK(α) ⊆ AWK(α), α ∈ {u, ctr}, X ∈ {N, F, S,
1, NS, N1, F S, F 1}.
Лемма 5.2. NWK(α) ⊆ F WK(α), NSWK(α) ⊆ F SWK(α),
N1WK(α) ⊆ F 1WK(α), α ∈ {u, ctr}.
Лемма 5.3. XSWK(α) ⊆ SWK(α), X1WK(α) ⊆ 1WK(α),
X1WK(α) ⊆ XSWK(α) ⊆ XWK(α), 1WK(α) ⊆ SWK(α), α ∈
{u, ctr}, X ∈ {N, F }.
Кроме того, легко видеть, что выполняются след ующие со-
отношения:
Лемма 5.4. REG ⊆ 1WK(u).
Лемма 5.5. AWK(α) ⊆ CS , α ∈ {u, ctr}.
Лемма 5.6. Каждый язык из семейства XWK(u) является
кодированием языка из семейства XWK(ctr), X ∈ {A, N, F, S,
1, NS, N1, F S, F 1}.
Использование состояний является сильным средством в
том смысле, чт о произвольные правила перехода можно заме-
нить на простые правила перехода без уменьшения порождаю-
щей силы. Следующую лемму можно считать одним из часто
встречающихся в теории автоматов результатов о «нормальной
форме».
Лемма 5.7. AWK(u) ⊆ 1WK(u).
Доказательство. Рассмотрим конечный автомат Уотсона–
Крика без дополнительных ограничений M = (V, ρ, K, s
0
, F, P )
и построим 1-ограниченный автомат Уотсона–Крика
M
0
= (V, ρ, K
0
, s
0
, F, P
0
),
следующим образом.