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

ненное дерево может давать ту же информацию, что и исходное позиционное дерево, и потому его можно использовать в тех же алгоритмах идентификации.

Алгоритм 9.5 можно модифицировать так, чтобы он строил уплотненные позиционное и вспомогательное деревья за линейное время. Мы не приводим здесь этот модифицированный алгоритм потому, что он аналогичен алгоритму 9.5, а также потому, что во многих приложениях можно ожидать, что размер позиционного дерева будет пропорционален длине входной цепочки. В замечаниях по литературе указаны работы, в которых излагается алгоритм с уплотнением позиционного дерева и другие его приложения.

УПРАЖНЕНИЯ

9.1. Постройте регулярные выражения и графы переходов конечных автоматов для следующих регулярных множеств цепочек в алфавите /={а, Ь).

(а) Все цепочки, начинающиеся и кончающиеся символом а.

(б) Все цепочки, не содержащие двух символов а подряд. *(в) Все цепочки, содержащие нечетное число символов а и четное число символов Ь.

*(г) Все цепочки, не содержащие подцепочки aba.

9.2. Докажите, что множество, допускаемое НКА на рис. 9.1, имеет вид (a+b)*aba.

9.3. Постройте НКА, допускающие регулярные множества

(а) {a+b)*(aa+bb),

(б) a*b*+b*a*,

(в) (а+е)(6+е)(с+е).

9.4. Покажите, что дополнение регулярного множества регулярно.

*9.5. Покажите, что множества цепочек

(а) {а"Ь\п1},

(б) lww\w{a, 6}*},

(в) {w\w{a, b}* и w=w} (т. е. множество палиндромов) не регулярны.

9.6. Пусть x=aiat. . .an - данная цепочка и а - регулярное выражение. Модифицируйте алгоритм 9.1 так, чтобы он находил наименьшее число k, а по нему (а) наименьшее / и (б) наибольшее /, такое, что ajaj+i. . .а принадлежит множеству, представленному выражением а. Указание: Каждому состоянию из St поставьте в соответствие целое число

*9.7. Пусть X к а те же, что и в упр. 9.6. Модифицируйте алгоритм 9.1 так, чтобы он находил такое наименьшее / и по нему наи-



большее k, что ajuj+i. . принадлежит множеству, представленному выражением а.

9.8. Пусть ;с и а те же, что и в упр. 9.6. Постройте алгоритм, который находил бы все подцепочки в х, принадлежащие множеству, представленному выражением а. Какова временная сложность вашего алгоритма?

*9.9. Пусть / - алфавит и 0 - символ, не принадлежащий /. Цепочкой с несущественными символами (ЦСНС) назовем цепочку в алфавите / U {0}. Будем говорить, что ЦСНС Ьф. . .bn идентифицируется с ЦСНС flifla. . .а„ в позиции i, если для всех /, г/п, либо aj=bj i+, либо один из символов Uj или bj-i+i есть 0. Покажите, что для фиксированного алфавита / проблема определения позиций, в которых одна ЦСНС идентифицируется с другой, эквивалентна по асимптотической временной сложности {и/или)-умноже-

нию, т. е. операции вида Cj=\/diAS}-i+u где все Cj, dj и Ct булевы

**9.10. Покажите, что можно определить позиции, в которых одна ЦСНС идентифицируется с другой, за время Оа{п log п log log п). Указание: Используйте упр. 9.9 и алгоритм Шёнхаге - Штрассена для умножения целых чисел.

9.11. Напишите алгоритм сложности 0{п), который по данным цепочкам aiOa. . .а„ и bib. . .ft„ узнавал бы, существует ли такое k, что ai=ft,ft+,-,mod„ для Ki<n.

9.12. С помощью алгоритма 9.3 постройте машины для цепочек у, равных

(а) abbbbabbbabbaba,

(б) abcabcab.

9.13. Докажите теорему 9.8.

9.14. Пусть S={i/i, у 2, ... , г/„} - множество цепочек. Напишите алгоритм, который находил бы все вхождения цепочек из S в цепочку-текст х. Какова временная сложность вашего алгоритма?

*9.15. Постройте 2ДМА, допускающие языки (а) {хсухсуг. . .cyjml, х{а, Ь}*, yi{a, b}* для l<t<m и хотя бы одна из цепочек г/i, г/а, ... , г/„ входит в х).

(б) (в) (г)

xyy\x,yei* и \у\>\}, Х1СХ2. . .cXn\Xi{a, b}* для l<t<n и все Xt различны}, xiCXa. . .cXhdyicya. . .cyi\ все Xi и yi принадлежат {а, b)* Xi=yf для некоторых i и /}.

9.16. Рассмотрим 2ДМА Р с правилами:

6(s„, а, Z„) = 6(s„, а, Л) = (5„, +1, push Л), 6(s„, $, Л) = (5„ -1),



6(Si, а, A) = 6{Si, а, Zg) = {Si, -1, pop), 6(s„ ф, Zo) = (Si, 0).

(а) Запишите все поверхностные конфигурации автомата Р для входа аа.

(б) Примените алгоритм 9.4 для вычисления массива ТЕРМ.

*9.17. Предположим, что 2ДМА может из позиции i перейти за один шаг в любую из позиций

(а) n-i,

(б) 1/2,

(в) п/2,

(г) log п,

где п - длина входа. Покажите, что ни одна из этих модификаций не увеличивает распознающей силы 2ДМА. Какие операции вы можете добавить, чтобы не увеличить при этом допускающей силы 2ДМА?

**9.18. Постройте 2ДМА, допускающий язык {tWitwfШаШШзШы Ш1, Шг, Шз€ {а, Ь}+ и и{а, Ь)*). Указание: Пусть х - входная цепочка. Напишите подпрограмму для нахождения такой кратчайшей цепочки Wi, что WiWfy=x. Затем примените вашу подпрограмму к г/ и т. д.

**9.19. Постройте алгоритмы, распознающие за линейное время языки

(а) {!м1у«ше/*}*,

(б) Iwwulw, uI*, kll},

(в) {WiWi. . . Wn\wi{a, b)* и каждая цепочка Wt является непустым палиндромом четной длины}.

9.20. Напишите алгоритм, который по двум цепочкам aifla- • • ., .а„ и bibi. . . bp отыскивает за линейное время такое наибольшее число /, что aiflj. . .Ui - подцепочка цепочки Ьф,. . .bp. Как с помощью этого алгоритма проверить, является ли данная цепочка палиндромом?

В следующих четырех упражнениях обсуждаются некоторые варианты магазинных автоматов.

*9.21. k-головчатым 2ДМА называют 2ДМА с k независимыми читающими головками на входной ленте. Покажите, как распознать за время 0(п*), допускается ли входная цепочка длины п Л-голов-чатым 2ДМА.

9.22. Односторонним магазинным автоматом называют магазинный автомат, никогда не сдвигающий свою входную головку влево. Недетерминированным магазинным автоматом (НМА) называют автомат, у которого есть нуль или более возможностей для выбора





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