Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений
Подождите немного. Документ загружается.
5.5. Варианты автоматов Уотсона–Крика 221
Мы не знаем, какие еще из результатов разделов 5.2 и 5.3
можно переформулировать для реверсивных конечных автома-
тов Уотсона–Крика. Во всяком сл учае, имеет место
Теорема 5.9. N RWK(u) − CF 6= ∅.
Доказательство. Рассмотрим реверсивный конечный автомат
Уотсона–Крика без состояний
M = ({a, b, c}, ρ, P ),
в котором
1. ρ = {(a, a), (b, b), (c, c)},
2. P =
n
a
c
,
b
λ
,
c
b
,
λ
a
o
и регулярный язык R = a
+
b
+
c
+
.
Нас интересует пересечение L
u
(M) ∩ R. По виду отноше-
ния ρ можно сказать, что лишь последовательности
w
w
, в ко-
торых w = a
n
b
m
c
p
, n, m, p > 1, могут быть входными для M,
приводящими к строкам из L
u
(M)∩R. Разбор такой последова-
тельности происходит следующим образом. Сначала получаем
λ
a
n
b
m
c
p
s
0
a
n
b
m
c
p
λ
=⇒
∗
a
n
a
n
b
m
c
p−n
s
0
b
m
c
p
c
n
=⇒
∗
a
n
b
m
a
n
b
m
c
p−n
s
0
c
p
c
n
,
если p > n, или
λ
a
n
b
m
c
p
s
0
a
n
b
m
c
p
λ
=⇒
∗
a
p
a
n
b
m
s
0
a
n−p
b
m
c
p
c
p
,
если n > p.
(В процессе используется только одно состояние автомата s
0
.
Оно бесполезно в смысле контроля за работой M и лишь отме-
чает положения читающих головок на дорожках.)
Дальнейшие шаги невозможны ни во втором случае, ни в
первом при p > n. Если же p = n, то возможны такие продол-
жения
a
n
b
m
a
n
b
m
s
0
c
n
c
n
=⇒
∗
a
n
b
m
c
n
a
n
b
m−n
s
0
λ
b
n
c
n
,
222 5. Автоматы Уотсона–Крика
если m > n, или
a
n
b
m
a
n
b
m
s
0
c
n
c
n
=⇒
∗
a
n
b
m
c
m
a
n
s
0
c
n−m
b
m
c
n
=⇒
∗
a
n
b
m
c
m
λ
s
0
c
n−m
a
n
b
m
c
n
,
если n > m.
Дальнейшие шаги невозможны ни во втором случае, ни в
первом при m > n. Если же m = n, то возможно такое продол-
жение
a
n
b
n
c
n
a
n
s
0
λ
b
n
c
n
=⇒
∗
a
n
b
n
c
n
λ
s
0
λ
a
n
b
n
c
n
.
Следовательно, L
u
(M) ∩ R = {a
n
b
n
c
n
| n > 1}, а это не кон-
текстно-свободный язык.
Теорема 5.10. F 1RWK(u) − CF 6= ∅.
Доказательство. Рассмотрим всефинальный 1-ограниченный
реверсивный конечный автомат Уотсона–Крика
M = ({a, b, c}, ρ, K, s
0
, K, δ) ,
в котором
1. ρ = {(a, a), (b, b), (c, c)},
2. K = {s
0
, s
1
, s
2
, s
3
},
3. δ(s
0
,
a
λ
) = {s
1
},
4. δ(s
1
,
λ
c
) = δ(s
0
,
b
λ
) = δ(s
2
,
λ
b
) = {s
0
},
5. δ(s
0
,
c
λ
) = {s
2
},
6. δ(s
0
,
λ
a
) = δ(s
3
,
λ
a
) = {s
3
},
7. δ(s,
u
v
) = ∅ в други х случаях.
Для регулярного языка R = a
+
b
+
c
+
получим
L
u
(M) ∩ R = {a
n
b
n
c
n
| n > 1}.
(При разборе цепочки
w
w
, в которой w = a
n
b
m
c
p
, состояния
из K контролируют работу M точно так же, как пары
u
v
∈ P
в доказательстве теоремы 5.9.)
5.6. Автоматы Уотсона–Крика с памятью 223
Следствие 5.10. Включения N SRWK(u) ⊂ F SR WK(u) и
NSRWK(u) ⊂ NRWK(u) строгие.
Естественными обобщениями конечных автоматов Уотсо-
на–Крика, к которым ведет идея реверсивных автоматов, яв-
ляются двунаправленные конечные автоматы Уотсона–Крика,
где одна или обе читающих головки способны передвигаться по
своим дорожкам ленты Уотсона–Крика в обоих направлен иях.
Мы не даем здесь формального определения таких уст-
ройств (в разделе 5.7 это будет сделано для случая, когда
только одна нижняя головка способна двигаться в обоих
направлениях). Тем не менее отметим, ч то поскольку двуна-
правленные автоматы являются обо бщениями обыкновенных
однонаправленных, все характеризации рекурсивно пере-
числимых языков из раздела 5.3 остаются верными и для
соответствующих вариантов двусторонних автоматов Уотсо-
на–Крика. Более того, остается верной и лемма 5.9, потому
что в случае простого автомата без состояний действия на
разных дорожках ленты не зависят друг от друга. В гла-
ве 3 было упомянуто, что двусторонние конечные автоматы
характеризуют регулярные языки. Проверка корректности со-
четаемости символов на цепочках в соответствии с отно шением
комплементарности может быть выполнена побуквенной пере-
тасовкой, выполняемой ОПМ, значит, эта операция сохраняет
регулярность.
Если дополнить модель маркерами конца на входной ленте,
то двусторонний конечный автомат Уотсона–Крика (с состоя-
ниями) сможет моделировать реверсивный конечный автомат
Уотсона–Крика.
Дальнейшее изучение этих вариантов конечных автоматов
Уотсона–Крика здесь не проводится.
5.6 Автоматы Уотсона–Крика
с памятью Уотсона–Крика
Обсуждавшиеся в разделе 5.4 конечные преобразователи Уот-
сона–Крика являются гибридными устройствами в том смысле,
224 5. Автоматы Уотсона–Крика
что они получают на входе ленту Уотсона–Крика, а на выходе
выдают обычную ленту (в одну строку). Это наводит на мысль
рассмотреть такое устройство, в котором бы и выходная лента
тоже была бы лентой Уотсона–Крика.
Префиксный автомат Уотсона–Крика — это конструкция
M = (V
1
, ρ
1
, V
2
, ρ
2
, K, s
0
, F, δ),
в которой
1. V
1
, V
2
— алфавиты,
2. ρ
1
⊆ V
1
× V
1
, ρ
2
⊆ V
2
× V
2
— симметричные отношения на
V
1
и V
2
, соответственно,
3. K — (конечное) множество состояний,
4. s
0
∈ K, F ⊆ K и
5. δ : K ×
V
∗
1
V
∗
1
−→ P
f
(
V
∗
2
V
∗
2
× K), где δ(s,
x
1
x
2
) 6= ∅ лишь
для конечного числа троек (s, x
1
, x
2
) ∈ K × V
∗
1
× V
∗
1
.
Интерпретируются эти элементы следующим образом.
1. V
1
и V
2
— алфавиты первой и второй лент Уотсона–Крика
соответственно.
2. ρ
1
, ρ
2
— отношения комплементарности на V
1
, V
2
.
3. K — множество состояний, в котором s
0
— начальное со-
стояние, а F — множество заключительных состояний.
4. δ — функция перехода.
Значение записи (
y
1
y
2
, s
0
) ∈ δ(s,
x
1
x
2
) состоит в следующем:
автомат в состоянии s читает строки x
1
, x
2
, записанные на
верхней и нижней цепочках первой ленты, после чего он пере-
ходит в состояние s
0
и пишет строки y
1
, y
2
на верхней и нижней
цепочках втор ой ленты. В начале работы автомат находится в
состоянии s
0
, а четыре его головки располагаются напротив
крайних левых концов четырех дорожек двух его лент. Работа
завершается, если автомат оказывается в одном из заключи-
тельных состояний, и при этом четыре его головки располага-
ются напротив крайних правых концов четырех цепочек двух
его лент. Рис. 5.6 иллюстрирует эту идею.
5.6. Автоматы Уотсона–Крика с памятью 225
s
?
-
6
-
?
-
6
-
Рис. 5.6. Автомат Уотсона–Крика с памятью.
Можно интерпретировать и использовать такую маши ну и
как распознающее устройство, и как преобразователь.
При интерпретации автомата как распознавателя вторая
лента используется как память для контроля за работой ав-
томата. Это можно сделать двумя способами:
1) начать с пустой второ й ленты и с каждым переходом
(
y
1
y
2
, s
0
) ∈ δ(s,
x
1
x
2
) записывать стр оки y
1
, y
2
на ее до-
рожках в крайних слева пустых позициях, или
2) начать со второй ленты, на которой записана последователь-
ность
h
w
1
w
2
i
∈ WK
ρ
2
(V
2
) и с каждым переходом (
y
1
y
2
, s
0
) ∈
δ(s,
x
1
x
2
) передвигать читающие головки на второй ленте
через слова y
1
, y
2
соответственно.
При первом способе использования памяти следует считать ра-
боту автомата корректной, если в результате на второй ленте
оказалась запись
h
w
1
w
2
i
∈ WK
ρ
2
(V
2
), как и во втором способе.
Ясно, что при таком условии оба способа использования второй
ленты в распознающем устройстве эквивалентны.
Во второй интерпретации, т. е. при использовании автомата
как преобразователя, следует считать входную последователь-
ность принятой, если втор ая лента оказалась пустой, а удале-
ние символов с нее можно производить двумя способами:
1) столбик
a
b
на второй ленте, в котором (a, b) ∈ ρ
2
, удаляется
сразу после появления;
226 5. Автоматы Уотсона–Крика
2) столбик
a
b
на второй ленте, в котором (a, b) ∈ ρ
2
, удаляется
после того, как обе головки окажутся справа от него.
Таким образом, в первом случае возникает память, организо-
ванная как очередь (первым вошел — первым вышел), которая
«тает» слева направо по мере укомплектования столбиков. По-
этому автоматы такого типа названы префиксными.
Дадим формальное определени е перехода, но лишь для того
случая, когда в начале работы на первой ленте записан элемент
WK
ρ
1
(V
1
), а вторая лен та пуста. При про чтени и первой ленты
на второй записывается элемент множества WK
ρ
2
(V
2
), т. е. по-
следовательность Уотсона–Крика. Таким образом, нам удастся
описать обе интерпретации префиксных автоматов Уотсона–
Крика: и распознаватели, и преобразователи.
Для w
1
, w
2
, x
1
, x
2
∈ V
∗
1
, z
1
, z
2
, y
1
, y
2
∈ V
∗
2
, s, s
0
∈ Q, запишем
s
x
1
w
1
x
2
w
2
/
z
1
z
2
=⇒ s
0
w
1
w
2
/
z
1
y
1
z
2
y
2
тогда и только тогда, когда
(
y
1
y
2
, s
0
) ∈ δ(s,
x
1
x
2
).
Последовательность
h
w
1
w
2
i
∈ WK
ρ
1
(V
1
) принимается автоматом
M, если существует такой элемент
h
z
1
z
2
i
∈ WK
ρ
2
(V
2
), что
s
0
w
1
w
2
/
λ
λ
=⇒
∗
s
f
λ
λ
/
z
1
z
2
.
Следовательно, вычисление (распознавание или трансляция)
завершается корректно, если последовательность Уотсона–
Крика на первой ленте прочитывается полностью и при этом
на второй ленте создается новая последовательность Уотсона–
Крика, иначе говоря, завершенная «молекула» в алфавите V
2
с соответствующим отношением комплементарности.
Замечание 5.5. Знак / в обозначениях выше разделяет две
разные сдвоенные последовательности, записанные на разных
лентах, а не две сцепленные сдвоенные последовательности.
Подчеркнем существенное различие между записями
h
x
1
x
2
ih
y
1
y
2
i
5.6. Автоматы Уотсона–Крика с памятью 227
и
h
x
1
x
2
i
/
h
y
1
y
2
i
; первую запись можно переписать в виде
h
x
1
y
1
x
2
y
2
i
,
что будет некорректно во втором случае.
При интерпретации префиксного автомата Уотсона–Крика
M как преобразователя результатом переработки последова-
тельности w =
h
w
1
w
2
i
∈ WK
ρ
1
(V
1
) будет
M(w) =
z
1
z
2
∈ WK
ρ
2
(V
2
) |
s
0
w
1
w
2
/
λ
λ
=⇒
∗
s
f
λ
λ
/
z
1
z
2
,
для некоторого s
f
∈ F
.
Особое значение здесь имеет тот факт, что последовательности
Уотсона–Крика над V
1
перерабатываются только в последова-
тельности Уотсона–Крика над V
2
; если на выходе не получится
элемент из WK
ρ
2
(V
2
), то переработка неудачна.
Мы не будем подробно исслед овать префиксные автоматы
Уотсона–Крика, используемые в качестве преобразователей.
Тем не менее отметим тот очевидный факт, что обобщенные по-
следовательные машины Уотсона–Крика из раздела 5.4 можно
смоделировать с помощью префиксных преобразователей Уот-
сона–Крика следующим образом: пусть в качестве отношения
комплементарности на V
2
взято от ношени е равенства, пусть
y
1
= y
2
для каждого перехода (
y
1
y
2
, s
0
) ∈ δ(s,
x
1
x
2
) и т. д.
Таким образом, утверждение теоремы 5.6 остается верным и
для (простых всефинальных) префиксных преобразователей
Уотсона–Крика.
Как и с конечным автоматом Уотсона–Крика, так и с пре-
фиксным автоматом Уотсона–Крика можно связать два языка:
L
α
(M), α ∈ {u, ctr}. Например,
L
u
(M) =
w ∈ V
∗
1
| s
0
h
w
w
0
i
/
λ
λ
=⇒
∗
s
f
λ
λ
/
z
1
z
2
для таких w
0
∈ V
∗
1
, z
1
, z
2
∈ V
∗
2
, s
f
∈ F, что
228 5. Автоматы Уотсона–Крика
h
w
w
0
i
∈ WK
ρ
1
(V
1
),
z
1
z
2
∈ WK
ρ
2
(V
2
)
.
Как и для конечных автоматов Уотсона–Крика, можно рас-
сматривать префиксные автоматы Уот сона–Кр ика, являющие-
ся простыми, 1-ограниченными, всефинальными ил и не имею-
щие состояний, а также обладающие какой-либо парой из при-
веденных свойств. В случае простых авт оматов в каждом пере-
ходе (
y
1
y
2
, s
0
) ∈ δ(s,
x
1
x
2
) в обеих парах x
1
, x
2
и y
1
, y
2
имеется
ровно по одному пустому слову, причем эти пустые слова не
обязательно имеют одинаковые индексы. Подобным образом, в
случае 1-ограниченных автоматов в обеих парах x
1
, x
2
и y
1
, y
2
имеется ровно п о одному пустому слову, а не пустые состоят из
одного символа. Можно рассмотреть и инициальные префикс-
ные автоматы Уотсона–Крика без состояний, реверси вные или
двусторонние автоматы, но здесь мы их не исследуем.
Префиксные автоматы Уотсона–Крика без состояний мож-
но представить в виде M = (V
1
, ρ
1
, V
2
, ρ
2
, P ), где
P ⊆
V
∗
1
V
∗
1
×
V
∗
2
V
∗
2
.
Обычно правила (
x
1
x
2
,
y
1
y
2
) из P записываются в виде
x
1
x
2
/
y
1
y
2
, где
x
1
x
2
обозначают строки, читаемые на пер-
вой ленте, а
y
1
y
2
обозначают строки, записываемые (или то-
же читаемые) на второй ленте (оба действия выполняются за
один такт работы автомата). Обозначим полученные таким пу-
тем семейства через XP WK(α) для X ∈ {A, N, F, S, 1, NS, N1,
F S, F 1} и α ∈ {u, ctr}.
Конечный автомат Уотсона–Крика можно смоделировать
с помощью идентичного ему префиксного автомата Уотсона–
Крика с двумя лентами так, что переходы будут происходить
на этих автоматах одинаково (это значит, что никакого допол-
нительного контроля за выводом вторая лента не даст). Из это-
го следует
5.6. Автоматы Уотсона–Крика с памятью 229
Лемма 5.20. XWK(α) ⊆ XP WK(α) для всех X и α, перечис-
ленных выше.
Это значит, что все представления семейства RE , получен-
ные для конечных автоматов Уотсон а–Кри ка, остаются верны
и для префиксных автоматов Уотсона–Крика. Кроме того, вер-
ны и соотношения между семействами XP WK(ctr), соответ-
ствующие диаграмме, изображенной на рис. 5.2.
Применение второй ленты увеличивает выразительную си-
лу автоматов Уотсона–Крика, а значит, и префиксных автома-
тов по сравнению с конечными.
Лемма 5.21. Если h
1
, h
2
: V
∗
−→ U
∗
— два морфизма, то
h
1
EQ(h
1
, h
2
)
∈ NSP WK(u).
Доказательство. Для данных морфизмов h
1
, h
2
построим
простой префиксный автомат Уотсона–Крика б ез состояний
M = (V
1
, ρ
1
, V
2
, ρ
2
, P ),
в котором
1. V
1
= U,
2. ρ
1
= {(a, a) | a ∈ U},
3. V
2
= V ,
4. ρ
2
= {(a, a) | a ∈ V },
5. P =
n
h
1
(a)
λ
/
a
λ
,
λ
h
2
(a)
/
λ
a
| a ∈ V
o
.
Легко видеть, что
w
1
w
2
/
λ
λ
=⇒
∗
λ
λ
/
z
1
z
2
,
если и только если w
1
= w
2
∈ U
∗
, z
1
= z
2
∈ V
∗
, w
1
= h
1
(z
1
) и
w
2
= h
2
(z
1
). Следовательно, L
u
(M) = h
1
EQ(h
1
, h
2
)
.
Следствие 5.11. Если h
1
, h
2
: V
∗
−→ U
∗
— два морфизма, то
EQ(h
1
, h
2
) ∈ NSP W K(u).
Доказательство. В доказательстве леммы 5.21 на обеих ча-
стях второй ленты оказалась запись EQ(h
1
, h
2
). Меняя ленты
местами, получим такой префиксный автомат Уотсона–Кри-
ка M
0
, что L
u
(M
0
) = EQ(h
1
, h
2
).
230 5. Автоматы Уотсона–Крика
Теорема 5.11. Каждый язык L ∈ RE можно представить
в виде L = h(L
0
∩ R), где L
0
∈ NSP WK(u), R ∈ REG и h —
проекция.
Доказательство. Достаточно применить л емму 5.21 вместе с
теоремой 3.16 или следствие 5.11 вместе с теоремой 3.15.
Следствие 5.12. Для каждого семейства F L, строго содер-
жащегося в RE и замкнутого относительно пересечений с
регулярными языками и произвольных морфизмов, выполня-
ется NSP WK(u) − F L 6= ∅.
Кроме того, из теоремы 5.11 следует, что включение
NSWK(u) ⊂ NSP WK(u) является строгим, так как NSWK(u)
содержит лишь регулярные языки.
Характеризацию RE, родственную вытекающей из теоре-
мы 5.11, можно получить и на основе следующего результата.
Лемма 5.22. Для каждого алфавита V выполняется T S
V
∈
N1PWK(u).
Доказательство. Рассмотрим простой префиксный автомат
Уотсона–Крика без состояний
M = (V
1
, ρ
1
, V
2
, ρ
2
, P ),
в котором
1) V
1
= V ∪ V ,
2) ρ
1
= {(a, a), (¯a, ¯a)) | a ∈ V },
3) V
2
= V ,
4) ρ
2
= {(a, a) | a ∈ V },
5) P =
λ
a
/
λ
λ
,
λ
¯a
/
λ
λ
| a ∈ V
o
∪
n
a
λ
/
a
λ
,
¯a
λ
/
λ
a
| a ∈ V
o
.
Итак, процесс корректного распознавания в M имеет вид
h
w
w
i
/
λ
λ
=⇒
∗
λ
λ
/
h
z
z
i
для w ∈ (V ∪ V )
∗
, z ∈ V
∗
, и w ∈ z t⊥ ¯z. Действительно, нижняя
дорожка первой ленты прочитывается безо всякого взаимодей-