Главная Промышленная автоматика.

валентных соответственно а и р, и заменить эти два множества их объединением. Очевидно, задачу можно смоделировать последовательностью операций ОБЪЕДИНИТЬ и НАЙТИ.

Однако если внимательнее проанализировать эту задачу, можно по-другому применить структуры данных из предыдущего раздела. Каждому идентификатору соответствует графа таблицы символов, и, если несколько идентификаторов эквивалентны, удобно хранить данные о них только в одной графе таблицы символов. Это означает, что для каждого множества эквивалентных идентификаторов есть начало отсчета, т. е. место в таблице символов, где хранится информация об этом множестве, и каждый элемент этого множества имеет смещение от начала. Чтобы найти положение идентификатора в таблице символов, надо прибавить его смещение к началу отсчета множества, которому принадлежит данный идентификатор. Но когда два множества идентификаторов становятся эквивалентными, надо изменить смещение. Эта задача корректировки смещений в абстрактном виде решается в приложении 2.

Приложение 2. Задача определения глубины

Дана последовательность операций двух типов: СВЯЗАТЬ(и, г) и НАЙТИ ГЛУБИНУ(и). Начнем с п неориентированных корневых деревьев, каждое из которых состоит из единственного узла i, l<t<n. Операция СВЯЗАТЬ(и, г), где г - корень дерева, а и - узел другого дерева, делает корень г сыном узла v. Условия о том, что и и г принадлежат различным деревьям и что г - корень, гарантируют, что получаемый в результате граф также будет лесом. Операция НАЙТИ ГЛУБИНУ(и) состоит в том, чтобы найти и напечатать глубину узла v в текущий момент.

Если при работе с лесом использовать обычное представление в виде списков смежностей и вычислять глубину узлов очевидным образом, то сложность алгоритма будет 0{п). Вместо этого мы представим исходный лес другим лесом, который будем называть Г)-лесом. Он нужен нам только для того, чтобы можно было быстро вычислять глубины. Каждому узлу в D-лесу приписывается целочисленный вес так, чтобы сумма весов вдоль пути в D-лесу от узла V к корню равнялась глубине узла v в исходном лесу. Для каждого дерева в D-лесу хранится счетчик числа узлов в этом дереве.

Вначале D-лес состоит из п деревьев, каждое из которых содержит единственный узел, соответствующий целому числу i, lin. Начальный вес каждого узла равен нулю.

Для выполнения операции НАЙТИ ГЛУБИНУ(и) мы проходим путь из узла v в корень г. Пусть Vi, Wj. - > ; Vh - узлы на этом пути (Ui=u, Wft=r). Тогда

ГЛУБИНА(&) = 2 BEC[w,J. i=i



Крометого, применяем сжатие путей. Каждый узел и,-, li-2,

делается сыном корня г. Чтобы сохранялось сформулированное

выше свойство весов, новый ВЕС узла Vi должен равняться V ВЕС[иЛ

для \i<ik. Так как новые веса можно вычислить за время 0{k), то операция НАЙТИ ГЛУБИНУ имеет ту же временную сложность, что и операция НАЙТИ.

Чтобы вьшолнить операцию СВЯЗАТЬ(и, г), соединим деревья, содержащие узлы и и г, снова вливая меньшее дерево в большее. Пусть Tj, и Гг - деревья в D-лесу, содержащие и и г соответственно, а о и г - их корни. Деревья в D-лесу не обязательно изоморфны деревьям в исходном лесу, так что, в частности, г может не быть корнем для Тг- Пусть СЧЕТ(Г) обозначает число узлов в дереве Т. Рассмотрим отдельно два случая.

Случай 1. СЧЕТ(ГгХСЧЕТ(Г„). Делаем г сыном узла v. Мы должны также скорректировать вес старого корня г дерева Тг так, чтобы глубина каждого узла w в Тг правильно вычислялась при прохождении пути из ш в о в объединенном дереве. Чтобы сделать это, выполняем операцию НАЙТИ ГЛУБИНУ(и), а затем

ВЕС[г]ВЕС[г]-ВЕС[и] + ГЛУБИНА(и) + 1.

Таким образом, глубина каждого узла в Тг эффективно увеличена на глубину узла v плюс 1. Наконец, полагаем счетчик числа узлов объединенного дерева равным сумме счетчиков для Тг и Т.

Случай 2. СЧЕТ(Г„)<СЧЕТ(Гг). Здесь вычисляется ГЛУБИ-HA(w), преобразуется узел v в сына узла г и

ВЕС [г] ВЕС [г] + ГЛУБИНА(и) + 1; ВЕС [у] ВЕС [и]-ВЕС [г]; СЧЕТ(ГЛ - C4ET(rj +СЧЕТ(Г,).

Итак, 0(п) операций СВЯЗАТЬ и НАЙТИ.ГЛУБИНУ можно вьшолнить за время 0{nG{n)).

Приложение 3. Эквивалентность конечных автоматов

Детерминированным конечным автоматом называется машина, распознающая цепочки символов. Она имеет входную ленту, разбитую на клетки, головку на входной ленте (входную головку) и управляющее устройство с конечным числом состояний (рис. 4.24). Конечный автомат М можно представить в виде пятерки (5, /, б. So, F), где

1)5 - множество состояний управляющего устройства, 2) / - входной алфавит (каждая клетка входной ленты содержит символ из /),



Входная лента

Головна

Управляющее устройство

Рис. 4.24. Конечный автомат.

3) б - отображение из Sx/ в 5 (если 6(s, a)=s, то всякий раз, когда М. находится в состоянии s, а входная головка обозревает символ а, М сдвигает входную головку вправо и переходит в состояние s),

4) So - выделенное состояние в 5, называемое начальным,

5) F - подмножество в S, называемое множеством допускающих (или заключительных) состояний.

Пусть /* - множество цепочек (слов) конечной длины, состоящих из символов алфавита 1. В 1* включается и пустая цепочка е. Продолжим б до отображения из 5х/* в S:

1) 6(5, e)=s,

2) б (s, ха)=Ь (б (s, х), а) для всех х!* nag/.

Входная цепочка х допускается автоматом М, если б (So, х) F. Языком L(M), допускаемым автоматом М, называется множество всех цепочек, допускаемых М. Более подробное введение в теорию конечных автоматов изложено в разд. 9.1.

Два состояния Si и Sa считаются эквивалентными, если для каждого х1* состояние б (Si, х) будет допускающим тогда и только тогда, когда б (Sa, х) - допускающее состояние.

Два конечных автомата Mi и М считаются эквивалентными, если L(Mi)=L(iWa). Мы покажем здесь, что с помощью алгоритма ОБЪЕДИНИТЬ - НАЙТИ можно распознать эквивалентность двух конечных автоматов Mi= (Si, 1, 6i, Si, и Л1а= (Sa, /, ба, sa, fa) за 0{nG{n)) шагов, где n=5i+5a.

Отношение эквивалентности двух состояний обладает важным свойством: если два состояния s и s эквивалентны, то для всех входных символов а состояния б (s, а) и б (s, а) также эквивалентны. Кроме того, благодаря наличию пустой цепочки, никакое допускающее состояние не может оказаться эквивалентным недопу-скающему. Таким образом, если допустить, что начальные состояния Si и Sa автоматов Mi и Ма эквивалентны, то можно вывести другие пары эквивалентных состояний. Если в одну из таких пар попадет допускающее состояние вместе с недопускающим, то Si и Sa были неэквивалентными. Если же это не произойдет, то верно обратное





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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021