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

строить регулярное выражение длины не более Ci/?i=c(Ci)~>mS представляющее ЦИКЛ(г/$), где «/$>2i#i>2«"-i"»=g(t, т). О

Теорема 11.3. Пусть S (л) - любая элементарная функция. Тогда не существует ДМТ с емкостной (и, следовательно, временной) сложностью, ограниченной сверху функцией S (п), которая могла бы установить, пусто ли множество, представленное произвольным расщиренным регулярным выражением.

Доказательство. Допустим противное, т. е. что нашлась ДМТ Ml с памятью, ограниченной функцией g{ko, п), которая выясняет, пусто ли множество, представленное расширенным регулярным выражением. По теореме 11.1 существует язык L, допускаемый некоторой ДМТ М с памятью, ограниченной функцией giko+l, rt), но не допускаемый никакой ДМТ с памятью, не большей giko+l, п)1п. Предположив, что Mi существует, можно построить ДМТ Мг, распознающую язык L следующим образом.

1. По данной входной цепочке waya. . .а„ длины л машина Mj строит расширенное регулярное выражение длины diH (где di - постоянная, не зависящая от л), представляющее измеритель с длиной, не меньшей g(feo+l, «)• Для построения Rl используется лемма 11.6.

2. Далее Mj строит расширенное регулярное выражение R2, представляющее правильные вычисления с измерителем Ri для ДМТ М, которая допускает L и требует для этого не более g{ko+\, л) клеток памяти. По лемме 11.5 можно добиться, чтобы было /?2<2/?1 для некоторой постояннойdj.

3. Затем Mj строит расширенное регулярное выражение R3, представляющее правильные вычисления машины М с измерителем Rl и начальным МО Co=[q<fli\a2. . . a„bb. . ., где 9о - начальное состояние машины М, а именно

;?з = П ([<7„а J aj... a„b» #) (А х А J*,

где hi - гомоморфизм из леммы 11.5 и AiXAj - алфавит выражения R. По лемме 11.3 /?зК/?2+аП для некоторой постоянной з>0. Поэтому

iRldidn+dn. (11.4)

4. Наконец, Ма кодирует R3 в фиксированном алфавите, как в теореме 11.2, и использует Mi для проверки пустоты множества, представленного расширенным регулярным выражением R3. Если оно пусто, что Ма отвергает вход хю, а если нет, то допускает его. Таким образом, Ма допускает L.

Теперь нетрудно видеть, что наибольшей памяти требует шаг 4. На этом шаге машине Mi нужна память g{ko, /?3log/?3), чтобы выяснить, пусто ли множество, представленное выражением Rs-



Следовательно, и машине Мз нужно столько же памяти. Учитывая границу (11.4) для ;?з, заключаем, что Мз имеет емкостную сложность S{n)=d,g{ko, dbtiHogn) для некоторых постоянных и dj, поскольку для всех, кроме конечного числа, значений п первое слагаемое в правой части (11.4), а именно diditi, больше второго, т. е. dsti. Однако, рассуждая, как в приведенном доказательстве теоремы 11.2, можно показать, что емкостная сложность машины Мз должна быть больше g{ko+l, п)/п для бесконечно многих п. Таким образом, если существует М а, ТО

g{k, + l, n)/n<d,g(ko, d,n4ogn) (11.5)

для бесконечно многих п. Но независимо от выбора d, и ds лишь для конечного числа значений п справедливо (11.5) (это легко проверить). Итак, машины Мз не существует, и, значит, не существует Ml. Поэтому проблема пустоты для расширенных регулярных выражений неразрешима никакой машиной Тьюринга с емкостной сложностью, ограниченной элементарной функцией. □

УПРАЖНЕНИЯ

11.1. Функцию Т{п) называют конструируемой по времени, если некоторая ДМТ М при данном входе длины п делает ровно Т{п) шагов до своей остановки. Покажите, что функции

(а) п\

(б) 2«,

(в) т

конструируемы по времени.

*11.2. Покажите, что всякая функция, конструируемая по времени, конструируема по памяти, и если функция S (л) конструируема по памяти, то с" конструируема по времени для некоторого целого числа с.

*11.3. Покажите, что если язык L допускается за время Г (л) какой-нибудь fe-ленточной ДМТ (НМТ), то он допускается некоторой одноленточной ДМТ (НМТ) с временной сложностью О (Т (л)).

*11.4. (Иерархия повремени для ДМТ) Покажите, что если функции Ti{n) и Та (л) конструируемы по времени и

inf = 0, „ „ Тз(п)

то некоторый язык допускается ДМТ за время Га (л), но не Ti(n). Указание: В силу упр. 11.3 достаточно диагонализировать по одноленточным ДМТ с временной сложностью не выше Ti{n). Саму диагонализацию можно выполнить с помощью многоленточной ДМТ.



. ,Ti(n)\ogT,{n) „

то некоторый язык допускается ДМТ за время Та{п), но не Ti{n).

*11.9. Покажите, что если L допускается ДМТ (НМТ) М с емкостной сложностью S (л) и временной сложностью Т (л), а с>0 - произвольная постоянная, то L допускается некоторой ДМТ (НМТ) М с емкостной сложностью МАХ(с5(л), л+1) и временной сложностью МАХ(сГ(л), 2л). Указание: М должна начинать свою работу с сжимания блоков клеток машины М так, чтобы каждый такой блок помещался в одну клетку машины М.

11.10. Покажите, что если L допускается НМТ с временной сложностью Т (л), то найдется такая постоянная с, что L допускается ДМТ с временной сложностью с*").

11.11. Пусть Ti и Га - такие функции, что

Покажите, что существует язык, допускаемый РАМ за время Та (л), но не Ti{n) (время определяется по логарифмическому весовому критерию).

11.12. Закончите доказательство леммы 11.2.

*11.13. По данному расширенному регулярному выражению/?i для множества ЦИКЛ(л:#) постройте расширенное регулярное

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

**11.5. Покажите, что для каждого целого числа fel существует язык, допускаемый некоторой НМТ с емкостной сложностью но не допускаемый никакой НМТ с емкостной сложностью л*.

**11.6. Докажите тот же результат, что и в упр. П.5, для временной сложности.

В следующих двух упражнениях иерархия по времени для ДМТ уплотняется.

**11.7. Покажите, что всякий язык L, допускаемый некоторой fe-ленточной ДМТ с временной сложностью Т (л), допускается двух-ленточной ДМТ с временной сложностью 0(Т{п) log Т(п)).

11.8. С помощью результата упр. 11.7 докажите, что если функции Ti{n) и Та (л) конструируемы по времени и





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