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

Покажем, как написать расширенное регулярное выражение для последовательностей в (AiXAj)*, по какой-то причине не отражающих правильные шаги машины М. Как и в лемме 10.2, замечаем, что в правильном вычислении три последовательных символа СхСз на верхней дорожке однозначно определяют символ, стоящий на \х#\ позиций правее Cj. Пусть, как и раньше, этим символом будет /(С1С2С3). Положим

Rc,c.c. = (AiX А,)» [hr (с,с,с,М) П[ЛГ (Ах (А-

-/(слСз))Д,)](Д,хА,). (11.3)

Заметим, что Л"* (ciCjCgA*,) представляет все цепочки из (AjXAa)*, у которых верхняя дорожка начинается с ссз, а /17" (/?i)-все цепочки длины JC#-; у которых нижняя дорожка корректна. Поэтому их пересечение содержит все цепочки длины у которых на нижней дорожке стоит цепочка из ЦИКЛ(л:#), а верхняя начинается с CiCaPs. Теперь должно быть понятно, что R включает все цепочки, удовлетворяющие условию 2, поскольку в них есть шаг, незаконный для М. Кроме них, туда будут включены некоторые цепочки, у которых на нижней дорожке не стоит #(л:#)*; они удовлетворяют и условию 1, и их присутствие или отсутствие в R несущественно. Далее, длина выражения R ограничена длиной выражения Ru умноженной на постоянную (зависящую от М). Чтобы убедиться в истинности этого утверждения, достаточно заметить, что увеличивает длину регулярных выражений в постоянное число раз, зависящее от М. Аналогично, ftf* увеличивает длину выражений не более чем в ЗуДаН раз, ибо если hi {b)=a ровно для k значений Ь, то /г" (а)= (1+2+. . .-f-bft) имеет длину 2k+l. Так как 1/г <А2, то /ix*(a)K3A2. Более того, должно быть ясно, что HAalK поскольку каждый символ из Аа появляется в i. Следовательно, Л-} (С1С2С3А;) и ftf > (Ai (Ai-/ (CiC2C3))Ai) из (11.3) имеют длину 0{\Ri\). Наконец, hiRi) и (AiXAa)*, очевидно, имеют длину 6{\Ri\), где постоянная зависит только от М. Поэтому (11.3) и, значит, R имеют длину 0(/?i+/?il).

Регулярные выражения, отражающие упомянутые выше нарушения структуры, строятся весьма просто, и это построение мы оставляем читателю. Изложенным способом можно построить такое расширенное регулярное выражение Ra, что его длина будет линейна по и оно будет содержать знак дополнения только тогда, когда его содержит или Rl. □

Теорема 11.2. Любой алгоритм, выясняюш,ий, представляет ли данное полурасширенное регулярное выражение ) все цепочки в своем

) Предполагается, что кодировка аналогична использованной в лемме 10.3.



1) Выбор функции 2" несуществен. Можно было бы вместо 2" взять любую экспоненциальную функцию Дп), а вместо 2"/л - любую функцию, которая растет чуть медленнее, чем /(л), при условии, что эти функции конструируемы по памяти.

алфавите, имеет емкостную (и, следовательно, временную) слож-ность, которая для бесконечно многих п не меньше сc°s, где с>0 и 01 - постоянные.

Доказательство. Пусть L - произвольный язык с емкостной сложностью 2", но не 2/п). (Из теоремы П.1 мы знаем, что такой язык существует.) Пусть М - ДМТ, допускающая L.

Предположим, что у нас есть ДМТ Мо с емкостной сложностью /(л), выясняющая, пусто ли дополнение множества, представленного данным полурасширенным регулярным выражением. Тогда можно применить Мо для распознавания языка L следующим образом. Пусть w=aia2. . .а„ - входная цепочка длины п.

1. Построим полурасширенное регулярное выражение Ri для измерителя с длиной 2-fl или более. По лемме 11.1(дляй=л) Ri существует и имеет длину 0(п). Более того, чтобы найти Ri, достаточно 0{п) памяти. Аналогично построим R[, представляющее -iJC, где X таково, что /?1=ЦИКЛ(л:#). В силу леммы 11.2 выражение/?1 имеет длину 0{п) и, как легко видеть, его можно построить, заняв 01п) клеток памяти.

2. Построим полу расширенное регулярное выражение R, представляющее все неправильные вычисления машины М с измерителем Ri. В силу леммы 11.4 можно построить R так, чтобы его длина была не больше СхП, где Ci - постоянная, зависящая только от М.

3. Построим регулярное выражение Ra, представляющее все цепочки из (А1ХА2)*, которые не начинаются на верхней дорожке с # [дойМг.. .а„Ь. . .Ь#, где до - начальное состояние машины М. Очевидно, что существует такое выражение Rs длины 0{п). Таким образом, IRi+RaCiH для некоторой постоянной Ci.

4. Применим Мо к множеству, представленному Rt+Rs, чтобы выяснить, пусто ли его дополнение. Если оно непусто, то существует правильное вычисление машины М с входом w, так что W принадлежит L. В противном случае w не принадлежит L.

Можно построить ДМТ М с емкостной сложностью /(СаЛ* log л), реализующую этот алгоритм распознавания L. Множитель log п в аргументе функции / появился из-за того, что регулярное выражение Ri+Ra над л-символьным алфавитом нужно закодировать цепочкой в фиксированном алфавите. Так как мы предположили, что L имеет емкостную сложность 2", но не 2"/л, то неравенство



f (Сгл" log пу>2/п должно выполняться по крайней мере для некоторых п. Но если бы /(Cjrt log п)>2"/п выполнялось лишь для конечного числа п, то можно было бы построить модифицированный вариант описанного выше алгоритма распознавания, который сначала проверял бы по конечной таблице, совпадает ли \w\ с одним из тех п, для которых / (сп log «)>2"/n, и если да, то узнавал бы из той же таблицы, принадлежит ли w языку L. Поэтому значение /(СгП" logn) должно превосходить 2"/п для бесконечно многих п, так что / {т.)2<*"/°е"/]/ /n/log пгс (с)"/°*для бесконечно многих m и некоторых постоянных Сз>0, с>0 и с>1. □

Следствие. Задача эквивалентности полу расширенных регулярных выражений требует cc"/°s" памяти и времени при некоторых постоянных с>0, с>1 и бесконечно многих п.

Доказательство. Легко показать, что задача пустоты дополнения полиномиально сводима к задаче эквивалентности, поскольку регулярное выражение, представляющее все цепочки, легко пишется и имеет небольшую длину. □

11.4. НЕЭЛЕМЕНТАРНАЯ ЗАДАЧА

Исследуем весь класс расширенных регулярных выражений. Поскольку теперь у нас есть операция дополнения, достаточно рассматривать задачу пустоты, а именно: пусто ли множество, представленное данным регулярным выражением? Мы увидим, что, располагая операцией дополнения, можно представлять регулярные множества еще более короткими выражениями и задача пустоты для расширенных регулярных выражений значительно труднее задачи пустоты дополнения для полурасширенных регулярных выражений.

Определим функцию g{m, п) равенствами

1) g(0, n)=n,

2) g(m, n)=2*"»-i>" для m>0. Тогда g{l, л)=2«, g(2, n)=2" и

g{m, n} = 2•\

где справа стоит башня из т двоек и последняя возводится в степень п. Функция / (rt) называется элементарной, если для некоторого /По она ограничена сверху функцией g(mo, п) для всех, кроме конечного числа, значений п.

С помощью техники разд. 11.3 можно доказать, что задача пустоты для всего класса расширенных регулярных выражений не может иметь емкостную сложность S (п) ни для какой элементарной





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