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

Теорема 9.6. Алгоритм 9.2 вычисляет f.

Доказательство. Докажем индукцией по /, что /(/) - такое наибольшее целое /</, что bifca- • bi=bj-i+ibj-i+i. . .bj. Если такого i нет, то f(j)=0.

По определению /(1)=0. Допустим, что предположение индукции верно для всех Л</. При вычислении /(/) алгоритм 9.2, выполняя строку 4, сравнивает с b/(y i,+i.

Случай 1. Пусть bj=bfj i+i. Поскольку /(/"-1) - это такое наибольшее i, что fci. . .bt=bj~i. . .bj-i, равенство/(/)=/-fl выполняется. Таким образом, в строках 5 и 6 /(;) вычисляется правильно.

Случай 2. Пусть bjФbfJ..+. Тогда надо найти наибольшее значение i, для которого bi. . .bj=b; j. . .bji и bi+i=bj, если такое i существует. Если такого i нет, то очевидно, что /(/)=0, и /(/) правильно вычисляется в строке 5. Пусть tj, i, . . .- наибольшее, второе по величине и т. д. значения i, для которых Kbi-• .bi = bj i.. .bj i.

С помощью простой индукции убеждаемся, что ii=f(j-1), ia=

=/Ol)=r(/-l).....th=/((h-i)=P(/-l), поскольку Ift-1-ЭТО

(k-l)-e no величине значение i, для которого bi. . .bi=bj-i. . .bj-i, a ill - наибольшее значение i<.ik-i. Для которого bi. . .bi=

• -bi.bj-i. . .bj-i. Строка 4 просматривает «1, /.....

по очереди, пока не найдет такое i, что bi. . .bi=bj-t. . .bj-i и bi+i=b), если такое i существует. По окончании выполнения while-оператора будет i=i„, если такое t„ существует, и, значит, f{j) правильно вычисляется в строке 5.

Таким образом, /(/) правильно вычисляется для всех /. □

Теорема 9.7. Алгоритм 9.2 вычисляет f за 0(1) ишгов.

Доказательство. Строки 3 и 5 имеют фиксированную сложность. Сложность while-оператора пропорциональна числу уменьшений значения i оператором i-f-fii), который стоит после do в строке 4. Единственный способ увеличить i - это присвоить 1 в строке 6, затем увеличить / на 1 в строке 2 и положить i-f(j-1) в строке 3. Поскольку вначале (=0, а строка 6 выполняется не более I-1 раз, заключаем, что while-оператор в строке 4 не может выполняться более / раз. Поэтому строка 4 требует 0(1) времени. Остальная часть алгоритма, очевидно, имеет сложность 0(1), и потому весь алгоритм тратит 0(1) времени. □

С помощью тех же рассуждений, что и в теореме 9.6, можно доказать, что после прочтения слова CiCa. . .а машина идентификации образов My будет находиться в состоянии i тогда и только тогда, когда bifcj- • -bi - самый длинный префикс цепочки у, который является суффиксом цепочки aia. . .а,,. Поэтому машина My правиль-



НО находит самое левое вхождение цепочки у в цепочку-текст д:= =aia2. . Мп.

С помощью тех же рассуждений, что и в теореме 9.7, можно доказать, что при обработке входной цепочки х машина My изменит свое состояние не более 2jcl раз. Поэтому можно узнать, является ли у подцепочкой цепочки х, проследив изменения состояния машины My на входе х Для этого надо лишь знать значение функции отказов на у. По теореме 9.7 эти значения функции / можно найти за время 0(\у\). Следовательно, узнать, является ли у подцепочкой цепочки X, можно за время 0(х+г/), не зависящее от размера алфавита. Если же алфавит цепочки-образа мал, а цепочка-текст значительно длиннее образа, то можно смоделировать некоторый ДКА, допускающий язык 1*у. Этот ДКА в точности один раз меняет состояние на каждом входном символе.

Алгоритм 9.3. Построение ДКА для /*у

Вход. Цепочка-образ «/=М». . -Ь, в алфавите /. Для удобства

вводим новый символ fef+j/.

Выход. ДКА М, для которого L(M)=I*y. Метод.

1. Алгоритмом 9.2 строим функцию отказов f для у.

2. Пусть M=(S, I, 6, О, {/}), где S={0, 1...../}, а 6 определяется так:

begin

for /=1 until I do 6(/-1, fcy) -/; for fcg/, ЬфЬ do 8(0,b*-0; for /=1 until / do

for fcg/, bbji do 6(/, fc) 6 (/(/), b) end □

Теорема 9.8. Алгоритм 9.3 строит такой ДКА М, что

(О, аА...а,)Н-*(/, е),

тогда и только тогда, когда Ьфз. . .bj - суффикс цепочки aia,. . .а, но bibi- . .bi при i>i не является суффиксом для Uia,. . .а,,.

Доказательство. Доказательство проводится индукцией по А с помощью тех же рассуждений, что и в теореме 9.6. Оставляем его читателю. □

Пример 9.10. ДКА М для y=aabbaab, построенный алгоритмом 9.3, изображен на рис. 9.15.

На входе x=abaabaabbaab автомат М делает такие переходы:

*) Напомним, что состояние машины My есть на самом деле указатель позиции в цепочке-образе у. Поэтому изменение состояния машины My можно реализовать, непосредственно перемещая указатель по у.




Рис. 9.15. Детерминированный конечный автомат, допускающий {а-\-Ь)*о,аЬЬааЬ.

Вход: аЬааЪааЬЬааЬ

Состояние: 0101231234567

Единственное отличие его от М.у состоит в том, что М заранее вычисляет состояние, в которое следует переходить в случае несовпадения. Поэтому он делает в точности один переход на каждом входном символе. □

Основные результаты раздела суммируем в следующей теореме.

Теорема 9.9. За время 0(л;Ц-1/) можно выяснить, является ли у подцепочкой цепочки х.

Теперь разберем случай, когда даны несколько цепочек-образов Уи Уг.....у. Наша задача - распознать, входит ли одна из цепочек yt в данную цепочку x=aia2. . .а„. К этой задаче можно также применить методы данного раздела. Сначала построим скелетную машину для Уи уг, . . . , y,t. Она будет деревом. На этом дереве вычислим функцию отказов за время, пропорциональное /=i/i+ + • Потом тем же способом, что и раньше, построим

машину идентификации образов. Тогда за 0{1-{-п) шагов мы узнаем, является ли какая-нибудь цепочка yi подцепочкой цепочки х. Детали оставляем в качестве упражнения.

9.4. ДВУСТОРОННИЙ ДЕТЕРМИНИРОВАННЫЙ МАГАЗИННЫЙ АВТОМАТ

Как только мы заподозрили, что существует алгоритм сложности 0(jc+i/), распознающий, входит ли у в jc, его уже нетрудно построить. Но что может заставить нас подозревать о существовании такого алгоритма? Одна из возможных причин возникает при изучении двусторонних детерминированных магазинных автоматов (2ДМА для краткости).

2ДМА представляет собой специальный тип машины Тьюринга, допускающей язык. Многие задачи распознавания образов можно переформулировать в терминах задач распознавания языков. Например, пусть L - язык {хсу\х, уГ, с1 и у - подцепочка це-





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