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

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

7.4. Расширенные H-си стем ы 321

тельно, работа γ

состоит в точности из производства аксиом

γ и последующего применения правил из R. Это означает, что

L(γ

) ⊆ L(γ), и значит, мы имеем равенство L(γ) = L(γ

) и

включение EH

(F IN, REG) ⊆ lmax

−1

(2).

Эта граница неулучшаема, так как lmax

−1

(1) строго содер-

жится в lmax

−1

(2). Действительно, возьмем язык L = {aa} и

предположим, что L = L(γ) для некоторого γ = (V, {a}, A, R)

при A ⊆ V . Поскольку все аксиомы имеют длину 1, символ a

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

тельно, a ∈ A. Это означает, что a ∈ L(γ), в противоречи е с

равенством L = L(γ).

Схлопывается (даже до одного уровня) и и ерархия, связан-

ная с числом аксиом.

Теорема 7.9. nrax

−1

(1) = EH

(F IN, REG).

Доказательство. Дл я данной H-системы γ = (V, T, A, R) с

A = {w

, w

, . . . , w

}, n > 2, построим H-систему

= (V ∪ {c, c

}, T, {w }, R

где c, c

— новые символы, и

w = c

· · · cw

= R ∪ {#c

c$c#c

, #c$c

#, #c

$c#}.

Докажем, что L(γ) = L(γ

Включение ⊆ получить легко: применяя правило #c

c$c#c

мы выводим (w, w) ` c

; используя правило #c$c

#, из каждой

строки вида xc (и из w) можно удалить самый правый сим-

вол c (соответственно, суффикс cc

), имея вторым термом c

;

используя же правило #c

$c#, из всякой строки вида x

можно выделить суффикс x

. Поэтому все аксиомы γ могут

быть выделены из w. Применяя правила R мы теперь можем

получить любую строку из L(γ).

Обратно, нетрудно видеть, что на любом шаге все возника-

ющие строки не выходят за пределы множества {с

} ∪ X, где

X = {gu

· · · cu

h | g ∈ {λ, c

c},

h ∈ {λ, cc

}, s > 1, u

∈ σ

∗

(A), 1 6 i 6 s}.

322 7. Системы сплетения

Действительно, мы начинаем с аксиомы w, которая, очевид-

но, принадлежит X. С помощью первого правила из R

− R и

строк из нашего множества всегда строится с

, второе и тре-

тье правила не выводят за границы X. Остается проверить,

что и с помощью правила из R нельзя получи ть ничего нового.

Действительно, если к двум строкам x, y вида x = x

y = y

при x

, y

∈ V

∗

применить правило сплетения из

R на участках x

, y

, получим строку z = x

, такую, что

, y

) ` z

при z

∈ V

∗

. Если x, y ∈ X, то, очеви дно , и z ∈ X.

Таким образом мы доказали, что L(γ

) ⊆ X ∩ T

∗

. Из структу-

ры множества X легко понять, что X ∩ V

∗

⊆ σ

∗

(A). Поэтому,

L(γ

) ⊆ X ∩ T

∗

⊆ σ

∗

(A) ∩ T

∗

= L(γ).

Следствие 7. 2. nrax

−1

(1) = RE.

В доказательствах предыдущих теорем, уменьшая длины

аксиом, мы были вынуждены увеличивать их ч исло , и наобо-

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

зированы одновременно.

Если µ : GM −→ N — мера сложности порождающих меха-

низмов в данном классе GM, положим

(L) = min{µ(G) | L = L(G), G ∈ GM}.

Тогда для языка L определим

−1

(L) = {G ∈ GM | L = L(G), µ(G) = µ

(L)}

(множество оптимально порождающих L устройств из GM).

Будем говорить, что две меры µ

, µ

несовместны (в GM ), если

с помощью GM можно породить такой язык L, что

−1

(L) ∩ µ

−1

(L) = ∅.

(Данные две меры не могут быть одновременно минимизиро-

ваны для элементов из GM, порождающих язык L.)

Теорема 7.10. Меры nrax, lmax несовместны.

Доказательство. Рассмотрим произвольный язык L ⊆ a

∪b

такой, что alph(L) = {a, b}. Тогда по теореме 7.9 nrax(L) = 1.

Возьмем H-систему γ = (V, {a, b}, A, R) такую, что L = L(γ) и

A = {w}, w ∈ V

∗

. Докажем, что |w| > 3. Действительно, оба

7.5. Простые H-системы 323

символа a и b должны присутствовать в w, поскольку в про-

тивном случае они не смогут появиться в строках L(γ). Однако

ни одна из строк ab и ba не может быть аксиомой. Значит, в w

есть по крайней мере один символ из V − {a, b}, откуда |w| > 3.

С другой стороны, по теореме 7.8 lmax(L) = 2. Следова-

тельно, для таких языков L мы не сможем найти H-систему γ,

для которой nrax(γ) = 1 и lmax(γ) = 2 одновременно. Языки

L рассмотренного вида есть и в EH

(F IN, REG), и это заме-

чание завершает доказательство.

7.5 Простые H-системы

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

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

ванных на операции сплетения. Здесь, напротив, мы изучим до-

вольно специфический тип сплетающих систем. Неудивитель-

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

ное решение, что придает таким устройствам оп ред еленн ую ма-

тематическую привлекательность.

Простая H-система — это тройка

γ = (V, A, Q),

где V — алфавит, A — конечный язык над V и Q ⊆ V . Элемен-

ты A называются аксиомами, а элементы Q — маркерами.

Для x, y, z ∈ V

∗

и a ∈ Q пи шем

(x, y) `

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

, y = y

, z = x

при некоторых x

, x

, y

∈ V

∗

Следовательно, можно представлять, что для каждого мар-

кера a ∈ Q мы имеем правило сплетения r

= a#$a# (или

= #a$#a). Положим

= {r

| a ∈ Q}

и рассмотрим H-схему σ

= (V, R

). Тогда язык, порождае-

мый γ и обозначаемый L(γ), полагаем равным σ

∗

(A). (В этом

324 7. Системы сплетения

разделе мы опускаем нижний индекс 1 в σ

(L), σ

∗

(L), чтобы

избежать громоздких обозначений типа (σ

)

∗

(L).)

Пример. Рассмотрим простую H-систему

γ = ({a, b, c}, {abaca, acaba}, {b, c}).

Получаем

L(γ) = (abac)

a ∪ (abac)

∗

aba ∪ (acab)

a ∪ (acab)

∗

aca.

Действительно,

((abac)

a, acaba) `

(abac)

n−1

abacaba = (abac)

aba,

((abac)

aba, abaca) `

(abac)

abaca = (abac)

n+1

и аналогично для строк (acab)

a, (acab)

aca, и значит, уста нов-

лено включение ⊇.

Обратно, при сплетении двух строк вида (abac)

a, (acab)

(в самом начале n = 1) или (abac)

aba, (acab)

aca, мы отож-

дествляем в них либо подстроку aba, либо подстроку aca, и

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

Обозначим через SH семейство языков, порождаемых про-

стыми H-системами.

Легко могут быть доказаны следующие необходимые усло-

вия того, что язык лежит в SH.

Лемма 7.20. (i) Если язык L ∈ SH бесконечен, то суще-

ствует такое непустое множество Q ⊆ alph(L), что

(L) ⊆ L.

(ii) Если L ∈ SH, L ⊆ V

∗

, и a

⊆ L при некотором a ∈ V ,

то σ

{a}

(L) ⊆ L.

(iii) Если w ∈ V

, то w

∗

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

существует символ a ∈ V такой, ч то |w|

= 1.

Используя эти условия, можно показать, что следующие

языки не лежат в семействе SH:

= a

b ∪ b

= (aabb)

7.5. Простые H-системы 325

а язык L ⊆ a

∗

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

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

∗

, a

. Кроме того, мы получаем

Следствие 7. 3. Семейство SH является анти-AFL.

Поскольку каждая простая H-система является (нерасши-

ренной) конечной H системой особого типа, лемма 7.14 влечет,

что SH ⊆ REG. Ниже мы увидим, что этот результат можно

получить гораздо более простым способом как следствие тео-

ремы о представлении языков из SH. Включение SH ⊂ REG,

ввиду предыдущих контрпримеров, является собственным. Од-

нако SH и REG «эквивалентны по модулю кодирования».

Лемма 7.21. Каждый регулярный язык есть проекция языка

из семейства SH.

Доказательство. Пусть M = (K, V, s

, F, δ) — детерминиро-

ванный конечный автомат. Построим простую H-систему

γ = (K ∪ V, A, K),

где A = {s

b · · · s

r+1

| r > 0, s

∈ K, причем каж-

дое состояние s

, 0 6 i 6 r + 1, появляется максимум дважды,

r+1

∈ F , s

i+1

= δ(s

, a

i+1

) для 0 6 i 6 r}. Ясно, что A — конеч-

ное множество. Рассмотрим также проекцию h, определяемую

правилом h(a) = a для a ∈ V и h(s) = λ для s ∈ K.

Включение h(L(γ)) ⊆ L(M) следует из конструкции γ и

определения h. Обратное включение может быть л егко доказа-

но с помощью индукции по длине строк в L(M).

Лемма 7.22. Для каждого языка L ∈ SH существуют пять

конечных языков L

, L

и проекция h такая, что

L = h(L

∗

∩ L

∗

) ∪ L

Доказательство. Пусть γ = (V, A, Q) — простая H-система.

Для каждого a ∈ V рассмотрим новый символ a

. Обозначим

= {a

| a ∈ V } и определим

= {xa | xay ∈ A, x, y ∈ V

∗

, a ∈ Q},

= {a

xb | yaxbz ∈ A, x, y, z ∈ V

∗

, a, b ∈ Q},

= {a

x | yax ∈ A, x, y ∈ V

∗

, a ∈ Q},

326 7. Системы сплетения

= V ∪ {aa

| a ∈ V },

= {x ∈ A | |x|

= 0 для всех a ∈ Q},

h : (V ∪ V

)

∗

−→ V

∗

, h(a) = a, a ∈ V, и h(a

) = λ, a ∈ V.

Мы утверждаем, что L(γ) = h(L

∗

∩L

∗

)∪L

. Обозначим

через B правую часть этого равенства.

(1) L(γ) ⊆ B. Из определений ясно, что достаточно дока-

зать два факта: (i) B включает множество A, и (ii) σ

(B) ⊆ B.

(i) Если x ∈ A и |x|

= 0 для всех a ∈ Q, то x ∈ L

⊆ B.

Если x ∈ A и x = x

, a ∈ Q, то x

a ∈ L

, a

∈ L

, следо-

вательно, x

∈ L

. Ясно, что x

∈ L

∗

. Поскольку

h(x

) = x

= x, имеем x ∈ B. Следовательно, A ⊆ B.

(ii) Возьмем две строки x, y ∈ B. Если одна из них из L

то σ

(x, y) = {x, y} ⊆ B.

Возьмем такие строки x

, y

∈ L

∗

∩ L

∗

, что x = h(x

y = h(y

), z ∈ σ

(x, y) и (x, y) `

z при некотором a ∈ Q. Тогда

x = z

, y = z

, где z = z

= x

· · · x

k+1

, k > 1,

= y

· · · y

s+1

, s > 1,

где a

, b

∈ Q, x

, y

∈ V

∗

, a

i−1

, b

i−1

∈ L

для всех i и

, y

∈ L

, a

k+1

, b

s+1

∈ L

. Тогда

x = x

· · · x

k+1

, y = y

· · · y

s+1

Определим теперь тот маркер a в x, соответственно в y, кото-

рый использовался в сплетении (x, y) `

Если a = a

, то

= x

· · · x

i−1

, z

= x

i+1

· · · a

k+1

Если a

6= a при всех 1 6 i 6 k, то тогда x

= x

. При

i = 1 мы имеем x

a ∈ L

и a

∈ L

. При 1 < i < k +1 имеем

i−1

a ∈ L

, a

i+1

∈ L

. При i = k + 1 имеем a

k+1

a ∈ L

и a

k+1

∈ L

. В любом случае можно найти такую строку

= w

∈ L

∗

∩ L

∗

, что x = h(x

Аналогично, есть строка y

= w

∈ L

∗

∩L

∗

такая,

что y = h(y

). Для z

= w

, очевидно, имеем z = h(z

) и

7.5. Простые H-системы 327

∈ L

∗

∩ L

∗

. Следовательно, z ∈ B, что завершает дока-

зательство свойства (ii), а значит, и включения L(γ) ⊆ B.

(2) B ⊆ L(γ). Возьмем x ∈ B. Если x ∈ L

, то x ∈ A ⊆ L(γ).

Если x = h(x

), где

= x

. . . x

k+1

, k > 1,

причем x

∈ L

, a

i−1

∈ L

, 2 6 i 6 k, a

k+1

∈ L

, то в

силу определения языков L

, L

найдутся строки x

i−1

, 2 6 i 6 k, z

k+1

, лежащие в A. Тогда

, y

) `

= w

, y

) `

= w

. . .

, z

k+1

) `

. . . x

k+1

= x.

Следовательно, x ∈ L(γ).

Данное представление не является характеризацией язы-

ков из SH. В действительности, сходный результат имеет ме-

сто для всех регулярных языков: достаточно объеди нить лем-

мы 7.21 и 7.22. Тем не менее, данное представление имеет ряд

интересных следствий, одно из которых как раз касается регу-

лярности языков, получаемых простым сплетением.

Следствие 7. 4. SH ⊆ REG.

Помимо этого, из леммы 7.22 мы получаем следующее по-

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

Следствие 7.5. Если γ = (V, A, Q) — простая H-система, то

|x| 6 max{|w| | w ∈ A} для каждого x ∈ Sub(L(γ)) ∩ (V − Q)

∗

Из него выводится

Теорема 7.11. Если L — регулярный язык, то вопрос о том,

принадлежит ли L семейству SH, алгоритмически разрешим.

Доказательство. Пусть L ⊆ V

∗

— регулярный язык, заданный

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

Для произвольного подмножества Q ⊆ V обозначим

328 7. Системы сплетения

= (V − Q)

∗

∪ {x

· · · x

k+1

| 1 6 k 6

2 · card(Q), x

∈ (V − Q)

∗

, a

∈ Q, 1 6 i 6 k, причем нет

таких 1 6 i < j < l 6 k + 1, что a

= a

(Множество R

состоит из всех строк над V , в которых каж-

дый символ из Q появляется самое большее дважды.)

Докажем, что L ∈ SH тогда и только тогда, когда су-

ществует такое множество Q

, что L ∩ R

конечно и есть

⊆ L ∩ R

такое, что L = L(γ

) для γ

= (V, A

, Q

Действительно, достаточность очевидна. Установим необходи-

мость. Пусть L = L(γ) и γ = (V, A, Q) при Q ⊆ V . Множество

L ∩ R

не может быть бесконечным, иначе в Sub(L) ∩ (V − Q)

∗

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

ствием 7.5. Положим, Q

= Q. Если A не лежит в L ∩ R

, то в

A имеется строка вида z = x

для x

, x

∈ V

∗

a ∈ Q

. Рассмотрим строки

= x

, z

= x

Обе они лежат в σ

({z}), и значит, в L(γ). Более того,

, z

) `

z. Следовательно, заменив A на

= (A − {z}) ∪ {z

, z

мы получим систему γ

= (V, A

, Q

), такую, что L(γ

) = L(γ).

Повторив этот процесс конечное число раз (множество A

конечно и |z

|, |z

| < |z|), мы найдем нужную систему

= (V, A

, Q

) с A

⊆ L ∩ R

Теперь для проверки того, принадлежит ли данный регу-

лярный язык L ⊆ V

∗

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

ющий алгоритм. Для каждого подмножества Q

⊆ V (таковых

конечное число) рассматривается пересечение L ∩ R

. Если

оно бесконечно, то L /∈ SH. В противном случае, для каждого

подмножества A

⊆ L∩R

(которых опять же конечное число)

строится простая H-система γ

= (V, A

, Q

). Если L = L(γ

)

(что можно проверить алгоритмически), то, очевидно, L ∈ SH.

Если же для всех таких пар Q

, A

L 6= L(γ

), то L /∈ SH.

Этот результат не может быть обобщен на случай контекст-

но-свободных (и даже линейных) языков.

7.5. Простые H-системы 329

Теорема 7.12. Вопрос о том, принадлежит ли данный ли-

нейный яз ык семейству SH, неразрешим.

Доказательство. Возьмем произвольный линейный язык L

⊆

{a, b}

∗

, а также язык L

= c

, который не лежит в

семействе SH. Построим линейный язык

L = L

{c, d}

∗

∪ {a, b}

∗

Если L

= {a, b}

∗

, то L = {a, b}

∗

{c, d}

∗

∈ SH: для

γ = ({a, b, c, d}, {xy | x ∈ {a, b}

∗

, y ∈ {c, d}

∗

|x| ∈ {0, 2}, |y| ∈ {0, 2}}, {a, b, c, d})

мы имеем L(γ) = {a, b}

∗

{c, d}

∗

Если L

6= {a, b}

∗

, то возьмем w ∈ {a, b}

∗

−L

и рассмотрим

строку w

= wcdcd. Она лежит в L и (w

, w

) `

wcdcdcd при

e ∈ {c, d}. Получаемая строка не лежит в L, поэтому ни c, ни

d не может быть маркером в простой H-системе для языка L.

Но L содержит все строки из wc

, а значит, включение

L ∈ SH противоречи т пункт у (i) леммы 7.20.

Следовательно, L ∈ SH тогда и только тогда, когда L

{a, b}

∗

, а вопрос о справедливости такого равенства для данно-

го линейного языка алгоритмически неразрешим.

Поскольку SH ⊂ REG, представляет интерес исследование

взаимосвязей между SH и другими подсемействами R EG. Мы

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

ство строго локально тестируемых языков.

Язык L ⊆ V

∗

называется p-строго локально тестируемым

для некоторого p > 1, если он может быть представлен в виде

L = {x ∈ L | |x| < 2p}

∪ (Pref(L) ∩ V

∗

(Suf(L) ∩ V

) − V

∗

− Sub(L))V

∗

Язык называется строго локально тестируемым, если он p-

строго локально тестируемый при некотором p > 1. Семейство

таких языков мы будем обозначать через SLT .

Ясно, что SLT ⊂ REG. В действительности, SLT содер-

жится в семействе расширенных беззвездных языков, наимень-

330 7. Системы сплетения

шем семействе, содержащем конечные языки и замкнутом от-

носительно булевых операций и произведения.

Теорема 7.13. SH ⊂ SLT.

Доказательство. Мы воспользуемся характеризацией строго

локально тестируемых языков из [72].

Следуя [311], будем называть строку x ∈ V

∗

константой

по отношению к языку L ⊆ V

∗

, если из uxv ∈ L и u

∈ L

всегда следует, что uxv

∈ L и u

xv ∈ L. В [72] доказано, что

язык L ⊆ V

∗

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

только тогда, когда существует такое целое k, что все строк и

из V

являются константами по отношению к L.

Рассмотрим теперь язык L ∈ SH, и пусть L = L(γ), где

γ = (V, A, Q) — некоторая простая H-система. Положим

k = max{|x| | x ∈ A} + 1.

Каждая строка из V

есть константа по отношению к L. Дей-

ствительно, возьмем такую стр оку x и две строки uxv, u

из

L. Поскольку |x| = k, по следствию 7.5 имеем |x|

> 0. Возь-

мем такую букву a ∈ Q, что x = x

. Тогда uxv = ux

= u

, и значит, (uxv, u

) `

= uxv

, uxv) `

v = u

xv. Итак, L ∈ SLT и SH ⊆ SLT .

Это включение строгое: при w = aabb, очевидно, имеем w

∗

∈

SLT , но w

∗

/∈ SH по лемме 7.20(iii).

7.6 Комментарии к библиографии

Операция спл етения введена Хэдом [130] в форме, рассмотрен-

ной в начале раздела 7.1: задаются тройки (u, x, v), которые

описывают схемы, распознаваемые рестрикционными фермен-

тами, и из троек , создающих совместимые окончания, стро-

ятся правила сплетения ((u

, x, v

), (u

, x, v

)). Идея пр исоед и-

нить символ x к u

, u

(или к v

, v

), приводящая к описа-

нию места разреза в терминах контекстов (u

, v

), (u

, v

), по-

явилась в [73]. Кодирование правил сплетения в виде строк

предложено в [239]; там же были рассмотрены

схемы сплетения с бесконечными множествами правил.