Главная  Кибернетика 

[0] [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] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

46] ДЕРЕВО ПРЕЕМНИКОВ 137

ветвей. Последовательность из / ветвей таких,, что k-я ветво

находится в k-ы уровне (ft=l, 2.....и таких, что

(k-\- 1)-я ветвь порождается й-й ветвью (ft = 1, 2...../ - 1),

называется путем по дереву; I называется длиной пути по дереву. Если ft-я ветвь этого пути по дереву есть

(ft=l, 2.....Г), то говорят, что этот путь описывает

входную последовательность ... . Таким образом,

первые ft+ 1 уровней дерева преемников содержат р" путей, описывающих все возможные р" входные последовательности длины ft, которые могут быть построены из р входных символов.

Каждая ветвь в дереве преемников, построенном для М и А{М), связана с Л-группой. Л-группа, с которой связана начальная ветвь, есть А{М). Если ветвь b связана с Л-груп-пой О, то ветвь которую порождает Ь, связана с ;-пре-емником О. Таким образом, Л-группы, связанные с ветвями ft-ro уровня (ft ;> 1), могут быть определены из Л-групп, связанных с ветвями (ft - 1)-го уровня. В этом методе любой уровень дерева может быть построен на основании построенного уровня, который непосредственно предшествует ему. Говорят, что путь по дереву ведет в Л-группу О, если его последняя ветвь связана с О.

Уроаш I

О SI {3,2} fij. 4,5}

а \ 0 * i

I---•-1 I I

г Wizxsjt i4.5t.a.5} (2лг},{11 (Ы4.5}

тМ(Ш ММ0,4) (ЗЛШ.Ш ши4,Я !.mw Ш.з.г){SMS)

Рис. 4.6. Дерево преемников для Л17 и множества допустимых начальных состояний {2, 3, 4, 5}.

Рис. 4.6 показывает первые четыре уровня дерева преемников, построенного для автомата Л17 (рис. 4.3) и множества допустимых начальных состояний {2, 3, 4, 5). Каждая ветвь отмечена входным символом, который она представляет, и Л-группой, с которой она связана. Л-группа,



связанная с начальной ветвью, есть множество допустимых начальных состояний {2, 3, 4, 5). Остальные Л-группы могут быть найдены с помощью таблицы или диаграммы переходов для Л17. Например, когда а прикладывается к состояниям 2, 3, 4 и 5, выходные символы будут О, О, 1 и 1 соответственно и следующие состояния будут 1, 5, 3 и 2 соответственно; тогда а-преемник Л-группы {2, 3, 4, 5) состоит из о-множеств {1, 5) и {3, 2). Следовательно, ветвь а в первом уровне дерева преемников связана с Л-группой {1,5), {3, 2).

Следующие леммы, которые описывают некоторые свойства дерева преемников для автомата М и множества допустимых начальных состояний Л (Ж), являются прямыми результатами вышеприведенных правил и определений.

Лемма 4.1. Пусть через А (М) обозначено Gq и пусть есть А-группа, связанная с k-u ветвью пути по дереву. Тогда: (а) Решение 0 равно или превышает решение G i. (б) Если Oj i содержит кратное о-множество, то также должно содержать кратное а-мно-жество.

Лемма 4.2. Пусть Л(Ж)=о,-, о,-.....Ojj и пусть

О есть А-группа, к которой ведет путь по дереву, описывающий входную последовательность . Пусть о

обозначает преемника по отношению к у. Тогда: (а) о о.....о -это т состояний, содержащихся

\ 2 m

в а-множествах О. (б) а и о находятся в различных а-множествах О тогда и только тогда, когда 0( и о,- выдают различные выходные последовательности при подаче входной последовательности у..

Лемма 4.3. Пусть и обозначают две ветви, связанные с одинаковыми А-группами. Тогда ветвь, связанная с А-группой О, может быть достигнута из bi через I ветвей тогда и только тогда, когда ветвь, связанная с А-группой О, может быть достигнута из через I ветвей.

4.7. Диагностическое дерево

Дерево преемников, определенное в предыдущем параграфе, по своему протяжению бесконечно и как таковое не имеет практического применения. В этом разделе мы



4.7] ДИАГНОСТИЧЕСКОЕ ДЕРЕВО 139

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

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

Определение 4.1. Диагностическое дерево есть дерево преемников, в котором ветвь b k-то уровня становится

Уровень I

О <2.3.4.5)

f V.5>{3.2} is 74 5}

I-*--•-1

г {r)j2US.r} <4.5},V,5)

a \ i a iff

I Ч I I

3 ln.V}.{2UU {4и5Ш4) {ЗЛ(ПШ {4,5}.{4.S)

Рис. 4.7. Диагностическое дерево для Л17 и множества допустимых начальных состояний {1, 2}.

оконечной, если удовлетворяется одно из следующих условий: (1) Л-группа, связанная с Ь, содержит кратное о-множество. (2) Л-группа, связанная с Ь, связана с некоторой ветвью уровня, предшествующего ft-му. (3) Имеется ветвь /г-го уровня (возможно, сама ветвь Ь), связанная с простой Л-группой.

Условие (3) подразумевает, что первый уровень, который содержит ветвь, связанную с простой Л-группой, является также последним уровнем в диагностическом дереве. Дерево, последний уровень которого является й-м, называется деревом высоты k. Рис. 4.7 показывает, как строится диагностическое дерево для автомата Л17, представленного на рис. 4.3, и для множества допустимых начальных состояний {2, 3, 4, 5 Ветвь первого уровня, связанная с Л-группой {5, 1, 4, 5 является оконечной в силу правила (1). Очевидно, что на третьем уровне Л-группа {1}, {1), {2}, {!) является простой; поэтому в силу правила (3) все ветви на третьем уровне



[0] [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] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

0.0012