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

Лемма ПЛ. Для каждого существует измеритель с длиной, большей 2*, который можно представить таким полу расширенным регулярным выражением R, что \R\ck для некоторой постоянной с, не зависящей от k.

Доказательство. Пусть Л = {ао, а.\,- • - алфавит

из k+\ различных символов. Положим Xo=a(flo п Xi=Xi-iaiXi-iai для l<t<fe. Тогда

х, = (...((а?а,Га,)..а,)

Длина цепочки Xf, равна 2, а длина цепочки Х/ больше удвоенной длины цепочки xi-i. Поэтому длина цепочки Xu-i не меньше 2* для

ЦИКЛ(Х; ]а - искомый измеритель. Осталось показать, что некоторое короткое полурасширенное регулярное выражение представляет множество 1ЩК.Л{х 1а).

Для 0<t<fe пусть Ai={ao+ai+. . .+aj) и A-Ai={ai+i+ai+2+ + . . .+а). Положим

R, = a„fl„ [(А - Ло)+ all* (Л - Л „)+ + а,[(А~А,Га1]*{А-АУа, + [(Л-Ло)+а?]*(Л-Ло)+а„а„(Л-Л„)»

Ri = AUaiAUai[{A-Aiy (Ла,)](Л-AU +atAUai[iA-Aiy (Л/.а,)»]* (Л-Л,.)+ AU + АиаМА-АУ {AUain{A-A,r AUaAU + ai [(Л - Л,)+ (АиаГУ (Л - Л,)+ AUaAU + [(Л-Л,)+ (Alia.rr (A-Ai)*Ar.iaiAliaAA-Ai)*

для l<t<fe-1.

Мы утверждаем, что полурасширенное регулярное выражение

= /?о П /?1 Л ... П Rk-i П AUokAUi

представляет Uy[KJl(x ia,). Для доказательства покажем индукцией по i, что любая цепочка из множества, представленного выражением Rof]Rif\- -ORi, имеет вид

уЛ(Л-Л,)+Х,]И-Л,)Уг

+ [(Л - Л,.)+ xi]* (Л - Л,)+ xi (Л - Л,).,

где У1У2=Х1.

Базис индукции. Для t=0 видно, что Ro представляет в точности цепочки вида

ai[(A-A,yal]4A-A,yal-i +[{А-А,)*а1\ЧА-А,Уа,а„{А-Ао)*

для некоторого 0</2. Поскольку х=а1, утверждение верно. 458



= г/;а,х, ,а,.[(Л-Л,.)+х,. + ал 1а,.[(Л-Л,.)+х,. + /аа,[(Л-Л,.)+х,:

{а-агу:

*(Л-Л,.)х, 1 *(A-A;yxi.iaiy[ + а,.[(Л-Л,)+ л;,.]* И-Л,)+ J:,-A-v, i

+ [{A-Airxi]*{A-Airxi.iaiXi.iai{A-Ai)\ (П.2)

Наконец, (11.2) можно переписать в виде

yA{A-Ai)Xi]*(A-Ai)-yi

+ [(Л-Л,) +х,]*(-Л,) Ч(-,)*.

где У1Уг=Х1. Отсюда вытекает утверждение индукции. Полагая [=• =k-\ и пересекая с Ak-ia,Al i, заключаем, что R представляет ЦИКЛ(х,.,а,).

Осталось показать, что длина расширенного регулярного выражения R не превосходит ck. Это непосредственно следует из существования такой постоянной Си что длина каждого регулярного выражения Rt не превосходит Cik. Иными словами, At и A-Aj обозначают расширенные регулярные выражения длины О (к), и потому каждое слагаемое суммы, определяющей Ri, обозначает расширенное регулярное выражение длины 0{k). Следовательно, длина полурасширенного регулярного выражения R ограничена сверху числом ck для некоторой новой постоянной с. □

Конструкция, аналогичная конструкции из леммы 11.1, позволяет написать короткое регулярное выражение, представляющее множество всех цепочек из А*, кроме x=Xi-i. Это регулярное выражение понадобится нам вместе с полурасширенным регулярным

Шаг индукции. Предположим, что /?о П -Ri П • • . П представляет все цепочки вида

(11-1)

где у\уг=Х1.г.

Рассмотрим цепочку z из пересечения множества цепочек (П.1) и множества, представленного выражением Каждая подцепочка цепочки 2, принадлежащая Af i и имеющая максимальную длину, должна совпадать с х,-.,, кроме тех случаев, когда она является началом или концом этой цепочки (тогда она равна у.,, или у[). Поэтому каждое вхождение Л/!, в Ri можно заменить на Xt-i (если только оно не в начале и не в конце этого регулярного выражения), не изменяя пересечения множеств (ИЛ) viRi. Вхождения Л/!, и/4j* i в начале и конце выражения Ri можно заменить на у, и у\ соответственно. Замечая, что Xi-iaiXi-iai=Xi, получаем

/?„П/?1П ... П/?/ =



) Через А - а/ обозначена сумма 5] о/.

выражением R, только что построенным для представления множества ЦИКЛ(а;#).

Лемма 11.2. Пусть алфавит А = {ао, a,. . ., а} и цепочки Xt те же, чпю и в лемме 11.1. Тогда найдется регулярное выражение длины 0(k), представляющее "гх-х.

Доказательство. Цепочка х обладает такими свойствами:

(1) она непуста и начинается с Оо (символы а» входят в нее парами и за каждым вхождением такой пары идет а),

(2) для 1/Л-2 символы Oj также входят парами (в каждой паре два символа отделены друг от друга цепочкой из аоЛ; 1 и за вторым Ui этой пары идет aj+i, т. е. за символом а слева от которого стоят исключительно символы из или непосредственно слева от которого стоит цепочка из Л имеющая перед собой символ из А-Ai, идет символ Оо),

(3) символ а 1 входит в точности два раза (за первым вхождением идет Оо, а второе является самым правым символом).

Еще важнее то, что х - единственная цепочка, обладающая этими свойствами. Можно доказать индукцией по /, что если Ьфг- . . .. - префикс цепочки, обладающей этими свойствами, то Ьф. .. .. .bj - префикс цепочки х.. Например, в силу (1) первым символом является flo. Также в силу (1) изолированный символ Оо не может быть последним в этой цепочке и за ним может идти только Оо, следовательно, цепочка начинается с йоДо. Далее, опять по свойству (1) за aoUo должен идти символ Oi. В силу свойства (2) при i=l за цепочкой aoaofli должен идти символ Оо и т. д. Формальную индукцию оставляем в качестве упражнения. Поскольку х. на самом деле обладает этими свойствами, эта цепочка и есть единственная, обладающая ими.

Легко написать регулярное выражение, представляющее все цепочки, не обладающие хотя бы одним из этих свойств. Цепочки, не обладающие свойством (1), представляются выражением)

S, = е + (Л -а„) А* + Л*а„а„ [(Л-а,) А* + г] + + [е + Л* (Л-а,)] а, [(А -а„) Л* + е].

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





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