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

щие свойством (2), представляются выражением

Si = S [AaAUai[{А-а) Л» + e] +

+ [е + Л» (Л - Л,)] AUa, [(Л-а,) А* + е]].

Наконец, цепочки, не обладающие свойством (3), представляются выражением

S, = Ла, И«А-И+ + (Л- а, ,)а, 1 (Л-а,.,) + + (Л + (Л -a,.i)a, i (Л -а„) Л».

В 5з первое слагаемое обозначает все цепочки, имеющие более двух вхождений символа а-р а также цепочки с ровно двумя вхождениями символа второе из которых не приходится на правый конец цепочки. Таким образом, S, и Sj U S3 представляет ~~\Xf, x. Легко видеть, что длина выражения S1US2US3 естьОС). □

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

Определение. Гомоморфизмом из в называется такая функция /г, что h{xy)=h{x) h(y) для любых цепочек х и у. Отсюда непосредственно следует, что/г(е)=е и hiaiUi- .an)=h(ai)li(ai). . . .. ./г(а„). Таким образом, гомоморфизм h однозначно определяется значением h(a) для каждого а 61.

Говорят, что гомоморфизм h сохраняет длину, если h (а) - одно-буквенное слово из Еадля каждого а 6 El. Гомоморфизм, сохраняющий длину, просто переименовывает символы, возможно отождествляя несколько символов путем переименования их в один символ. Если 1625, то h- {w)={x\h{x)=w}. Если LeZ, то h-HL)={x\hix)eL}.

Пример 11.2. Пусть Ei={a, b, с} и Е2={0, 1}. Определим гомоморфизм h равенствами h (а)=010, h (b)= 1 и h (с)=е. Тогда h {аЬс) = =0101. Заметим, что h не сохраняет длину. Пусть L - язык, пред-сгавляемый расширенным регулярным выражением l-f-1I*, или, в эквивалентной форме, обычным регулярным выражением 1+(0--4-1)*0(04-1)*. Тогда h-(L) представляется расширенным регулярным выражением c*bc*+-\{b+c)* или обычным регулярным выражением c*bc*+{a+b+c)*a{a-rb+c)*. О

Лемма 11.3. Пусть h - сохраняющий длину гомоморфизм из 1,1 в 1,1, а Ri - расширенное регулярное выражение, представляющее множество SeSj. Можно построить такое расширенное регулярное выражение Ri, представляющее /г-(S), что его длина будет



Верхняя дорожка

• • •

Нижняя дорожка

• • •

Рис. 11.1. Последовательность МО с измерителем.

ограничена длиной выражения R, умноженной на постоянную (за-висящую только от h), и оно будет содержать знак дополнения только тогда, когда его содержит R.

Доказательство. Заменим каждое вхождение в R2 символа из s2 регулярным выражением, представляющим множество символов, отображаемых в этот символ гомоморфизмом/г. Например, если {fli, Аа,- • ., «г} - множество символов, отображаемых в а, заменим а на (01+02+- +аг)- Пусть Ri - расширенное регулярное выражение, получающееся в результате такой замены. Доказать, что Rl представляет h- (S), можно индукцией по числу вхождений в Ri знаков +, •, *, П и -1. □

Теперь мы можем представить последовательности МО машин Тьюринга во многом так же, как делали это в лемме 10.2. Иными словами, для данной машины Тьюринга M=(Q, Т, I, б, Ь, qo, qi) представляем ее мгновенное описание последовательностью символов из Г и еще одним символом вида [qX], где qQu ХТ, который указывает состояние и положение головки. При необходимости можно дополнить МО пустыми символами, чтобы все МО одного и того же вычисления были одинаковой длины.

Чтобы облегчить сравнение символов одного МО с "соответствующими" символами в следующем МО, приложим к самим МО измеритель, длина которого равна длине этих МО. Формально мы используем "двухдорожечную" цепочку символов, в которой верхняя дорожка содержит последовательность МО, а нижняя - повторяющийся измеритель. Здесь "двухдорожечными" символами служат пары [а, Ь], где а - символ на верхней дорожке, а b - на нижней. Это изображено на рис. 11.1, где использован измеритель ЦИКЛ(л:#) {х может быть любой цепочкой, не содержащей #).

Определение. Для данной МТ М положим Ai=r и (Qx Г) и {#}, а Да пусть будет множеством символов, входящих в хф, т. е. Ai- множество символов, которые могут появляться на верхней дорожке, а Аа - на нижней. "Двухдорожечным" алфавитом будет AiXAj. Правильным вычислением машины М с измерителем ЦИКЛ(л:#) называют цепочку из множества (д1ха2)*, имеющую вид, как на рис. 11.1, где Сг[-Cj+i за один шаг машины М для 0<i<f, Со- начальное МО и состоянием последнего МО С является q. В МО дописаны пустые символы, чтобы все МО имели длину \х



Лемма 11.4. Пусть Ri - расширенное регулярное выражение для множества ЦИКЛ(л:#) и R\ - регулярное выражение над алфавитом цепочки хф, представляющее все цепочки, кроме х. Можно построить такое расширенное регулярное выражение R2, представляющее все неправильные вычисления машины М с измерителем ЦИКЛ(л:#), что его длина будет линейной по \Ri\-\R{\, причем коэффициент пропорциональности будет зависеть только от М, и оно будет содержать знак дополнения только тогда, когда его содержит Ri или R[.

Доказательство. Цепочка не является правильным вычислением с измерителем ЦИКЛ (хф) тогда и только тогда, когда либо

1) нижняя дорожка не содержится в либо

2) нижняя дорожка содержится в но верхняя дорожка не является правильным вычислением.

Если Ai и А 2 - алфавиты верхней и нижней дорожек соответственно, то обозначим через hi и йа гомоморфизмы, отображающие (AiXAa)* в AJ и А2 соответственно, так что hi{la, b])=a и hi{[a, b])=b. Тогда

fta- [Аа* # (R[ n (Aa-#)*) # Да*+ (Aa-#) A3 + AJ (Aa-#)] +e

представляет те и только те цепочки, у которых нижняя дорожка не принадлежит Первое слагаемое аргумента в ft" представ-

ляет цепочки, у которых между двумя знаками # стоит нечто, отличное от х, а остальные представляют цепочки, которые не начинаются или не кончаются символом #. По лемме 11.3 найдется расширенное регулярное выражение с длиной, пропорциональной \R[\, представляющее это множество.

Данная цепочка удовлетворяет условию 2, когда два символа, отделенные друг от друга символами в количестве, равном длине измерителя, не соответствуют шагу машины М либо когда происходит одно или более из следующих нарушений структуры:

1) цепочка на верхней дорожке не начинается или не кончается символом #,

2) в первом МО или совсем нет состояния, или есть два или более состояний,

3) в первом МО начальное состояние не является компонентой первого символа,

4) допускающее состояние не появляется в качестве компоненты никакого символа,

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