Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений
Подождите немного. Документ загружается.
4.3. Выразительная сила систем со склейкой 171
2. h
u
1
u
2
,
v
1
v
2
i →
h
w
1
w
2
i
h
u
0
1
u
0
2
,
v
0
1
v
0
2
i
h
z
1
z
2
i
для таких
w
1
w
2
,
z
1
z
2
∈ WK
ρ
(V ),
h
u
1
u
2
,
v
1
v
2
i, h
u
0
1
u
0
2
,
v
0
1
v
0
2
i ∈ N,
и (
x
1
x
2
x
0
1
x
0
2
u
0
1
u
0
2
,
v
0
1
v
0
2
y
1
y
2
y
0
1
y
0
2
) ∈ D,
что
h
u
1
x
1
x
0
1
u
2
x
2
x
0
2
i
=
h
w
1
w
2
i
,
h
y
1
y
0
1
v
1
y
2
y
0
2
v
2
i
=
h
z
1
z
2
i
. (При движении к «цен-
тру» последовательности слева и справа присоединяются
блоки, взятые из пар множества D, а нетерминальные сим-
волы обеспечивают правильность соединений. Для этой це-
ли будет достаточно запасенных нетерминальных символов,
поскольку γ обладает свойством ограниченной задержки.)
3. h
u
1
u
2
,
v
1
v
2
i →
h
w
1
w
2
ih
x
1
x
2
ih
z
1
z
2
i
, если
w
1
w
2
,
x
1
x
2
,
z
1
z
2
∈ WK
ρ
(V ),
x
1
x
2
6=
λ
λ
,
h
u
1
u
2
,
v
1
v
2
i ∈ N,
и найдется такая аксиома
w
0
1
w
0
2
h
x
1
x
2
i
z
0
1
z
0
2
∈ A, что
w
0
1
w
0
2
,
z
0
1
z
0
2
∈
λ
V
∗
∪
V
∗
λ
и
h
w
1
w
2
i
=
h
u
1
w
0
1
u
2
w
0
2
i
,
h
z
1
z
2
i
=
h
z
0
1
v
1
z
0
2
v
2
i
.
(Вывод можно завершить, когда оба липких конца какой-
либо аксиомы из A подходят к липким концам, которые
хранит в себе единственный в последовательности элемент
из N.)
4. S →
h
w
1
w
2
i
, для
h
w
1
w
2
i
∈ A.
172 4. Системы со склейкой
Из предыдущих объяснений легко понять, что L(G) =
LM
d
(γ). Поскольку L
d
(γ) является кодированием LM
d
(γ),
получаем L
d
(γ) ∈ LIN .
Следствие 4.3. Для каждой склеивающей системы γ и каж-
дого целого d выполняется L
d
(γ) ∈ LIN .
Доказательство. Эт о прямое следствие предыдущего доказа-
тельства.
Поскольку в склеивающих системах не используются вспо-
могательные символы, довольно удивительно, ч то верны и об-
ратные приведенным в теоремах 4.1 и 4.3 включения, даже
в усиленном виде. Приведем сначала д оказательство для ре-
гулярного случая. Оно проще и подготовит ч итателя к более
сложному доказательству в линейном случае.
Теорема 4.4. REG ⊆ RSL(b) ∩ RSL(p).
Доказательство. Рассмотрим конечный автомат M = (K, V,
s
0
, F, δ), где K = {s
0
, s
1
, . . . , s
k
}, n > 0.
Построим регулярную склеивающую систему γ = (V, ρ,
A, D), в которой
1. ρ = {(a, a) | a ∈ V },
2. A =
x
x
| x ∈ L(M), |x| 6 k + 2
∪
x
x
u
λ
| |xu| = k + 2,
|x| > 1, |u| = i, для таких 1 6 i 6 k + 1, что s
0
xu =⇒
∗
xus
i−1
,
3. D = {(
λ
λ
,
λ
v
x
x
u
λ
) | 1 6 |v| 6 k + 1, |xu| = k + 2,
|x| > 1, |u| = i, для таких 1 6 i 6 k+1, что s
j
xu =⇒
∗
xus
i−1
,
и j = |v| − 1} ∪ {(
λ
λ
,
λ
v
x
x
) | 1 6 |v| 6 k + 1, 1 6 |x| 6 k,
и s
j
x =⇒
∗
xs
f
, s
f
∈ F , где j = |v| − 1}.
Эта система начинает работу с домино такого вида как на
рис. 4.4a, затем использует несколько раз домино такого вида
как на рис. 4.4b, и заканчивает вычи слени е на д омино такого
вида как на рис. 4.4c.
Состояния автомата M кодируются длиной отростков.
Каждая не попавшая в WK
ρ
(V ) аксиома из A имеет правый
4.3. Выразительная сила систем со склейкой 173
a
b
c
Рис. 4.4. Домино, используемые в доказательстве теоремы 4.4.
отросток д ли ны i, 1 6 i 6 k + 1, этим она определяет со-
стояние s
i−1
. Тем же свойством обладают и правые члены
пар из D, соответствующие по виду домино, изображенной
на рис. 4.4b. Автомат M окажется в состоянии s
i−1
после
прочтения строки, которая записана в верхней нити молеку-
лы с правильной основой, склеенной из домино. Все домино
видов 4.4b и 4.4c имеют непустой левый отросток, след ова-
тельно, молекула из WK
ρ
(V ) не может удлиняться. То есть
после использования домино типа c) вычисление останавли-
вается. Поскольку задержка системы γ не прево сходит k + 1,
получаем L
n
(γ) = L
p
(γ) = L
k+1
(γ) = L(M), что и завершает
доказательство.
Следствие 4. 4. RSL(α) = OSL(α) = REG, α ∈ {n, p, b}.
Доказательство. OSL(n) ⊆ REG по теор еме 4.1. След-
ствие 4.1 дает включение OSL(p) ⊆ REG. Включение
OSL(b) ⊆ OSL(n) ⊆ REG отмечено в лемме 4.2, а вклю-
чение RSL(α) ⊆ OSL(α), α ∈ {n, p, b} — в лемме 4.1. В
предыдущей теореме доказаны включения REG ⊆ RSL(b)
и REG ⊆ RSL(p). Вместе с RSL(b) ⊆ RSL(n) (лемма 4.2),
получаем REG ⊆ RSL(n).
Теорема 4.5. LIN ⊆ ASL(b) ∩ ASL(p).
Доказательство. Рассмотрим линейную грамматику G =
(N, T, S, P ). Существует такая эквивалентна я ей граммати-
ка G
0
= (N
0
, T, S, P
0
), что P
0
содержат лишь пр ави ла вида
X → aY, X → Y a, X → a, дл я X, Y ∈ N
0
, a ∈ T .
Предположим, что N
0
= {X
1
, X
2
, . . . , X
k
}, k > 1. Построим
склеивающую систему γ = (T, ρ, A, D), в которой
(A) ρ = {(a, a) | a ∈ T },
(B) A =
x
x
| x ∈ L(G), |x| 6 3k + 1
∪{
u
λ
x
x
| |ux| 6 3k+1,
|x| > 1, |u| = i, для таких 1 6 i 6 k, что X
i
=⇒
∗
ux} ∪
174 4. Системы со склейкой
{
x
x
u
λ
| |xu| 6 3k +1, |x| > 1, |u| = i, для таких 1 6 i 6 k,
что X
i
=⇒
∗
xu},
(C) D содержит следующие группы пар домино:
1) (
u
λ
x
x
λ
v
,
z
z
) для 1 6 |u| 6 k, 1 6 |v| 6 k, |ux| =
k + 1, 0 6 |z| 6 k, и X
|u|
=⇒
∗
uxX
|v|
z,
2) (
x
x
λ
v
,
z
z
u
λ
) для 1 6 |v| 6 k, 1 6 |u| 6 k, 1 6 |x| 6
k, |zu| = k + 1, и X
|u|
=⇒
∗
xX
|v|
zu,
3) (
x
x
λ
v
,
z
z
), для 1 6 |v| 6 k, |x| > 1, |xz| 6 2k + 1,
|z| > 0, и S =⇒
∗
xX
|v|
z,
4) (
z
z
,
λ
v
x
x
u
λ
), для 1 6 |v| 6 k, 1 6 |u| 6 k, |xu| =
k + 1, 0 6 |z| 6 k, и X
|u|
=⇒
∗
zX
|v|
xu,
5) (
u
λ
z
z
,
λ
v
x
x
), для 1 6 |u| 6 k, 1 6 |v| 6 k, 1 6 |x| 6
k, |uz| = k + 1, и X
|u|
=⇒
∗
uzX
|v|
x,
6) (
z
z
,
λ
v
x
x
), для 1 6 |v| 6 k, |x| > 1, |xz| 6 2k + 1,
|z| > 0, и S =⇒
∗
zX
|v|
x.
Идея этой конструкции в следующем. Мы намерены моде-
лировать выводы в G
0
в обратном порядке вычислениями в γ,
которые начинаются с блока в центре строки и продолжаются
добавлением блоков к обоим концам строки. Нетерминальный
символ из N
0
вновь шифруется длиной отростка на одном из
концов строящейся последовательности, тогда как второй ко-
нец последовательности прямой.
Разбиение пар на группы соответствует перемещению от-
ростка по концам строящейся строки. Домино пар из группы 1
оставляют левый конец липким, т. е. и до и после приклеивания
такой пары информация о нетерминальном символе находит-
ся на левом конце последовательности. Группа 2 перемещает
липкий конец слева направо. Пары из группы 3 завершают по-
строение молекулы. Пары из групп 4, 5 и 6 действуют симмет-
рично парам из групп 1, 2 и 3 соответственно. Последователь-
ность с двумя прямыми концами не может быть продолжена,
4.3. Выразительная сила систем со склейкой 175
поскольку у каждой пары из D есть не пустой липкий конец с
«внутренней стороны» домино пары.
Таким образом, ясно, что завершенные вычисления в γ со-
ответствуют выводам в G
0
. Обратно, каждый вывод в G можно
смоделировать каким-либо завершенным вычислением в γ.
В самом деле, рассмотрим вывод δ : S =⇒
∗
w в G. Если
|w| 6 3k + 1, то
w
w
∈ A. Предп оложим, что |w| > 3k + 1.
Поскольку каждое правило из P
0
вносит ровно один терми-
нальный символ, можно так разложить вывод δ на отр езки
S =⇒
∗
u
1
X
i
1
v
1
=⇒
∗
u
1
u
2
X
i
2
v
2
v
1
=⇒
∗
. . .
=⇒
∗
u
1
. . . u
r
X
i
r
v
r
. . . v
1
=⇒
∗
u
1
. . . u
r
yv
r
. . . v
1
,
что
1. |u
j
| = k + 1 и 0 6 |v
j
| 6 k, или 0 6 |u
j
| 6 k и |v
j
| = k + 1,
для каждого j = 1, 2, . . . , r,
2. k + 1 6 |y| 6 3k + 1,
3. r > 1.
После этого для каждой пары (u
j
, v
j
) со свойством |u
j
| =
k + 1 можно подобрать пару домино вида 1 или 5, кодирую-
щую X
i
j−1
в левом конце отростком длины i
j−1
, для каждой
пары (u
j
, v
j
) со свойством |v
j
| = k + 1 можно подобрать па-
ру домино вида 2 или 4, кодирующую X
i
j−1
в правом конце
отростком длины i
j−1
. Ясно, что для y можно подобрать акси-
ому, кодирующую X
i
r
в одном из концов. Также и для (u
1
, v
1
)
можно подобрать пару домино вида 3 или 6, делающую оба
конца прямыми. Следовательно, получаем L(G) ⊆ L
n
(γ).
Очевидно, что L
n
(γ) = L
p
(γ) и задержка γ не превосходит
k, значит, L
n
(γ) = L
k
(γ), что и завершает доказательство.
Следствие 4. 5. LIN = ASL(b).
Доказательство. Нужно объединить теоремы 4.3 и 4.5.
В доказательстве теоремы 4.1 мы отметили, что если γ =
(V, ρ, A, D) — односторонняя склеивающая система, то L
n
(γ) =
L
d
(γ) для некоторого целого d, зависящего от A и D (макси-
мальная длина липкого конца домино из A или из D). Очевид-
176 4. Системы со склейкой
SRSL(b) = SRSL(n)
SOSL(b) = SOSL(n)
6
@
@
@
@I
OSL(n) = RSL(n) = REG
OSL(b) = RSL(b) =
SSL(b)
@
@
@I
ASL(b) = LIN
@
@
@
@I
SSL(n)
@
@
@I
ASL(n)
CS
6
Рис. 4.5. Соотношения между семействами языков,
порожденных склеивающими системами.
но, что это также верно для простых и для простых регулярных
систем, тем самым мы получили следующий результат.
Теорема 4.6. SOSL(n) = SOSL(b), SRSL(n) = SRSL(b).
Доказательство. Включение ⊆ обсуждено выше, а обратное
включение — в лемме 4.2.
Суммируя предыдущие результаты для семейств XSL(b),
XSL(n), мы получим диаграмму, изображенную на рис. 4.5;
как обычно, стрелками обозначены нестрогие включения.
Теорема 4.7. REG − SOSL(α) 6= ∅, α ∈ {n, b}.
Доказательство. Рассмотрим регулярный язык L = ba
+
b и
предположим, что L = L
n
(γ) для некоторой простой односто-
ронней склеивающей системы γ = (V, ρ, A, D). Поскольку A —
конечное множество (молекул с правильной основой), а L —
бесконечный язык, в D найдутся две пары одного из следую-
щих видов:
4.4. Представления регулярных языков 177
1. (
λ
λ
,
λ
y
2
) и (
λ
λ
,
y
0
1
λ
), где y
2
∈ V
+
, y
0
1
∈ a
+
,
2. (
λ
λ
,
y
1
λ
) и (
λ
λ
,
λ
y
0
2
), где y
1
∈ a
+
, y
0
2
∈ V
+
,
3. (
λ
x
2
,
λ
λ
) и (
x
0
1
λ
,
λ
λ
), где x
2
∈ V
+
, x
0
1
∈ a
+
,
4. (
x
1
λ
,
λ
λ
) и (
λ
x
0
2
),
λ
λ
), где x
1
∈ a
+
, x
0
2
∈ V
+
,
которые используются сколь угодно много раз при порождении
достаточно длинных строк из L.
Все четыре случая можно трактовать одинаково. Предпо-
ложим, что мы имеем дело с первым случаем, тогда
(
λ
λ
,
λ
y
2
) ∈ D, (
λ
λ
,
y
0
1
λ
) ∈ D.
Ясно, что y
0
1
= a
i
для некоторого i > 1 и строка y
2
составлена
из таких символов c, что (a, c) ∈ ρ.
Предположим, что |y
2
| = j, j > 1. Завершенное вычисление
x
1
x
2
y
1
y
2
z
1
z
2
=⇒
∗
w
1
w
2
для
x
1
x
2
y
1
y
2
z
1
z
2
∈ A,
x
1
x
2
,
z
1
z
2
∈
V
∗
λ
∪
λ
V
∗
и
h
y
1
y
2
i
,
h
w
1
w
2
i
∈ WK
ρ
(V ), w
1
= ba
n
b, можно продолжить следу-
ющим образом:
x
1
x
2
y
1
y
2
z
1
z
2
=⇒
∗
w
1
w
2
=⇒
∗
"
w
1
y
0
1
j
w
2
y
i
2
#
.
Это завершенное вычисление, создающее строку w
1
y
0
1
j
=
ba
n
ba
ij
, которая не лежит в L. Противоречие.
Следствие 4. 6. Включение SOSL(n) ⊆ OSL(n) строгое.
4.4 Представления регулярных
и линейных языков
Мы установили, что включение SOSL(n) ⊂ REG является
строгим, и предполагаем, что строгим будет и включение
178 4. Системы со склейкой
SSL(b) ⊆ LIN . Поэтому было бы интересно дополнить скле-
ивающие системы сжимающим механизмом с тем, чтобы
попытаться получить представления регулярных и линей-
ных языков, отправляясь от языков и з семейств SOSL(n)
и соответственно SSL(b). Этого можно добиться даже пр и
использовании таких слабых сжимающих механизмов, как
кодирование и слабое кодирование.
Теорема 4.8. Каждый регулярный язык является кодирова-
нием языка из семейства SRSL(α ) для любого α ∈ {n, b, p}.
Доказательство. Рассмотрим регулярную грамматику G =
(N, T, S, P ) и построим склеивающую систему
γ = (V, ρ, A, D),
в которой
1) V = {[X, a]
i
| X ∈ N, a ∈ T, i = 1, 2},
2) ρ = {([X, a]
1
, [X, a]
1
), ([X, a]
2
, [X, a]
2
) | X ∈ N, a ∈ T },
3) A =
nh
[S,a]
1
[S,a]
1
i
λ
[X,b]
2
| S → aX ∈ P и либо X → bY ∈ P ,
либо X → b ∈ P , a, b ∈ T , X, Y ∈ N
o
∪
nh
[S,a]
1
[S,a]
1
i
| S → a ∈ P , a ∈ T
o
,
4) D =
n
(
λ
λ
,
λ
[X,a]
1
[Y,b]
2
) | X → aY ∈ P и либо
Y → bY
0
∈ P , либо Y → b ∈ P , для a, b ∈ T и X, Y, Y
0
∈ N
o
∪
n
(
λ
λ
,
λ
[X,a]
1
) | X → a ∈ P, X ∈ N, a ∈ T
o
∪
n
(
λ
λ
,
[X,a]
2
[Y,b]
1
λ
) | X → aY ∈ P и либо Y → bY
0
, либо
Y → b ∈ P , для a, b ∈ T и X, Y, Y
0
∈ N
o
∪
n
(
λ
λ
,
[X,a]
2
λ
) | X → a ∈ P, X ∈ N, a ∈ T
o
.
Каждый вывод в G вида
=⇒ a
1
X
1
=⇒ a
1
a
2
X
2
=⇒
. . . =⇒ a
1
a
2
. . . a
k
X
k
=⇒ a
1
a
2
. . . a
k
a
k+1
,
k > 1, соответствует вычислению в γ вида
4.4. Представления регулярных языков 179
[S, a
1
]
1
[S, a
1
]
1
λ
[X
1
, a
2
]
2
=⇒
[S, a
1
]
1
[X
1
, a
2
]
2
[S, a
1
]
1
[X
1
, a
2
]
2
[X
2
, a
3
]
1
λ
=⇒ . . .
с чередованием липких концов
[X
2i
,a
2i+1
]
1
λ
и
λ
[X
2i−1
,a
2i
]
2
. Вы-
вод завершается использованием блока
λ
[X
k
,a
k+1
]
1
при четном
k и блока
λ
[X
k
,a
k+1
]
1
при нечетном k. Все нижние блоки до-
мино из D начинаются с символов вид а [X, a]
1
, а все верхние
с символов вида [X, a]
2
. Таким образом, завершенное вычисле-
ние невозможно продолжить (из-за отношения ρ). В силу это-
го ясно, что L
n
(γ) = L
p
(γ) = L
1
(γ), и что для кодирования h,
определяемого как h([X, a]
i
) = a для X ∈ N, a ∈ T , i = 1, 2,
получим L(G) = h
L
n
(γ)
.
Для произвольного семейства языков FL через Cod(FL)
обозначим семейство всевозможных языков вида h(L), где L —
язык из FL, а h — кодирование.
Следствие 4.7. Cod
SOSL(α)
= Cod
SRSL(α)
= REG,
α ∈ {n, b, p}.
Доказательство. Все семейства SOSL(α), SRSL(α), α ∈ {n,
b, p} содержатся в семействе REG (теорема 4.1, следствие 4.1),
которое замкнуто относител ьно (произвольных) морфизмов.
Следовательно, семейства Cod(SOSL(α)
и Cod
SRSL(α)
также содержатся REG. В п редыд ущей теореме доказаны
обратные включения.
Теорема 4.9. Каждый линейный язык является слабым ко-
дированием языка из семейства SSL(b).
Доказательство. Рассмотрим линейную грамматику G =
(N, T, S, P ). Без потери общности можно предполагать, что
все правила в P имеют вид X → aY , X → Y a, X → a, a ∈ T ,
X , Y ∈ N. Возьмем новый символ c /∈ T и заменим эти правила
на X → aY c, X → cY a, X → cac. Таким образом, можно
предполагать, что для каждого линейного языка L ⊆ T
∗
есть
символ c /∈ T и такая линейная грамматика G
0
с правилами
180 4. Системы со склейкой
вывода упомянутого выше вида, что L = g
L(G
0
)
для сла-
бого кодирования g, стирающего символ c и оставляющего
неизменными символы из T .
Предположим, что уже G = (N, T ∪{c}, S, P ) является такой
грамматикой для данного языка L ∈ LIN.
Построим простую склеивающую систему
γ = (V, ρ, A, D),
в которой
(A) V = {[X, a]
i
| X ∈ N, a ∈ T ∪ {c}, i = 1, 2, 3},
(B) ρ = {([X, a]
i
, [X, a]
i
) | X ∈ N, a ∈ T ∪ {c}, i = 1, 2, 3},
(C) A =
n
[X,a
1
]
1
λ
h
[X,a
2
]
3
[X,a
2
]
3
i
[X,a
3
]
1
λ
| X → a
1
a
2
a
3
∈ P , X ∈
N, a
1
, a
2
, a
3
∈ T ∪ {c}
o
(D) D состоит из следующих пар домино:
(a) (
λ
[Y,a
2
]
2
[X,a
1
]
1
,
λ
[X,a
3
]
1
[Y,a
4
]
2
), для Y → a
2
Xa
4
∈ P ,
a
1
, a
2
, a
3
, a
4
∈ T ∪ {c}, X, Y ∈ N , и есть правило
X → a
1
X
0
a
3
или X → a
1
a
5
a
3
в P, X
0
∈ N, a
5
∈ T ∪ {c},
(b) (
[Y,a
2
]
1
[X,a
1
]
2
λ
,
[X,a
3
]
2
[Y,a
4
]
1
λ
) для Y → a
2
Xa
4
∈ P ,
a
1
, a
2
, a
3
, a
4
∈ T ∪ {c}, X, Y ∈ N , и есть правило
X → a
1
X
0
a
3
или X → a
1
a
5
a
3
в P, X
0
∈ N, a
5
∈ T ∪ {c},
(c) (
λ
[S,a
1
]
1
,
λ
[S,a
2
]
1
) для S → a
1
Xa
2
∈ P , X ∈ N, a
1
, a
2
∈
T ∪ {c},
(d) (
[S,a
1
]
2
λ
,
[S,a
2
]
2
λ
) для S → a
1
Xa
2
∈ P , X ∈ N, a
1
, a
2
∈
T ∪ {c}.
Смоделируем выводы в G от конца к началу, начав наращи-
вать строку из центра. Пары домино из первой группы добав-
ляют блоки снизу, а пары из второй группы — сверху. При этом
все домино первой группы присоединяются к символам [X, a]
1
,
а домино второй группы — к символам [X, a]
2
. Таким образом,
получается молекула, состоящая и з столбика вида
h
[X,a]
3
[X,a]
3
i
по
середине и чередующихся последовательностей столбиков ви-
да
h
[X,a]
1
[X,a]
1
i
и
h
[X,a]
2
[X,a]
2
i
слева и справа от него. Это чередование