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

2, 3 или 4, но нарушают условие 1, т. е. цепочки вида . .

.. где \w,\=p(n) HWtT* (QxT)T*. Однако для простоты мы выпишем выражения, определяюш,ие множества цепочек, которые удовлетворяют условию 2, 3 или 4 и нарушают условие 1, а также некоторых цепочек, удовлетворяющих не только условию 2, 3 или 4, но и условию 1. Так как цепочки последнего типа уже представлены ъ Rx ъ силу определения выражения А, их наличие или отсутствие в В, С и D несущественно.

Считая, что входная цепочка имеет вид x=aiat. . .а„, полагаем В=Вг+В,+. . .+Вр,„„ где

Б, = # (А - [q,a,]) А" («>" # (А + #)»,

Г#Л-ЧГ-{а,.})А()-#(Д + #)., 1</<п, \#А-ЧГ-{Ь})А()-#(Д+#)*, n<t<p(n).

Таким образом. В; отличается от начального МО по крайней мере в i-M входном символе. Очевидно, В имеет длину 0(р{п)), причем мультипликативная постоянная зависит только от М.

Положим С=((А+#)-({9}ХТ))*. Длина этого выражения, конечно, зависит только от М.

Наконец, построим D. Пусть дана цепочка у, представляющая правильное (т. е. позволяющее фактически реализовать) вычисление машины М. Тогда у имеет вид #wi#w2#. . где \wi\=p(n)

для каждого i и Wt+t - это МО, которое получается из Wt за один шаг работы машины М. Заметим, что по данным трем последовательным символам С1С2С3 цепочки у можно однозначно определить символ, назовем его / (CjCaCs), который должен появиться в цепочке на р {п)+1 символов правее Cj. Например, если ci, Ct и Сз все принадлежат Т, то с2 не может измениться в следующем МО, так что /(с1С2Сз)= =Cj. Если Ci и Са принадлежат Т, Сз=[дХ] - символ из QxT и 6{q, Х)=(р, X, L), то /(CiC2Cs)=[pC2l. Остальные правила для определения /, включая те, что соответствуют случаю, когда Ci или с» принадлежит Qx Г или один из символов с, равен #, должны быть очевидны; оставляем их в качестве упражнения.

D представляет собой сумму членов

1>..с.г, = (А + #)• ССаСз (А -f #)" С)-1 / (ССаСз) (А + #)

ДЛЯ всех ci, С2 и Сз из AU{#}, где7(с1С2Сз)=Д U {#} -/(CjCaCa). Ясно, что выражение D имеет длину 0{р (п)) и его можно выписать за время 0(р («)), где мультипликативная постоянная зависит лишь от М.

Таким образом, регулярное выражение R можно построить за время р(п), где р - полином, растущий по порядку как р*. Более того, R представляет множество (А и {#})* тогда и только тогда, когда х не допускается машиной М. □



Итак, в лемме 10.2 построено регулярное выражение над алфавитом А и {#}. размер которого зависит от М. Мы хотим рассуждать о "языке регулярных выражений, дополнения которых (относительно их алфавитов) представляют непустые множества". Так как язык должен определяться над конечным алфавитом, мы будем кодировать регулярное выражение над конечным алфавитом 2 следующим образом:

1) +, *, 0, ей скобки обозначают сами себя,

2) i-й символ алфавита 2 (в произвольном порядке) обозначается через где w - десятичное представление числа i.

Таким образом, для кодирования любого регулярного выражения над любым алфавитом достаточно 17 символов из алфавита

Г={+. *, 0. е, (, ), #, О, 1.....9}.

Определим язык ЬгГ* как множество кодов тех регулярных выражений R, дополнения которых представляют непустые множества. Если R - выражение над алфавитом 2, то дополнение берется относительное*. Заметим, что если выражение R имеет длину п2, то длина его кода не превосходит Зп log п.

Лемма 10.3. Lr принадлежит классу -SPACE.

Доказательство. По теореме 10.1 достаточно построить НМТ М, которая допускает язык Lr, работая с полиномиально ограниченной памятью. Пусть/? - регулярное выражение, код которого подан на вход машины М. В силу теоремы 9.2 по данному регулярному выражению длины п можно построить недетерминированный конечный автомат Л с не более чем 2п состояниями, распознающий язык, представленный этим регулярным выражением. НМТ М сначала строит автомат А по коду выражения R, поданному машине М. Заметим, что по теореме 9.2 можно построить функцию переходов автомата А за время, не превосходящее 0{п).

Допустим, что дополнение множества, представленного выражением R, непусто. Тогда существует цепочка x=ai. . .а„, не принадлежащая языку, представленному выражением R. М угадывает ее символ за символом. Для хранения множества Sj состояний, в которых А может оказаться после прочтения Oi. . .а,-, lim, машина М использует массив из 2п битов. Она начинает с множества So состояний, достижцмых из начального состояния автомата А только с помощью е-переходов. После того как она угадает Ui. . .а,-, автомат А может находиться в одном из состояний множества Sj. Когда М угадывает следующий входной символ а+ь она прежде всего вычисляет ri+j={ss€6(s, Oj+i) и sgS;}, где -функция переходов автомата А, а затем строит Si+u добавляя к Tj+i все состояния из 6(s, е) для s из Ti+i. (Обратите внимание на аналогию с алгоритмом 9.1.)



1) в действительности при сделанных предположениях о росте Г мы не можем получить требуемое неравенство т-\-Т(тХТ(2т). Для завершения доказательства можно использовать упр. 11.9.-Ярил. ред.

Когда М угадает fliOa. . .а„, она выяснит, что S„ не содержит заключительного состояния автомата А. Обнаружив это, машина М допускает свой вход, т. е. код регулярного выражения R. Таким образом, М допускает код выражения R тогда и только тогда, когда дополнение множества, представленного выражением R, непусто. □

Теперь покажем, что язык Lr, состоящий из кодов тех регулярных выражений, которые представляют множества с непустыми дополнениями, полон для полиномиальной памяти.

Теорема 10.14. Если Lr допускается ДМТ с временной сложностью Т (п)п, то для каждого L G -SPACE найдется такой полином Pi, что L допускается за время Т{р{п)).

Доказательство. Пусть М будет ДМТ, допускающей L. В силу леммы 10.2 и рассуждений, проведенных выше, существует алгоритм с полиномиально ограниченным временем работы, скажем с временной сложностью pi(n), который по входной цепочке х строит регулярное выражение R. Это выражение в фиксированном 17-символьном алфавите, и, разумеется, оно не длиннее pi(x). По лемме 10.2 его дополнение пусто тогда и только тогда, когда xL. По предположению можно проверить пустоту этого дополнения за Ti\Rx\)=T{pj,{\x\)) шагов. Построение R занимает Pi(a;) шагов, а проверка пустоты - T{pi{\x\)) шагов. Так как Т{п)п, то для завершения доказательства достаточно взять р,(п)2рг{пП О

Следствие. принадлежит -TIME тогда и только тогда, когда 5-TlME=.5>-SPACE.

Доказательство. Если 5-TIME=5-SPACE, то L,. принадлежит -TIME по лемме 10.3. Обратное следует из теоремы 10.14 с полиномиальной функцией Т{п). О

Теорема 10.15. Если L г допускается НМТ с временной сложностью Т(п)п, то для каждого L--SPACE найдется такой полином Pi, что L допускается НМТ за время T(pi{n)).

Доказательство. Аналогично доказательству теоремы 10.14. □

Следствие. Lr принадлежит olV.-TIME тогда и только тогда, когда оГ-Т1МЕ=-5РАСЕ.





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