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


назад Оглавление вперед




[9]

Доказательство. Предположим, что T является каноном, но

width(T) = s > (w + 1)m.

Из определения ширины следует, что T содержит участок T1 ...Ts, в котором маршрут Tj, i = 1,..., s, непуст и нейтрален. Вследствие утверждения 2 неравенство s > (w + 1)m означает, что среди начальных вершин этих маршрутов по крайней мере w + 2 одинаковы. Пусть, например, beg(Tij) = beg(Tij+1), где 1 < ij < s и 1 < j < w + 2. Тогда w + 1 участков Tij ... Tij+1 1 являются нейтральными циклами. Следовательно, T не удовлетворяет первому условию определения канона вопреки допущению, что T есть канон. Предположим теперь, что T - канон, но

depth(T) = k> (d + 1)m2.

Из определения глубины следует, что T содержит участок

T11 . . . T1kT2k ... T21,

в котором T1i и T2i, i = 1,..., k, парны друг другу. Из неравенства k > (d + 1)m2 имеем существование таких номеров ij, что beg(T1ij) = beg(T1ij+1) и end(T2ij) = end(T2ij+1) для 1 < j < d + 2. Тогда

T1ij . . . T1(ij+1 1) и T2(ij+1 1) . . . T2ij

являются парными в T циклами для 1 < j < d + 1. Следовательно, T не удовле творяет второму условию определения канона, вопреки допущению, что T есть канон □

Из теоремы 1 и леммы 3 вытекает

Теорема 3. Пусть m есть число вершин Dграфа D. Длина канона графа D ограничена числом g(w+1)m,{d+1)m2. Следовательно, множество Core(D) конечно □

Пример 8. Пусть M - магазинный автомат из примера 6, D2 = Graph(M). Тогда пересечение множеств Core(D2, 1, 1) и Sentences(D2) совпадает с

{12k234k678(98)1k, I = 0,1} U {1578(98)г/ = 0,1}.

1.3.2. Теорема о развитии. Покажем, что ядро Dграфа D выражает закон образования цепочек языка L(D) из некоторых подцепочек пометок маршрутов, входящих в ядро. Для этого определим форманты - важный "материал строи тельства"произвольных маршрутов Dграфа из присутствующих в ядре. Определяемое здесь же бинарное отношение развития на множестве маршрутов можно расценить как "инструмент строительства". Основная здесь теорема 4 имеет ана -логию с классической теоремой о разрастании цепочек бесконтекстных языков.

Пусть (T1,T2,T3) есть гнездо, в котором T1 и T3 - циклы. Пусть (T12, T2, T32) и (T11, T12T2T32, T31) не являются гнездами в маршруте T1T2T3 для любых циклов T11, T12, T32, T31, таких, что T1 = T11T12, T3 = T32T31. Тогда назовем гнездо (T1,T2,T3) простым.

Пусть маршрут T является нейтральным циклом или простым гнездом и не содержит меньшего участка, который есть нейтральный цикл или простое гнездо. Тогда назовем маршрут T формантом.


Определим бинарные отношения D, TD на множестве маршрутов Эграфа D: (T, T) eD (с историей (T1,T2, T3, T4, T5)) тогда и только тогда, когда T = TlT3T5, T = TlT2T3T4T5, T2T3T4 есть формант, в котором T2 и T4 являются парными циклами; (T,T) eD (с историей (Tl,T2,end(T2),end(T2),T5)) тогда и только тогда, когда T = TlT2T5, T = T{T5, T2 есть циклический формант.

Объединение ffD=\D U TD будем называть отношением развития.

Пусть T, T - это маршруты графа D. Пусть либо T = T, либо для некоторого k > 0 существует последовательность

gen(T) = ((T11,T12,T13,T14,T15), , (Tkl ,Tk2,Tk3,Tk4,Tk5)),

такая, что V = ТцТ, T = TklTk2TT, (TTuTT) e Ь с историей (Tn,Ti2,Ti3,Ti4,Ti5) и

(T(i-l)lT(i-l)2T(i-l)3T(i-l)4T(i-l)5, TilTi2Ti3Ti4Ti5) ei[D

с историей

(Til, Ti2, Ti3,Ti4, Ti5), 1 < i < k.

Тогда назовем последовательность gen(T) родословной (с предком T) маршрута T; число k назовем длиной родословной. Если T = T, то родословная маршрута T (с предком V) пуста.

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

Пусть маршрут T содержит нейтральный цикл или парные циклы. Тогда на зовем маршрут T производным. Маршрут, не являющийся производным, назовем элементарным.

Теперь установим, что среди предков каждого нейтрального маршрута есть канон (более того, элементарный канон).

Лемма 4. Каждый производный маршрут содержит в себе формант.

Доказательство. Ясно, что каждый производный маршрут содержит производный нейтральный участок. Выберем среди нейтральных производных участков производного маршрута минимальный по длине. Предположим, что выбранный участок T не является формантом. Тогда из определения форманта следует, что T содержит меньший участок, который является нейтральным циклом или гнездом, образованным парными циклами. Итак, исходный маршрут содержит производный участок, который короче, чем T, вопреки выбору T □

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

Пусть T - маршрут. Пусть

Sl = {TlT3 3 (нейтральный цикл T2) T = TlT2T3},

S2 = {TiT3T5 3 (циклы T2,T4) (T2,T3,T4) является гнездом в T = T3T4T5}

DelCycle(T) = { {T} Sl = 0 * 1 Sl иначе.

DelPair(T) = ( {J} S2 = 0 S2 иначе.


Следующие функции отображают некоторые разбиения маршрутов во множества маршрутов.

Пусть TTT- маршрут. Пусть S3 = {TiT3T5 е DelPair(TTT") 3 (T2, T4, T[, T5) (T = TT2T, T" = T5T4T5, T3 = T{TT5) }.

PreservingDel(T,T,T) = I {TTT"} S 0 v 1 S3 иначе.

Пусть m > 1, T = TiT/ ... Tm iTlm iTm - маршрут. Пусть S обозначает объединение следующих двух множеств:

{TiTi... Ti i T! iTiT ... Tm iTm iTm 1 < i < m

"Ti е DelCycle(Ti) U DelPair(Ti)}, {TiTi... Ti i T i TiT... Tj i T i T Tj ... Tm i Tm i Tm1 < i<j < m,

T{T[ ... Tj i Tj i T е PreservingDel(Ti, Ti ... Tj i Tj i ,Tj)}.

Если S = 0, то значением reduction(Ti, T[, ..Tm i, Tm i, Tm) является множество {T}, иначе множество

UfiT{ ...fm-1Trn 1fm&Sreduction{Ti, Ti, . . . , Tm i , Tm i , Tm).

Лемма 5. Пусть T - нейтральный маршрут; пусть (T,T) efr> с историей (T, T2, T3, T4, T5). Тогда существует (2,1)канон

Tl ГТ1 ГТ1 ГТ1 ГТ1 ГТ1 0 = T0i T2T3T4T05,

такой, что pair(T0) = pair(T). Доказательство. Пусть

T0 = T0 iT2T3T4T05 е reduction(Ti,T2T3T4,T5).

Убедимся, что T0 является (2,1)каноном. Из построения маршрута T0 следует, что каждый его нейтральный цикл должен иметь общий участок с формантом T2T3T4. Следовательно, для участка T . . . T m маршрута T0, в котором T i явля ется нейтральным циклом для i = 1,... ,m, число m не может превышать двух.

Из построения маршрута T0 следует также, что хотя бы один из парных в нем циклов должен иметь общий участок с формантом T2T3T4. Следовательно, гнездо T = T2T3T4 маршрута T0, которое отлично от T2T3T4 и в котором T2 и T4 -парные циклы, содержит в себе формант T2T3T4. Если T2T3T4 содержится в одном из циклов T2, T4, то гнездо T является простым. Если T2T3T4 имеет общий участок с каждым из циклов T22, T4, то pair(T3) = pair(T33) (иначе маршрут T2T3T4 не был бы формантом). Следовательно, и в этом случае гнездо T = T2T3T4 является простым. Таким образом, T0 удовлетворяет определению (2,1)канона □

Прием применения функции reduction подходит и в доказательстве следую щего факта, который влечет возможность построения D множества магазинного автомата за конечное число шагов.

Лемма 6. Пусть (ni,T2,n2) есть гнездо некоторого предложения TniT2n2T3, ni и п2 являются дугами. Тогда существуют такие маршруты Ti, T22, T3, что TiniT2n2T3 является предложением и (1,1)каноном, а (ni,T22,п2) - его гнездом.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49]