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

очередного шага. Таким образом, различаются четыре семейства магазинных автоматов: 1ДМА, 1НМА, 2ДМА и 2НМА. Язык, допускаемый 1НМА, называется бесконтекстным.

(а) Покажите, что {wcw\w{a, Ъ}*} допускается некоторым 1ДМА.

(б) Покажите, что {ww\w{a, b}*) допускается некоторым 1НМА. (Этот язык не может допускаться никаким 1ДМА.)

(в) Покажите, что {mox\w, х{а, &}*,а)>1} допускается некоторым 2НМА. (Этот язык не может допускаться никаким IHMA.)

*9.23. Покажите, что язык L порождается бесконтекстной грамматикой в нормальной форме Хомского ) тогда и только тогда, когда он допускается некоторым 1НМА.

*9.24. Покажите, что за время О(п) можно распознать, допускается ли входная цепочка длины п некоторым 2НМА.

9.25. Постройте позиционные деревья для цепочек

(а) baaaab,

(б) abababa$.

9.26. Покажите, что позиционное дерево для a"b"a"b"% содержит га+бп-Н! узлов.

*9.27. Покажите, что позиционное дерево для случайной входной цепочки X содержит 0(д:) узлов при условии, что символы во всех позициях выбираются из фиксированного алфавита равновероятно и независимо.

9.28. Для позиционных деревьев из упр. 9.25 найдите

(а) вспомогательные деревья,

(б) двоичные векторы В„ для каждого узла v.

9.29. Покажите, что для каждого позиционного дерева существует вспомогательное дерево.

9.30. Завершите доказательство леммы 9.4, показав, что Г, и

Ai правильно строятся по + 1 и Л i + l.

*9.31. Покажите, что с помощью позиционного дерева для х можно проверить, является ли какая-то цепочка из у и у.,. . ., у„ подцепочкой в х, за время порядка

\У1\ + \У2\ + • + \уЛ

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

1) См. определение перед упр. 2.34.



9.33. Напишите эффективный алгоритм, который по данным цепочкам X и bib г. . .bp находил бы для каждого i, lip, длиннейшую подцепочку в х, являющуюся префиксом цепочки bibi+i. . .bp.

9.34. Напишите эффективный алгоритм, который по данным двум цепочкам x=aia2. . .а„ и у=Ьт,Ьг. . .Ьп в алфавите / находил бы кратчайшее представление для у в виде CiCj. . .с„, где Ci - символ из / или символ, обозначающий подцепочку цепочки х. Например, если x=abbabb и y=ababbaa, то [1 : 2][4 : 6]аа - представление для у длины 4 (U : j] обозначает подцепочку fljaj+i. . .aj цепочки д:). Указание: Воспользуйтесь упр. 9.33.

9.35. Докажите, что уплотненное позиционное дерево для цепочки длины п содержит не более 4п-2 узлов.

**9.36. Напишите алгоритм, который за время 0(п) находил бы уплотненное позиционное дерево для цепочки длины п.

9.37. Цепочка x=aia2. -fln называется подпоследовательностью цепочки y=bib2. .bp, если OiOj. . .an=bifii. . .6; для некоторых 1<12<- . <.in (т. е. X получается из у вычеркиванием нуля или более символов). Напишите алгоритм сложности 0(л;г/) для нахождения самой длинной общей подпоследовательности цепочек х и у.

9.38. Напишите алгоритм, который по двум данным цепочкам X тл у находил бы кратчайшую последовательность вставок и удалений одного символа, превращающую х ъ у.

Проб.аемы для исследования

9.39. Можно ли улучшить оценку времени в упр. 9.10?

9.40. Необходимо ли время 0(ад:) для распознавания вхождения в X цепочки из языка, представленного регулярным выражением а?

9.41. -головчатый 2ДМА можно промоделировать на РАМ за время 0(п*) (упр. 9.21). Может ли каждый бесконтекстный язык допускаться некоторым 2-головчатым 2ДМА? Если да, то каждый бесконтекстный язык можно было бы распознать на некоторой РАМ за время 0{п).

9.42. Существует ли бесконтекстный язык, не допускаемый никаким 2ДМА?

9.43. Существует ли язык, допускаемый некоторым 2НМА, но не допускаемый никаким 2ДМА?

9.44. Можно ли улучшить оценку времени в упр. 9.37? (См. Ахо, Хиршберг, Ульман [19741, где для получения оценок использована модель дерева решений.)



Замечания по литературе

Эквивалеитиость конечных автоматов и регулярных выражений установлена Клини [1956]. Недетерминированные конечные автоматы изучались Раби-ным, Скоттом [1959], которые доказали их эквивалентность детерминированным. Алгоритм идентификации цепочек, задаваемых регулярным выражением (алгоритм 9.1), построен на основе алгоритма Томпсона [1968]. Эренфойхт, Цайгер [1974] обсуждают сложность НКА как устройства для классификации образов. Распознавание вхождения одной цепочки в другую за линейное время (алгоритм 9.3) взято у Морриса, Пратта [1970] ). Моделирование 2ДМА за линейное время, а также обобщение в упр. 9.21 принадлежат Куку [1971а]. Свойс1ва 2ДМА изучали Грей, Харрисон, Ибарра [1967]. Моделирование 2НМА за время О(п) (упр. 9.24) описано у Ахо, Хопкрофта, Ульмана [1968]. Упр. 9.15(6) принадлежит Честеру, а упр. 9.19(b) - Пратту. Решение упр. 9.19(b) приведено в работе Кнута, Пратта [1971].

Материал разд. 9.5, касающийся позиционных деревьев, а также понятие уплотненного позиционного дерева можно иайти у Вайнера [1973]. Там же содержатся решения упр. 9.20 и 9.31-9.36 вместе с некоторыми другими приложениями; см. также Кнут [19736]. Карп, Миллер, Розенберг [1972] дают несколько алгоритмов идентификации, касающихся повторяющихся цепочек. Упр. 9.9 и 9.10 о совпадении цепочек с несущественными символами принадлежа? Фишеру, Патерсону [1974]. Вагнер, Фишер [1974] приводят решение упр. 9.38. В их статье и статье Хиршберга [1973] обсуждаются алгоритмы для задачи об общей подпоследовательности (см. упр. 9.37).

1) Более сильный результат о распознавании вхождения одной цепочки в другую был получен Ю. В. Матиясевичем в 1969 г. (См. его статью [1971].) Для обычной постановки задачи вопрос о сложности идентификации цепочек символов и близких задач решен в работе Слисенко [1977].- Прим. перев.





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