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

Рис. 9.4. Конечные автоматы, допускающие языки, представленные регулярными выражениями длины 1: (а) 0, (б) {е}, (в) [а].

С точки зрения сложности вычислений наиболее важно, что можно найти НКА, у которого число состояний не больше удвоенной длины данного регулярного выражения и который из каждого своего состояния может перейти не более чем в два других.

Теорема 9.2. Пусть а - регулярное выражение. Тогда найдется НКА M=(S, I, б. So, {S{}), допускаюш,ий язык, представленный а, и обладаюи1,ий такими свойствами:

1) SK2a, где \а\ - длина выражения а),

2) для каждого а1\]{г} множество б(S, а) пуста,

3) для каждого sS сумма чисел б(s, а)\\ по всем а из не превосходит 2.

Доказательство. Доказательство проведем индукцией по длине выражения d. Рассмотрим базис, т. е. случай а=1. Тогда выражение а должно быть одного из трех видов: (а) 0, (б) е или (в) а для некоторого а g /. На рис. 9.4 изображены три автомата, имеющие по два состояния каждый, допускающие указанные языки и удовлетворяющие условиям теоремы.

Для шага индукции рассмотрим четыре возможных вида а: (а) p-bv, (б) pv, (в) р*, (г) (Р), где р и 7 - регулярные выражения. В случае (г) а и Р представляют один и тот же язык, так что индукция очевидна. Рассмотрим другие случаи. Пусть М и М" - НКА, допускающие языки, представленные выражениями Р и 7 соответственно, причем их множества состояний не пересекаются. Пусть и So - начальные состояния этих автоматов, а sl и sf - их заключительные состояния. Графы переходов для случаев (а), (б) и (в) показаны на рис. 9.5.

Пусть длины а, Р и 7 равны а, Р и I7I соответственно, а га, га и га" - числа состояний автоматов М, М и М". В случае (а) а = = 11+171+1 и n=ra4-n"-f2. По предположению индукции га< <2Р и n"<27, откуда га<2а. Кроме того, в случае (а) добавляются только два ребра, выходящие из So (которые удовлетворяют тому ограничению, что из любого узла выходит не более двух ребер), да еще по одному ребру, выходящему из каждого узла s\ и s{. Так

Длиной регулярного выражения а называется число вхождений символов в цепочку а. Например, е*=2. Можно было бы усилить свойство 1, игнорируя скобки при подсчете длины выражения а (например, регулярное выражение (а*Ь*)* при таком условии имело бы длину 5, а не 7).





Рис. 9.5. Графы переходов автоматов, допускающие языки, представленные регулярными выражениями (а) P+V. (б) Pv. (*) Р*-

как по предположению из каждого узла si и s] раньше не выходило ни одного ребра, то это же ограничение на число выходящих ребер выполнится и для Sf и Sf. Наконец, из Sf, очевидно, никакие ребра не выходят. Случай (б) проверяется аналогично

В случае (в) а=Р+1 и п=п+2. Поскольку п<2р, то отсюда следует, что п2а. Ограничение на число ребер, выходящих из любого узла, легко проверяется. □

Пример 9.4. Построим НКА для регулярного выражения аЬ* + +с, длина которого равна 5. НКА для а, b и с изображены на рис. 9.4, в. С помощью конструкции рис. 9.5,в построим автомат для &*, как показано на рис. 9.6,а. Затем с помощью конструкции рис. 9.5,6 построим автомат для аЬ*, как показано на рис. 9.6,в. Наконец, с помощью конструкции рис. 9.5,а построим НКА для аЬ*+с. Этот автомат, имеющий 10 состояний, изображен на рис. 9.6,в. □

Необходимо упомянуть один дополнительный результат. По данному НКА можно найти эквивалентную "детерминированную" машину. Однако детерминированный конечный автомат, эквивалентный данному НКА с п состояниями, может иметь вплоть до 2" состояний. Поэтому переход к детерминированному автомату не всегда дает эффективный способ моделирования недетерминированного конечного автомата. Тем не менее детерминированные автоматы оказыва-

1) На самом деле ребро из sf в So не нужно. Вместо него можно было бы просто отождествить s] и so. Точно так же на рис. 9.5,а можно было бы отождествить Sf и Sf в одно заключительное состояние.






Рис. 9.6. Построение НКА для ай*+с: (а) для Ь*; (б) для аЬ*; (в) для аЬ*+с.

ются полезными в распознавании образов, и сейчас мы напомним их определение.

Определение. Детерминированным конечным автоматом (ДКА) называется недетерминированный конечный автомат (S, /, 6, So, F), в котором

1) 6(s, е)=0 для всех sgS,

2) 6Cs, а)К1 для всех sS иа1.

Теорема 9.3. Если L - регулярное множество, оно допускается некоторым ДКА.

Доказательство. По теореме 9.2 L допускается некоторым НКА Л1=(5, /, 6, Sg, {sj}). Превратим М в ДКА следующим образом. Сначала найдем такие пары состояний (s, t), что (s, е) (/, е). Чтобы сделать это, построим ориентированный граф G=(S, Е), у которого (s, О 6 тогда и только тогда, когда 6 (s, е) содержит t. Затем вычислим рефлексивное и транзитивное замыкание (j={S,E) графа G. Мы утверждаем, что (s, е)-aj(, е) тогда и только тогда, когда (s, t) принадлежит Е.

Теперь построим такой НКА Л1=(5, /, 6, So, f), что L(A1)=-=L(A1) и в Л1 нет е-переходов.

1) S={so} и {t\b{s, а) содержит для некоторого sgS и некоторого а б/}.

2) Для каждого s б S и каждого а g /

6(s, a)={«{s, t)E и 6(, a) содержит и).





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