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


Рис. 9.7. НКА М из примера 9.5.

3) F={s\{s,f)E и / eF}.

В качестве упражнения предлагаем доказать, что L{M)= =L(A1). Разумеется, в М нет переходов по е.

Далее по М построим ДКА М", состояния которого образуют множество-степень для S. Другими словами, M-iSS), I, 8", {So}. F"), где

1) для каждого подмножества S множества S и каждого ag/ 6"(S, a)={t\8(s, а) содержит t для некоторого sgS},

2) F={S\SnF0y

В качестве упражнения предлагаем доказать индукцией по \w\, 4To{{so},w)\-M~{S,e,) тогда и только тогда, когда S={(so, ш) \-M(i> е)}. Таким образом, L{M)=L(M)=L(M). □

Пример 9.5. Рассмотрим НКА М на рис. 9.7. Из начального состояния Si можно достичь Sg и заключительное состояние St по путям, помеченным символом е. Поэтому для вычисления рефлексивного и транзитивного замыкания С ориентированного графа G, о котором шла речь в доказательстве теоремы 9.3, надо добавить ребро (Si, S4). Весь граф G изображен на рис. 9.8. По Л1 и G построим НКА Л1 (рис. 9.9). Так как в узел s« входят ребра из всех узлов графа G, объявляем все состояния в М заключительными. Так как единст-


Рис. 9.8. Граф G.




Рис. 9.9. НКА М.


Рис. 9.10. ДКА М.

венное ребро, входящее в узел Sj в диаграмме для М, помечено символом е, то Sa не входит в М.

При построении ДКА М" по автомату М образуется восемь состояний. Но только четырех из них можно достичь из начального состояния, так что остальные четыре можно выбросить. ДКА М изображен на рис. 9.10. □

9.2. РАСПОЗНАВАНИЕ ОБРАЗОВ,

ЗАДАВАЕМЫХ РЕГУЛЯРНЫМИ ВЫРАЖЕНИЯМИ

Изучим задачу распознавания образов, в которой дана цепочка-текст x=aia2. . .а„ и регулярное выражение а, называемое образом. Мы хотим найти такой наименьший индекс /, что для некоторого ( подцепочка а,аг+1. . .а цепочки х принадлежит языку, представленному выражением а.

Вопросы такого рода часто возникают при редактировании текстов. Многие программы для редактирования текстов разрешают пользователю задавать типы замен в цепочке-тексте. Например, пользователь может сказать, что он хочет заменить слово у каким-то другим словом в куске текста х. Чтобы вьшолнить такую команду, программа редактирования текста должна суметь найти вхождение слова у в X. Некоторые искусные редактирующие программы разрешают пользователю в качестве множества заменяемых цепочек указывать регулярное множество. Например, пользователь может



сказать: "Заменить [/*] в х пустой цепочкой", имея в виду, что в х следует стереть пару квадратных скобок и символы между ними.

Поставленную выше задачу можно переформулировать, заменив данное регулярное выражение а выражением р=/*а, где / - алфавит цепочки-текста. Можно найти первое вхождение цепочки из L(a) в x=aiai. . .а„, обнаружив кратчайший префикс цепочки х, принадлежащий языку выражения р. Эту задачу можно решить, сначала построив НКА М для распознавания множества, представленного выражением р, а затем применив алгоритм 9.1 (см. ниже) для определения последовательности множеств состояний St, в которые может перейти НКА М после прочтения цепочки aifla- • при i=l, 2, . . . , п. Как только в Sj попадает заключительное состояние, мы можем сказать, что у цепочки aiflj. . Oj есть такой суффикс flifli+i. . Mj, что ajflj+i. . Mj принадлежит языку, представленному выражением а, при некотором lt. Техника нахождения t, т. е. левого конца образа, обсуждается в упр. 9.6-9.8.

Один из способов моделирования поведения НКА М на цепочке-тексте X - превратить М в детерминированный конечный автомат, как в теореме 9.3. Но такой путь может оказаться слишком дорогим, поскольку от регулярного выражения р можно перейти к НКА с 2р состояниями, а затем к ДКА с почти 2«3i состояниями. Уже само построение ДКА может вызвать непреодолимые трудности.

Другой способ моделирования поведения НКА М на цепочке х - сначала исключить е-переходы в Л1 и тем самым построить НКА М без е, как это было сделано в теореме 9.3. Затем моделировать НКА М на входной цепочке x-aiOt. . .an, вычислив для каждого i, 1< <i<rt, множество состояний Sj, в которые мог бы попасть М после прочтения Oiua. . .at. На самом деле каждое множество Sj - это то состояние, в которое пришел бы ДКА М", построенный в доказательстве теоремы 9.3, после прочтения fliflj. . .at.

Применяя 8ту технику, можно не строить автомат М", а вычислить только те его состояния, которые появляются при обработке цепочки X. Чтобы объяснить, как найти множество Sj, надо показать, как построить S по St-i. Легко видеть, что

Si= и 6(s, а,),

где 6 - функция переходов автомата М. Тогда Sj - объединение вплоть до 2Р множеств, каждое из которых содержит не больше 2р членов. Так как при объединении надо исключить повторяющиеся члены (иначе представление множеств может стать громоздким), то очевидное моделирование автомата М занимает 0(1Р*) шагов на входной символ, т. е. в общей сложности 0(п IPI") шагов.

Как это ни удивительно, но во многих практических ситуациях гораздо эффективнее не исключать е-переходы, а работать прямо с НКА М, построенным по теореме 9.2 из регулярного выражения р.





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.0038