Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений
Подождите немного. Документ загружается.
3.1. Основные понятия 131
=⇒ (x
(2)
1
, . . . , x
(2)
n
) ` (y
(2)
1
, . . . , y
(2)
n
) =⇒
. . . =⇒ (x
(s)
1
, . . . , x
(s)
n
),
для некоторого s > 1 такого, что w = x
(s)
1
}.
Приведем пример. Пусть
Γ = (N, T, (S
1
, P
1
, R
1
), (S
2
, P
2
, R
2
), (S
3
, P
3
, R
3
)),
N = {S
1
, S
2
, S
0
2
, S
3
, S
0
3
, X}, T = {a, b, c},
P
1
= {S
1
→ aS
1
, S
1
→ bS
1
, S
1
→ X}, R
1
= {a, b}
∗
c,
P
2
= {S
2
→ S
0
2
, X → c}, R
2
= {a, b}
∗
X ,
P
3
= {S
3
→ S
0
3
, X → c}, R
3
= {a, b}
∗
X .
Начинаем с тройки (S
1
, S
2
, S
3
). Максимальный покомпо-
нентный вывод имеет вид
(S
1
, S
2
, S
3
) =⇒ (xX, S
0
2
, S
0
3
)
для некоторой строки x ∈ {a, b}
∗
. Строка xX будет послана
второй и третьей компонентам, откуда получаем
(xX , S
0
2
, S
0
3
) ` (S
1
, xX, xX) =⇒ (yX, xc, xc) `
` (xcxc, yX, yX) =⇒ (xcxc, yc, yc),
для некоторой строки y ∈ {a, b}
∗
. Строка xcxc терминальная,
откуда
L(Γ) = {xcxc | x ∈ {a, b}
∗
}.
Итак, очень простая система Γ всего лишь с тремя праволиней-
ными компонентами породила неконтекстно-свободный язык.
Отметим, что каждый вывод в системе Γ содержит ровно два
шага взаимодействия (и три шага переписывания, посл едни й из
которых нужен только ради соответствия приведенному выше
определению языка L(Γ), в котором предполагается, что вывод
всегда оканчивается шагом переписывания).
Мы не обсуждаем здесь порождающую силу таких грамма-
тических систем. Как и в случае регулируемых переписываний,
для нас более важны лежащие в их основе идеи распр еделен ия,
кооперации, взаимодействия и параллелизма.
132 3. Введение в теорию языков
3.2 Характеризации рекурсивно перечислимых
языков
Неизменными ориентирами наших исследований в последую-
щих главах будут две следующие границы вычислимости. Наи-
низший представляющий интерес уровень вычислимости за-
дается конечными автоматами, а наивысший возможный уро-
вень в соответствии с тезисом Черча–Тьюринга определяет-
ся машинами Тьюринга. Конечн ым автоматам соответствуют
регулярные, а машинам Тьюринга — рекурсивно перечисли-
мые языки. Доказательство того, что устройства из некоторо-
го данного класса способны породить все регулярные языки,
обычно несложно: начав с конечного автомата или регуляр-
ной грамматики, нужно промоделировать его или ее работу
устройством желаемого типа. Иногда сходный прием срабаты-
вает и при характеризации рекурсивно перечислимых языков.
(В этом смысле весьма полезны нормальные формы, обсуж-
давшиеся в предыдущем разделе.) Однако зачастую прямое
моделирование затруднительно, и тогда на помощь приходят
теоремы о представлениях рекурсивно перечислимых языков.
Среди них есть и парадоксальные с интуитивной точки зре-
ния, что делает их следствия особенно интересными. Посколь-
ку некоторые результаты последующих глав существенным об-
разом опираются на теоремы о представлениях, мы приведем
здесь доказательства ряда таких теорем.
Первая из них очень проста.
Теорема 3.12. Для любого языка L ⊆ T
∗
из RE найдутся
такие L
0
∈ CS и c
1
, c
2
/∈ T , что L
0
⊆ L{c
1
}{c
2
}
∗
и для каждой
строки w ∈ L есть такое i > 0, что wc
1
c
i
2
∈ L
0
. (Итак, L и L
0
равны по модулю «хвоста» вида c
1
c
i
2
, i > 0.)
Доказательство. По грамматике G = (N, T, S, P ) типа 0 по-
строим грамматику G
0
= (N ∪ {S
0
, X}, T ∪ {c
1
, c
2
}, S
0
, P
0
), в
которой
P
0
= {S
0
→ Sc
1
} ∪ {u → v | u → v ∈ P, |u| 6 |v|}
∪ {u → vX
n
| u → v ∈ P, |u| > |v|, n = |u| − |v|}
3.2. Характеризации рекурсивно перечислимых языков 133
∪ {Xα → αX | α ∈ N ∪ T } ∪ {Xc
1
→ c
1
c
2
}.
Легко видеть, что G
0
моделирует выводы в G с той лишь
разницей, что вместо сокращающих длину слова правил из P
используются правила, вводящие символ X. Этот символ мож-
но сдвинуть вправо и заменить на терминаль ный символ c
2
справа от c
1
. Тогда, если L = L(G), то язык L
0
= L(G
0
) удовле-
творяет заключению теоремы.
Следствие 3.2. (i) Л юбой рекурсивно перечислимый язык яв-
ляется проекцией некоторого контекстного языка.
(ii) Для лю бого L ∈ RE существуют такие языки L
1
∈ CS
и L
2
∈ R EG, что L = L
1
/L
2
.
Доказательство. Первое утверждение получится, если взять
проекцию, стирающую введенные выше символы c
1
, c
2
. Второе
утверждение получится, если рассмотреть регулярный язык
L
2
= c
1
c
∗
2
. (В обоих случаях контекстный язык — это язык L
0
из теоремы 3.12.)
Разумеется, приведенные выше утверждения верны и в
«зеркальной» версии, т. е. для L
0
⊆ {c
2
}
∗
{c
1
}L в теореме 3.12,
и для левого деления в пункте (ii) следствия 3.2.
Эти результаты показывают, что семейства RE и CS «по-
чти равны»: строки из языков этих семейств различаются лишь
хвостом, который, имея вид c
1
c
i
2
, i > 1, не несет никакой ин-
формации, кроме своей длины. Следовательно с синтаксиче-
ской т очк и зрения языки L и L
0
в теореме 3.12 можно считать
неразличимыми.
Приводимые ниже результаты имеют другую природу: в
них рекурсивно перечислимые языки строятся, исходя из «ма-
леньких» подсемейств семейства RE, но при этом используют-
ся сильные операции (такие, как пересечение, деление и т.п.).
Теорема 3.13. Любой рекурсивно перечислимый язык есть
частное двух линейных языков.
Доказательство. Пусть L ∈ RE, L ⊆ T
∗
. Рассмотрим грам-
матику G = (N, T, S, P ) типа 0, порождающую язык mi(L) и
добавим к P правило S → S. (После этого можно считать, что
134 3. Введение в теорию языков
каждый вывод в G состоит по крайней мере из двух шагов.)
Возьмем символ c 6∈ N ∪ T и построим языки
L
1
= {x
n
u
n
y
n
cx
n−1
u
n−1
y
n−1
c · · · cx
1
u
1
y
1
cc mi(y
1
) mi(v
1
)
mi(x
1
)c mi(y
2
) mi(v
2
) mi(x
2
)c · · · c mi(y
n−1
) mi(v
n−1
)
mi(x
n−1
)ccc mi(y
n
) mi(v
n
) mi(x
n
) | n > 2, x
i
, y
i
∈ (N ∪ T )
∗
,
u
i
→ v
i
∈ P , 1 6 i 6 n и x
n
v
n
y
n
∈ T
∗
},
L
2
= {w
n
cw
n−1
c · · · cw
1
cScc mi(w
1
)c mi(w
2
)c · · · c mi(w
n
)ccc |
n > 1, w
i
∈ (N ∪ T )
∗
, 1 6 i 6 n}.
Оба они линейные. Вот грамматика для L
1
:
G = ({X
0
, X
1
, X
2
, X
3
}, N ∪ T ∪ {c}, X
0
, P
1
),
P
1
= {X
0
→ aX
0
a | a ∈ T }
∪ {X
0
→ uX
1
mi(v) | u → v ∈ P, v ∈ T
∗
}
∪ {X
1
→ aX
1
a | a ∈ T }
∪ {X
1
→ cX
2
ccc}
∪ {X
2
→ aX
2
a | a ∈ N ∪ T }
∪ {X
2
→ uX
3
mi(v) | u → v ∈ P }
∪ {X
3
→ aX
3
a | a ∈ N ∪ T }
∪ {X
3
→ cX
2
c, X
3
→ cc}.
Покажем, что L = L
2
\L
1
. Действительно, каждая строка
из L
1
имеет вид
w = w
n
cw
n−1
c · · · cw
1
ccw
0
1
cw
0
2
c · · · cw
0
n−1
cccw
0
n
,
где n > 2, w
i
=⇒ mi(w
0
i
), 1 6 i 6 n, в грамматике G, и w
0
n
∈ T
∗
.
Каждая строка из L
2
имеет вид
z = z
m
cz
m−1
c · · · cz
1
cScc mi(z
1
)c · · · c mi(z
m
)ccc,
где m > 1, z
i
∈ (N ∪ T )
∗
, 1 6 i 6 m. Следовательно, w = zz
0
тогда и только тогда, когда n = m + 1, S = w
1
, z
i
= w
i+1
для
1 6 i 6 m, w
0
i
= mi(z
i
), 1 6 i 6 m, и z
0
= w
0
n
. Это означает, что
w
0
i
= mi(z
i
) = mi(w
i+1
), 1 6 i 6 n, т. е.
S = w
1
=⇒ w
2
=⇒ . . . =⇒ w
n
=⇒ mi(z
0
)
в грамматике G. Таким образом, mi(z
0
) ∈ L(G), откуда имеем
L
2
\L
1
= mi
L(G)
= L, что и завершает доказательство.
3.2. Характеризации рекурсивно перечислимых языков 135
Следствие 3.3. Любой язык из RE есть образ пересечения
двух линейных языков при слабом кодировании.
Доказательство. Видоизменим приведенную выше конструк-
цию языка L
1
, считая, что в зап иси блока x
n
v
n
y
n
из его
определения участвуют штрихованные версии символов из T .
Пусть T
0
— множество всех таких штрихованных символов.
Вместо L
2
возьмем язык L
2
T
0∗
. Обозначим получившиеся язы-
ки через L
0
1
и соответственно L
0
2
. Они, очевидно, линейны, и
x ∈ L
0
1
∩ L
0
2
в том и только в том случае, когда x = x
1
cccx
0
2
,
где x
1
∈ (N ∪ T ∪ {c})
∗
, x
0
2
∈ T
0∗
и притом x
2
∈ L
2
\L
1
. Если
определить слабое кодирование h правилами h(a) = λ для
a ∈ N ∪ T ∪ {c} и h(a
0
) = a для a ∈ T , то очевидно, что
h(L
0
1
∩ L
0
2
) = mi
L(G)
= L.
Для ОПМ g = (K, V
1
, V
2
, s
0
, F, P ), в которой V
1
= V
2
, можно
определить отображение g
∗
: V
∗
1
−→ P(V
∗
1
) правилом
g
∗
(w) = {z ∈ V
∗
1
| найдутся такие w
1
, . . . , w
n
∈ V
∗
1
, n > 2,
что w
i
∈ g(w
i−1
), 2 6 i 6 n, w = w
1
, z = w
n
} ∪ {w}.
Можно сказать, что g
∗
есть итерация ОПМ-отображения g.
Теорема 3.14. Каждый язык L ∈ RE, L ⊆ T
∗
представим в
виде L = g
∗
(a
0
)∩T
∗
, где g = (K, V, V, s
0
, F, P ) — ОПМ и a
0
∈ V .
Доказательство. Возьмем грамматику G = (N, T, S, P ) ти-
па 0. Без ограничения общности можно предполагать, что S
не появляется в правых частях правил из P . Построим ОПМ
g = (K, N ∪ T, N ∪ T, s
0
, F, P ),
K = {s
0
, s
1
} ∪ {[x] | x ∈ Pref(u) − {λ}, u → v ∈ P },
F = {s
1
},
P = {s
0
a → as
0
| a ∈ N ∪ T }
∪ {s
0
a
1
→ [a
1
] | u → v ∈ P, u = a
1
u
0
,
a
1
∈ N ∪ T, u
0
∈ (N ∪ T )
∗
}
∪ {[x]a → [xa] | xa ∈ Pref(u) − {u}, u → v ∈ P, a ∈ N ∪ T,
x ∈ (N ∪ T )
∗
}
∪ {[x]a → vs
1
| xa = u, u → v ∈ P, a ∈ N ∪ T, x ∈ (N ∪ T )
∗
}
136 3. Введение в теорию языков
∪ {s
0
a → vs
1
| a → v ∈ P, a ∈ N}
∪ {s
1
a → as
1
| a ∈ N ∪ T }.
Ясно, что каждый шаг работы ОПМ g моделирует п римен ение
некоторого правила из P . Отсюда g
∗
(S) ∩ T
∗
= L(G).
Перейдем теперь к рассмотрению ряда сильных (и по-
лезных для некоторых и з последующих глав) результатов о
представлении рекурсивно перечислимых языков, использую-
щих множества совпадений морфизмов. Для пары морфизмов
h
1
, h
2
: V
∗
−→ U
∗
их множество совпадений есть
EQ(h
1
, h
2
) = {w ∈ V
∗
| h
1
(w) = h
2
(w)}.
Теорема 3.15. Лю бой рекурсивно перечислимый язык L ⊆ T
∗
представим в виде L = pr
T
(EQ(h
1
, h
2
) ∩ R), где h
1
, h
2
— мор-
физмы, R — регулярный язык, pr
T
— проекция на алфавит T .
Доказательство. Рассмотрим грамматику G = (N, T, S , P ) ти-
па 0 и допустим, что продукции из P взаимно однозначным
образом помечены элементами множества Lab.
Рассмотрим алфавиты
V
1
= N ∪ T ∪ {c},
V
2
= N ∪ T ∪ Lab ∪ T
0
∪ {B, F, c},
где T
0
= {a
0
| a ∈ T }.
Определим морфизмы h
1
, h
2
: V
∗
2
−→ V
∗
1
правилами:
h
1
(B) = Sc, h
2
(B) = λ,
h
1
(c) = c, h
2
(c) = c,
h
1
(p) = v, h
2
(p) = u для p : u → v ∈ P,
h
1
(A) = A, h
2
(A) = A для A ∈ N,
h
1
(a
0
) = a, h
2
(a
0
) = a для a ∈ T,
h
1
(a) = λ, h
2
(a) = a для a ∈ T,
h
1
(F ) = λ, h
2
(F ) = c.
Наконец, рассмотрим регулярный язык
R = {B}((N ∪ T
0
)
∗
Lab(N ∪ T
0
)
∗
{c})
+
T
∗
{F }.
Идея конструкции состоит в следующем. Каждая строка из
L(G) появляется как заключительная строка некоторого выво-
3.2. Характеризации рекурсивно перечислимых языков 137
да D по правилам грамматики G. На строке w(D), кодирующей
вывод D, морфизмы h
1
, h
2
совпадают: h
1
w(D)
= h
2
w(D)
.
Однако морфизм h
1
«обгоняет» h
2
на префиксах строки w(D),
и h
2
«догоняет» h
1
только в самом конце. Проекция pr
T
, опре-
деляемая правилами h(a) = a при a ∈ T и h(α) = λ при
α ∈ V
1
− T , стирает все, кроме конечного результата. Язык
R используется для отбора строк прави льн ой фор мы.
Используя эти пояснения, читатель может убедиться, что
L(G) = pr
T
(EQ(h
1
, h
2
) ∩ R). (Детали доказательства можно
найти в [307].)
Следующий вариант этой теоремы используется в главе 4.
Теорема 3.16. Для любого рекурсивно перечислимого языка
L ⊆ T
∗
существуют два λ-свободных морфизма h
1
, h
2
, регу-
лярный язык R и проекция pr
T
такие, что
L = pr
T
h
1
EQ(h
1
, h
2
)
∩ R
.
Доказательство. Рассмотрим грамматику G = (N, T, S , P ) ти-
па 0, продукции которой взаимно однозначным образом поме-
чены элементами множества Lab. Без ограничения общности
можно предположить, что v 6= λ в каждой продукции p : u → v
из P , кроме продукции S → λ в случае, когда λ ∈ L(G).
Пусть T
0
= {a
0
|a ∈ T }, T
00
= {a
00
|a ∈ T }, Lab
0
= {p
0
|p ∈ Lab}.
Удобно ввести еще морфизм d : (N ∪ T )
∗
−→ (N ∪ T
0
)
∗
такой,
что d(A) = A при A ∈ N и d(a) = a
0
при a ∈ T . Заметим,
что d является биекцией, а, значит, существует обратное к d
отображение d
−1
.
Пусть
V
1
= N ∪ T ∪ T
0
∪ {B, F, c},
V
2
= N ∪ T ∪ T
00
∪ Lab ∪ Lab
0
∪ {B, F, c, c
0
},
138 3. Введение в теорию языков
где B, F, c, и c
0
— новые символы. Зависящие от G морфизмы
h
1
, h
2
: V
∗
2
−→ V
∗
1
определяются следующим образом:
h
1
(B) = BSc, h
2
(B) = B,
h
1
(c) = c, h
2
(c) = c,
h
1
(p) = d(v), h
2
(p) = d(u) для p : u → v ∈ P,
h
1
(p
0
) = v, h
2
(p
0
) = d(u) для p : u → v ∈ P,
h
1
(A) = A, h
2
(A) = A для A ∈ N,
h
1
(a
0
) = a
0
, h
2
(a
0
) = a
0
для a
0
∈ T
0
,
h
1
(a
00
) = a, h
2
(a
00
) = a
0
для a
00
∈ T
00
,
h
1
(a) = F, h
2
(a) = a, для a ∈ T,
h
1
(c
0
) = F, h
2
(c
0
) = c,
h
1
(F ) = F, h
2
(F ) = F F.
Кроме того, рассмотрим регулярный язык
R = {BS}({c}(N ∪ T
0
)
∗
)
∗
{c}T
∗
{F }
+
.
Заметим, что u, v 6= λ во всех п рав илах u → v ∈ P . Таким
образом, и h
1
, и h
2
— λ-свободные морфизмы. Е сли λ ∈ L,
добавим еще один символ e в V
2
и положим
h
1
(e) = h
2
(e) = BScF.
Легко видеть, что при этом мы не добавляем новых слов к
h
1
EQ(h
1
, h
2
)
∩ R. Следовательно, в дальнейших рассужде-
ниях можно считать, что λ 6∈ L.
Доказательство того, ч то L(G) ⊆ pr
T
h
1
EQ(h
1
, h
2
)
∩ R
сходно с обоснованием аналогичного включения в теореме 3.15.
Обратно, пусть w ∈ pr
T
h
1
EQ(h
1
, h
2
)
∩ R
, т. е. w есть
pr
T
(y) для некоторой ст роки y ∈ h
1
EQ(h
1
, h
2
)
∩ R. Тогда по
определению языка R эта строка имеет вид
y = BScy
1
cy
2
c · · · cy
t
F
l
,
где y
1
, . . . , y
t−1
∈ (N ∪ T
0
)
∗
, y
t
∈ T
∗
, l > 0. Пусть y = h
1
(x) для
некоторой строки x ∈ EQ(h
1
, h
2
). Тогда
x = Bx
1
cx
2
c · · · cx
t
c
0
x
t+1
F
m
,
причем h
2
(x
1
) = S, h
1
(x
i
) = h
2
(x
i+1
) = y
i
для 1 6 i 6 t, l = 2m,
h
1
(x
t+1
) = F
m−1
. Заметим, что если x
j
= x
j+1
при некотором
3.2. Характеризации рекурсивно перечислимых языков 139
j, 1 6 j < t, то, вычеркнув x
j
c из x, получим такую строку x
0
,
что pr
T
(h
1
(x
0
) ∩ R) = pr
T
(h
1
(x) ∩ R) = w . Таким образом, без
ограничения общности можно предполагать, что x
j
6= x
j+1
для
всех j, 1 6 j < t. (Ясно, что x
t
6= x
t+1
.)
Следующие утверждения очевидны:
(1) x
1
= p (или x
1
= p
0
при t = 1) для некоторого p : S → z ∈ P ,
(2) x
i
∈ (N ∪ T
0
∪ Lab)
∗
Lab(N ∪ T
0
∪ Lab)
∗
для 2 6 i < t,
(3) x
t
∈ (N ∪ T
0
∪ Lab
0
)
∗
,
(4) x
t+1
∈ T
∗
,
(5) h
1
(x
i
) = y
i
и h
2
(x
i
) = y
i−1
для 1 6 i 6 t (здесь y
0
= S).
Из (2) и (5) и определения морфизмов h
1
и h
2
следует, что
d
−1
(y
i−1
) =⇒
+
G
d
−1
(y
i
)
при 2 6 i 6 t − 1. Кроме того, заметим, что S =⇒
G
d
−1
(y
1
)
и d
−1
(y
t−1
) =⇒
+
G
y
t
. Следовательно, S =⇒
+
G
y
t
, т. е. y
t
∈ L(G).
Поскольку w = pr
T
(y) = y
t
, мы доказали, что w ∈ L.
Отметим различие между представлениями в теоремах 3.15
и 3.16: в первом случае язык L получается как проекция пересе-
чения множества совпадений с регулярным языком, тогда как
во втором случае L является проекцией пересечения регуляр-
ного языка с образом множества совпадений относительно
одного из определяющих его морфизмов.
Очень полезно такое следствие теоремы 3.15. Рассмотрим
алфавит V вместе с его копией V = {¯a | a ∈ V }. Язык
T S
V
=
[
x∈V
∗
(x t⊥ ¯x)
называется языком перетасованных копий над V . (Через ¯x обо-
значается строка, полученная из строки x ∈ V
∗
заменой каж-
дого символа на его копию с чертой.)
Если определить морфизм h : (V ∪ V )
∗
−→ V
∗
правилами
h(a) = λ при a ∈ V,
h(¯a) = a, при a ∈ V,
140 3. Введение в теорию языков
то л егко видеть, что T S
V
= EQ(h, pr
V
). Это делает правдопо-
добным следующий результат.
Теорема 3.17. Лю бой рекурсивно перечислимый язык L ⊆ T
∗
представим в виде L = pr
T
(T S
V
∩ R
0
) для подходящих алфа-
вита V и регулярного языка R
0
.
Доказательство. В доказательстве теоремы 3.15 можно пред-
полагать, что алфавит V
1
области значения морфизмов h
1
, h
2
не пересекается с алфавитом V
2
области их определения. (Это-
го всегда можно добиться переименованием букв алфавита V
1
.)
Определим морфизм g : V
∗
2
→ (V
1
∪ V
1
)
∗
правилом
g(a) = ah
1
(a)h
2
(a) для каждого a ∈ V
2
,
а регулярный язык R
0
⊆ (V
1
∪ V
1
∪ V
2
)
∗
— равенством
R
0
= g(R) t⊥ V
∗
2
.
Рассмотрим теперь алфавит V = V
1
∪V
2
. Из приведенных опре-
делений непосредственно следует равенство
pr
T
(T S
V
∩ R
0
) = pr
T
(EQ(h
1
, h
2
) ∩ R),
и потому доказываемое представление вытекает из представ-
ления, указанного в теореме 3.15.
Отметим сходство данного представления рекурсивно пере-
числимых языков с представлением Хомского–Шютценберже
для контекстно-свободных языков (теорема 3.11); роль язы-
ков Дика играют теперь языки перетасованных копий.
В указанном представлении язык T S
V
зависит от языка L.
Этого можно избежать следующим образом. Возьмем какое-ни-
будь кодирование f : V −→ {0, 1}
∗
, например, f(a
i
) = 01
i
0, где
a
i
— это i-й символ алфавита V при некотором фиксированном
упорядочении. Язык f(R
0
) регулярен. ОПМ может моделиро-
вать пересечение с регулярным языком, проекцию pr
T
, а также
декодирование элементов из f(TS
V
). Итак, мы получаем
Следствие 3. 4. Для л юбого рекурсивно перечислимого языка
L существует такая ОПМ g
L
, что L = g
L
(T S
{0,1}
).
Следовательно, каждый рекурсивно перечисл имый язык
может быть получен с помощью последовательного преоб-