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

1. for г-<-О until п do

begin

2. if 1 = 0 then S, -{So}

3. else 5,. U б (s, a,.);

comment S,- еще не достигло своего конечного значения. Сейчас оно соответствует множеству Г,-, упомянутому выше;

4. пометить каждое состояние tS; как "рассмотренное";

5. пометить каждое состояние tS-Si как "нерассмот-

ренное";

6. ОЧЕРЕДЬ -S,;

7. while список ОЧЕРЕДЬ не пуст do

begin

8. найти и удалить первый элемент t, входящий в

ОЧЕРЕДЬ;

9. for u8(t, е) do

10. if и-"нерассмотренное" состояние then

begin

11. пометить и как "рассмотренное";

12. добавить и в ОЧЕРЕДЬ и в end

Рис. 9.11. Моделирование недетерминированного конечного автомата.

Решающее свойство в теореме 9.2 заключалось в том, что на графе переходов из каждого состояния автомата М выходит не более двух ребер. Это свойство позволяет показать, что на входной цепочке х= =aiai. . Мп алгоритм 9.1 (см. ниже) тратит на моделирование НКА, построенного из р, 0(п р) шагов.

Алгоритм 9.1. Моделирование недетерминированного конечного автомата

Вход. НКА M=(S, 1, 6, So, F) и цепочка хафг. . .а„ из /*. Выход. Последовательность So, Si, Sа, .... 5„, где

S,= {s(s„, a,a,...ai)\-*{s, е)}, 0<t<n.

Метод. Чтобы получить Sj по Sj-j, сначала найдем множество состояний Г{ = {/6 (s, Ui) содержит t для некоторого s Sj-i}. Затем



ВЫЧИСЛИМ "замыкание" множества Ti, добавив к Г; все такие состояния и, что 6 {t, е) содержит и для некоторого t, ранее оказавшегося в Ti. Это замыкание (оно и будет множеством Si) строится с помощью очереди состояний tTi, для которых множество б (/, е) еще не рассматривалось. Алгоритм приведен на рис. 9.11. □

Пример 9.6. Пусть М - НКА, изображенный на рис. 9.6, в. Допустим, что на вход подана цепочка х=аЬ. Тогда So={si} в строке 2. В строках 9-12 рассмотрение состояния Si приводит к добавлению Sa и Sg в ОЧЕРЕДЬ и в So. Рассмотрение Sa и Sp не добавляет ничего, поэтому So={si, Sg, Sg}. Затем в строке 3 Si={s3}. Рассмотрение Ss добавляет Si в Si, а рассмотрение Si добавляет Sj и s,. Рассмотрение Sj не добавляет ничего, а рассмотрение s, добавляет Sio Таким образом, Si={ss, s, Sj, s„ Sio}. Затем в строке 3 Sa={s5}. Рас смотрение s, добавляет и $7 в о а. Рассмотрение s, добавляет Sio

Итак, Sa={s„ Sg, S„ Sio}. □

Теорема 9.4. Алгоритм 9.1 правильно вычисляет последовательность So, Si, ... , s„, где Sj={s(so, fli fla- • -aO H* (s, e)}.

Доказательство. Простое упражнение на применение индукции, которое мы оставляем читателю. □

Теорема 9.5. Пусть в диаграмме автомата М с т состояниями из каждого узла выходит не более е ребер. Тогда на входной цепочке длины п алгоритм 9.1 тратит 0{етп) шагов.

Доказательство. Исследуем построение множества Si для одного конкретного значения i. Строки 8-12 на рис. 9.11 занимают 0(e) шагов. Поскольку для данного i никакое состояние не попадает в ОЧЕРЕДЬ дважды, то цикл в строках 7-12 требует 0{ет) времени. Поэтому легко показать, что тело основного цикла, т. е. строки 2-12, занимает 0(ет) времени. Таким образом, весь алгоритм занимает 0{етп) времени. □

Отсюда вытекает важный результат, связывающий распознавание вхождения элементов регулярного множества с алгоритмом 9.1.

Следствие. Если р - произвольное регулярное выражение и х= =aiaa. . -fln - цепочка длины п. то найдется НКА М, допускаюи{ий язык, представленный выражением Р, причем алгоритм 9.1 тратит на построение последовательности So, Si, ... , S„, где Sj={s (so.flifla- • -Oi) \-*(s, e)} для 0<i<rt, время 0(np).

Доказательство. По теореме 9.2 можно построить автомат М, у которого не более 2р состояний и из каждого из них выходит не более двух ребер. Поэтому е в теореме 9.5 не превосходит 2. □



Исходя ИЗ алгоритма 9.1, можно построить различные алгоритмы распознавания образов. Например, пусть даны регулярное выражение а и цепочка-текст x=aia2. . an и надо найти наименьшее число k, для которого существует такое j<.k, что ajaj+i. . .а принадлежит множеству, представленному выражением а. С помощью теоремы 9.2 можно построить по а НКА М, допускающий язык /*а. Чтобы найти наименьшее число k, для которого flifla- . .flft принадлежит L{M), можно после блока, состоящего из строк 2-12 на рис. 9.11, вставить тест, проверяющий, содержит ли множество Sj состояние из F. В силу теоремы 9.2 можно сделать F одноэлементным, так что такой текст не займет много времени; достаточно 0{т) шагов, где т - число состояний в М. Если Sj содержит состояние из F, то прерываем основной цикл, поскольку обнаружено, что Ciua. . .ai - кратчайший префикс цепочки х, который входит в L{M).

Алгоритм 9.1 можно модифицировать и так, чтобы он для каждого упомянутого k находил такое наибольшее }<.k (или наименьшее /), что ajaj+i. . .flft входит в множество, представленное выражением а. Это делается приписыванием целого числа каждому состоянию из множеств Si. Число, приписанное состоянию s б S, указывает такое наибольшее (или наименьшее) /, что (so, flyfly+i. . .ял) Ь-* (s,e). Детали приписывания этих целых чисел с помощью алгоритма 9.1 оставляем в качестве упражнения.

9.3. РАСПОЗНАВАНИЕ ПОДЦЕПОЧЕК

Важным частным случаем общей проблемы, описанной в предыдущем разделе, является случай, когда регулярное выражение а имеет вид yi+yt+. . .+Ук, где каждый член yt - цепочка в алфавите /. Из следствия теоремы 9.5 вытекает, что первое вхождение цепочки-образа yt в цепочку-текст jc=aia,. . .а„ можно найти за 0(1п) шагов, где I - сумма длин цепочек yi. Однако возможно решение и сложности 0{1+п). Сначала рассмотрим случай, когда дана только одна цепочка-образ y=6ifc». . .fc/, где каждый символ bi принадлежит /.

По цепочке у построим детерминированную машину My для идентификации цепочек, которая распознает кратчайшую цепочку из 1*у, входящую в X. Чтобы построить My, построим сначала скелетный ДКА с /+1 состояниями О, 1, . . . , /, который переходит из состояния i-1 в состояние i на входном символе bi, как показано на рис. 9.12. Состояние О имеет также переход в себя при всех ЬфЬ. Состояние I можно считать указателем на t-ю позицию цепочки-образа у.

Машина идентификации цепочек My работает как детерминированный конечный автомат с той лишь разницей, что, просматривая один входной символ, она может сделать несколько переходов (изме-





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