Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений

Подождите немного. Документ загружается.

10.1. Сплетающие грамматиче ски е системы 421

правил, используемых в его компонентах? Что можно сказать

о системах с регулярными или право-линейными правилами?

У эт их систем также довольно большие возможности. Доказа-

тельства двух следующих включений можно найти в [113]:

LIN ⊆ SGS

(REG),

CF ⊆ SGS

(REG).

Оба эти включения являются собственными.

Действительно, рассмотрим сплетающую грамматическую

систему

Γ = ({S

, S

, A, B, C}, {a, b, c, d}, (S

, P

), (S

, P

), R)

= {S

→ aS

, S

→ aA, B → cB, C → c},

= {S

→ dB, B → bB, A → cA, A → cC},

R = {a#A$b#B, c#B$d#b}.

Выводы в Γ происходят следующим образом. После началь-

ной переписывающей фазы,

, S

) =⇒ (aS

, dB)

=⇒

∗

n+1

, db

=⇒ (a

n+2

A, db

n+1

B),

n > 0, или состоящей только из одного шага,

, S

) =⇒ (aA, dB),

мы должны выполнить сплетение в соответствии с первым пра-

вилом. Это единственный способ достичь терминальной стро-

ки, поскольку переписывания не могут избавить от A первую

компоненту, а от B — вторую. Во втором случае ни одно спле-

тение не может быть выполнено. В первом же мы получаем

n+2

|A, db

n+1

|B) |= (a

n+2

B, db

n+1

A).

Нужно сделать, по крайней мере, один переписывающий шаг,

поскольку сейчас нельзя использовать ни одно правило спле-

422 10. Распределенные H-системы

тения:

n+2

B, db

n+1

A) =⇒

∗

n+2

B, db

n+1

A), m > 1.

Если снова сплести, применив второе правило, то в первую

компоненту будет введен символ A, что заблокирует работу

системы:

n+2

|B, d|b

n+1

A) |= (a

n+2

n+1

A, dB).

Следовательно, мы должны переписать A на cC во второй ком-

поненте. Символ C не может быть переписан в P

, значит,

должно быть немед ленн о выполнено сплетение, после чего C в

первой компоненте будет заменен на c:

n+2

B, db

n+1

A) =⇒ (a

n+2

m+1

|B, d|b

n+1

m+1

|= (a

n+2

m+1

n+1

m+1

C, dB) =⇒ (a

n+2

m+1

n+1

m+2

, dbB).

Следовательно,

L(Γ) = {a

n+1

m+1

| n > 1, m > 2}.

Ясно, что этот язык не является контекстно-свободным.

На самом деле сплетающие грамматические системы с тре-

мя регулярными компонентами «почти характеризуют» рекур-

сивно перечислимые языки.

Теорема 10.2. Каждый язык L ⊆ T

∗

, L ∈ RE, может

быть представлен в виде L = L

∩ T

∗

для некоторого

∈ SGS

(REG).

Доказательство. Возьмем L, как и в доказательстве теоре-

мы 10.1, порожденный грамматикой в нормальной форме Геф-

ферта G = (N, T, S, P ) с N = {S, A, B, C}. Мы построим спле-

тающую грамматическую систему, для которой символы из N

будут считаться терминальными.

Рассмотрим систему

Γ = (N

, T

, (S

, P

), (S

, P

), (S

, P

), R),

где

= {S

, S

, X, X

, Y, Z, Z

, Z

= {S, A, B, C} ∪ T ∪ {d

, d

10.1. Сплетающие грамматиче ски е системы 423

= {S

→ SY, Y → d

Y, X → d

, Z → d

= {S

→ d

X , X → d

Z, Y → d

Y, Z

→ d

Z, Z

→ d

}

∪ {X → αX | α ∈ {S, A, B, C} ∪ T },

= {S

→ d

X , X

→ d

X , X → d

X},

R = {#S$d

#xX | S → x ∈ P }

∪ {#d

S#, d

#Sd

#X , #ABC$d

#Z,

ABC#, #d

#}.

Идея этой конструкции состоит в следующем.

Каждый вывод в Γ имеет две фазы: в первой и митир уется

использование правил S → x из P , а во второй — правила

ABC → λ. На переход от первой фазы к второй указывает

замена X на Z во второй компоненте.

В первой фазе P

недетерминированным п утем порождает

строку d

xX при некотором x ∈ ({S, A, B, C}∪T )

∗

. Такая стро-

ка может быть использована в сп летен ии, если только S → x —

правило из P . Таким образом, P

играет роль производителя

правых частей для правил из P . С помощью правил сплетения

из R, не содержащих символа Z и его штрихованных вариан-

тов, мы можем далее имитировать применение правила S → x

для переписывания в первой компоненте единственного вхо-

ждения S. Переписывающие шаги необходимы между опера-

циями сплетени я именно для изменения нетерминальных сим-

волов. Во время таких переписываний в P

и P

вводится фик-

тивный терминальный символ d

, а в P

— символ d

. Для того

чтобы повторять этот процесс, не производя строк-паразитов

(здесь имеются в виду строки из (L(Γ) ∩ T

∗

) − L), нам требу-

ется третья компонента. Ее роль состоит в «очистке» второй

компоненты (см. объяснения ниже).

После введения символа Z мы начинаем имитацию прави-

ла ABC → λ. Эта имитация осуществляется так же, как и в

доказательстве теоремы 10.1. Ни одно правило S → x из P не

может быть смоделировано во время этой фазы. Это не явля-

ется ограничением общности, поскольку вывод в грамматике в

нормальной форме Гефферта может без ущерба для порожда-

424 10. Распределенные H-системы

емой строки быть переделан так, чтобы сначала применялись

контекстно-свободные правила, а затем стирающее правило.

Исследуем подробно работу Γ. Мы начинаем с

, S

) =⇒ (SY, d

X , d

X).

Никакое сплетение не может быть выполнено (1) до получения

во второй компоненте строки x, такой, ч то S → x ∈ P , или

(2) до введения символа Z. Для сплетения в случае (2) нам в

строке первой компоненты нужна, по крайней мере, подстрока

ABC. Следовательно, мы должны продолжать по случаю (1):

(SY, d

X , d

X) =⇒

∗

(Sd

Y, d

xX , d

n+1

X), n = |x| > 1.

Процесс блокируется, когда x нельзя увеличить этим способом

так, чтобы получить строку xx

с S → xx

∈ P (x

может быть

пустой строкой). Предположим, что S → x ∈ P . Тогда мы

можем выполнить сплетение:

(|Sd

Y, d

|xX, d

n+1

X) |= (xX, d

Y, d

n+1

X).

Если мы продолжим

(xX , d

|Sd

Y, d

n+1

|X) |= (xX, d

X , d

n+1

Y ),

то система окажется блокированной, никакое п ереп исыван ие

или сплетение невозможно. Мы должны вместо этого перепи-

сать, а затем сплести:

(xX, d

Y, d

n+1

X) =⇒ (x|d

, d

S|d

n+1

Y, d

n+2

|= (xd

n+1

Y, d

, d

n+2

X).

Единственное возможное продолжение — снова сплетение:

(xd

n+1

Y, d

|Sd

, d

n+2

|X) |= (xd

n+2

Y, d

X , d

n+2

Мы вернулись к конфигурации с нетерминальными Y, X в

первых двух компонентах и с «очищенной» строкой во второй

компоненте, снова равной d

X. Можно повторить этот процесс.

Продемонстрируем произвольный шаг такого вида. В слу-

чае фиктивных символов d

, d

мы будем записывать d

∗

, d

∗

чтобы указать на присутствие некоторого числа их копий, кон-

кретное значение которого нам не важно. Подобная запись ка-

10.1. Сплетающие грамматиче ски е системы 425

сается блоков d

∗

в третьей компоненте. Итак, мы имеем:

(u|Svd

∗

Y, d

|xX, (d

∗

)

∗

|= (uxX, d

Svd

∗

Y, (d

∗

)

∗

=⇒ (ux|d

, d

S|vd

∗

Y, (d

∗

)

∗

|= (uxvd

∗

Y, d

|Sd

, (d

∗

)

∗

|X) (∗)

|= (uxvd

∗

Y, d

X , (d

∗

)

∗

)

=⇒

∗

(uxvd

∗

Y, d

yX, (d

∗

)(d

∗

X).

Процесс идет так же, как описано выше в общем случае.

Заметим, что в конфигурации (∗) можно также сплести

строки второй и третьей компонент при условии v = λ, но по-

сле такой операц ии система будет блокирована, никакое пере-

писывание (из-за Y в третьей компоненте) или сплетение осу-

ществить будет невозможно.

Если во второй компоненте присутствует X, мы тоже мо-

жем воспользоваться правилом X → d

Z, определяющим пе-

реход к второй фазе вывода, в которой подстроки ABC могут

быть удалены из строки первой компоненты:

(uABCvd

∗

Y, d

wX, −X) =⇒ (uABCvd

∗

Y, d

Z, −X)

(в дальнейшем, третья компонента не играет никакой роли, и

мы будем игнорировать ее строку, только проставляя нетер-

минальный X, и имея в виду, что ни одно сплетение не может

задействовать эту строку; переписывающие же операции могут

выполняться когда угодно, т.е. никаких ограничений на длину

вывода не накладывается). Мы должны сплести

(u|ABCvd

∗

Y, d

|Z, −X) |= (uZ, d

ABCvd

∗

Y, −X).

Никакое дальнейшее сплетение невозможно, мы вынуждены

переписывать

=⇒ (ud

, d

ABCvd

∗

Y, −X).

Теперь мы должны сплетать:

(u|d

, d

ABC|vd

∗

Y, −X)

|= (uvd

∗

Y, d

ABCd

, −X). (∗∗)

426 10. Распределенные H-системы

После переписывания

=⇒ (uvd

∗

Y, d

ABCd

Z, −X)

во второй компоненте вновь появляется подстрока d

Z, присут-

ствующая во второй компоненте. Если в uv есть еще вхожде-

ния ABC, то можно удалить их, снова осуществляя сплетение.

Заметим, что при каждом таком повторе выполняются два пе-

реписывания, и значит, строка в первой компоненте имеет вид

uvd

Y при некотором i > 2.

Таким образом могут быть удалены все подстроки ABC.

Однако на каком-то этапе при достижении конгруэнции вида

(∗∗), может быть применено правило Z

→ d

из P

. Это

подготавливает удаление нетерминального символа в первой

компоненте:

(uvd

Y, zZ

, −X) =⇒ (uvd

Y, zd

|, −X)

|= (uvd

, zd

Y, −X).

Возникает терминальная (с точки зрения Γ) строка.

Заметим, что правило #d

# не может быть приме-

нено для сплетения строк в третьей и второй компонентах,

поскольку строка в третьей компоненте не содержит подстро-

ку d

(это можно легко провер ить путем исследования выво-

дов, обсуждавшихся выше).

Теперь ясно, что если все подстроки ABC были удалены, а

последнее сплетение было осуществлено перед суффиксом d

(и значит, j = 0 в предыдущей записи), то мы получаем строку

из L(G). Следовательно, L(G) = L(Γ) ∩ T

∗

Следствие 10.1. Для каждого семейства F L из RE, замкну-

того относительно пересечения с регулярными множества-

ми, имеем SGS

(REG) − F L 6= ∅.

Этими свойствами обладают многие важные семейства из

основной иерархии Хомского, области регулируемых перепи-

сываний и теории Линденмайера: языки, порожденные мат-

ричными грамматиками с проверкой вхождений или без нее,

но без использования λ-правил, языки, порожденные матрич-

10.2. Взаимодействующие распр еде лен ные H-системы 427

ными грамматиками с λ-правилами и без проверки вхождений,

ET 0L, CS, рекурсивные и т. д. Семейство SGS

(REG) содер-

жит языки, отличающиеся от каждого из них, что еще раз

демонстрирует возможности кооперации в духе параллельных

взаимодействующих грамматических систем, объединяемой с

возможностями операции сплетения.

Мы не знаем, выполняется ли для некоторого n равенство

RE = SGS

(REG). Тем не менее, если мы позволим приме-

нять цепные п рави ла X → Y и правила вида X → xY для

нетерминальных символов X, Y и терминальной строки x, то

сможем пол учить характеризацию RE. Доказательство следу-

ющего результата можно найти в [113].

Теорема 10.3. RE = SGS

(RL).

Мы рассмотрели сплетающие грамматические системы

смешанного типа. Распределенные H-системы, использующие

только операции сплетения (и не использующие при этом

операции переписывания), будут представлены в следующих

трех разделах.

10.2 Взаимодействующие распределенные

H-системы

Модель, рассматриваемая нами в этом разделе, — аналог па-

раллельных грамматических систем с передачей по команде:

компоненты работают на основе сплетения, а связываются, по-

сылая друг другу строчки, которые проходят некие заранее

определенные фильтры.

Взаимодействующая распределенная H-система (степени

n > 1) — это структ ура

Γ = (V, T, (A

, R

, V

), . . . , (A

, R

, V

)),

где

1. V — алфавит,

2. T ⊆ V ,

3. A

— конечные языки над V ,

4. R

— конечные множества правил сплетения над V , а

428 10. Распределенные H-системы

5. V

⊆ V , 1 6 i 6 n.

Каждая тройка (A

, R

, V

), 1 6 i 6 n, называется компо-

нентой Γ; A

, R

, V

соответственно — множество аксиом, мно-

жество правил сплетения и селектор (или фильтр) компонен-

ты i; T — терминальный алфавит системы.

Положим

B = V

∗

−

[

i=1

∗

Пара σ

(i)

= (V, R

) — основная H-схема, ассоциированная c

i-й компонентой системы.

Конфигурацией системы называется n-кортеж (L

, . . . , L

⊆ V

∗

, 1 6 i 6 n. Язык L

будем называть содержимым

i-й компоненты, воспри нимая компоненты как пробирки, где

выполняются операции сплетения.

Для двух конфигураций (L

, . . . , L

), (L

, . . . , L

), мы опре-

деляем

, . . . , L

) =⇒ (L

, . . . , L

)

тогда и только тогда, когда

[

j=1

(σ

(j)∗

) ∩ V

∗

) ∪ (σ

(i)∗

) ∩ B)

для каждого i, 1 6 i 6 n. Иными словами, содержимое каж-

дой компоненты сплетается в соответствии с ассоциированным

множеством правил (мы переходим от L

к σ

(i)∗

), 1 6 i 6 n),

и результат перераспределяется среди n компонент, согласно

селекторам V

, . . . , V

. Часть, которая не может быть передана

(которая не принадлежит никакому V

∗

, 1 6 i 6 n) остается в

компоненте. Никаких ограничений на алфавиты V

не накла-

дывается. В частности, они могут пересекаться, при этом, если

некая строка из σ

(j)∗

) принадлежит нескольким языкам V

∗

то копии этой строки будут распределены по всем компонен-

там i с таким свойством.

10.2. Взаимодействующие распр еде лен ные H-системы 429

Язык, порождаемый Γ, определяется следующим образом:

L(Γ) = {w ∈ T

∗

|w ∈ L

для некоторых L

, . . . , L

⊆ V

∗

таких, что (A

, . . . , A

) =⇒

∗

, . . . , L

)}.

Другими словами, первая компонента системы п ред назначена

на роль главной, и язык Γ есть множество всех терминальных

строк, порожденных ею (или собранных в ней посредством пе-

редач).

Мы обо значаем через CDH

семейство языков, порожден-

ных взаимодействующими распределенными H-системами сте-

пени не выше n, n > 1. Если n не определено, мы заменяем

нижний индекс n на ∗.

Можно рассмотреть другой вариант, в котором в качестве

языка, порождаемого Γ, берется объединение всех языков, по-

рождаемых ее компонентами. Подобный подход обсуждался в

замечании 10.1, но здесь исследовать его мы не будем.

Взаимодействующие распределенные H-системы характе-

ризуют RE. Прежде чем доказать этот результат, исследуем

пример.

Рассмотрим систему

Γ = ({a, b, c, d, e}, {a, b, c}, (A

, R

, V

), (A

, R

, V

)),

= {cabc, ebd, dae},

= {b#c$e#bd, da#e$c#a},

= {a, b, c},

= {ec, ce},

= {b#d$e#c, c#e$d#a},

= {a, b, d}.

Единственно возможные сплетения в первой компоненте та-

ковы:

b|c, e|bd) |= (x

bbd, ec) для x

∈ {a, b, c, d, e}

∗

(da|e, c|ax

) |= (daax

, ce) для x

∈ {a, b, c, d, e}

∗

К строкам x

bc, cax

добавляется таким образом еще по одно-

му символу b и a соответственно (при этом в обоих случаях c

430 10. Распределенные H-системы

заменяется на d). Мы начинаем с cabc. Из второй компоненты

передаются строки над {a, b, c}. Из первой же можно переда-

вать во вторую только строки над {a, b, d}. Это означает, что,

начав со строки ca

c, n, m > 1 (первоначально, n = m = 1),

мы произведем в первой компоненте da

n+1

m+1

d. Больше ниче-

го сплести мы здесь не можем, и строка передается во вторую

компоненту. При этом должны быть применены оба правила

из R

, иначе из строки не исчезнет символ c. Во второй компо-

ненте можно выполнить:

(αa

|d, e|c) |= (αa

c, ed), α ∈ {c, d},

(c|e, d|a

α) |= (ca

α, de), α ∈ {c, d}.

Строку ca

c разрешено передавать в первую компоненту,

и значит, процесс можно повторить.

Таким образом, мы получаем язык

L(Γ) = {ca

c | n > 1},

не являющийся регулярным языком.

Следовательно, CDH

− REG 6= ∅.

Теорема 10.4. RE = CDH

= CDH

∗

для всех n > 3.

Доказательство. Включения CDH

⊆ CDH

n+1

⊆ CDH

∗

⊆

RE, n > 1, очевидны. Мы должны доказать лишь включение

RE ⊆ CDH

Рассмотрим грамматику G = (N, T, S, P ) типа 0. Возьмем

новый символ B и обозначим для удобства

N ∪ T ∪ {B} = {D

, D

, . . . , D

Так как N 6= ∅, T 6= ∅, имеем n > 3. Построим взаимодейству-

ющую распределенную H-систему

Γ = (V, T, (A

, R

, V

), (A

, R

, V

), (A

, R

, V

))

V = N ∪ T ∪ {X, Y, X

, Y

, Z, B}

∪ {X

, Y

| 0 6 i 6 2n},

= {XBSY } ∪ {ZvY | u → v ∈ P }