Регулярные выражения и языки (стр. 9 )

Чтобы проиллюстрировать суть этой методики, рассмотрим следующий закон.

(L + М) = (См*)"

Этот закон утверждает, что в результате итерации объединения двух произвольных язы­ков получим тот же язык, что и в результате итерации языка L*Af', состоящего из всех цепочек, образованных из нуля или нескольких цепочек из L, за которыми следует нуль или несколько цепочек из М.

Чтобы доказать этот закон, сначала предположим, что цепочка w принадлежит языку выражения (L + M)*7. Тогда vv = vv1vv2...vvk для некоторого к, где каждая цепочка vv, при­надлежит либо L, либо М. Из этого следует, что каждая такая цепочка vv; принадлежит языку L*M*. Действительно, если цепочка vv, принадлежит языку L, то она также принад­лежит языку L. Тогда из М не берем ни одной цепочки, т. е. из М выбираем е. Если w* принадлежит м, доказательство аналогично. Если каждая >v, принадлежит L'a/, то w принадлежит итерации этого языка.

Чтобы завершить доказательство, необходимо доказать обратное утверждение, т. е. что все цепочки из (/,*Л/)* принадлежат также (L + М) . Опустим эту часть доказательст­ва, поскольку нашей целью является не доказательство данного закона, а установление следующего важнейшего свойства регулярных выражений.

Любое регулярное выражение с переменными можно рассматривать как конкретное регулярное выражение, не содержащее переменных, если считать, что каждая перемен­ная — это просто отдельный символ. Например, в выражении (L + М) переменные L и М можно заменить символами а и Ь, соответственно, и получить регулярное выражение (а + Ь)*.

Язык конкретного выражения дает представление о виде цепочек любого языка, об­разованного из исходного выражения в результате подстановки произвольных языков вместо переменных. Например, при анализе выражения (L + М) мы отметили, что любая цепочка w, составленная из последовательности цепочек, выбираемых либо из L, либо из М, принадлежит языку (L + М) . Можно прийти к тому же заключению, рассмотрев язык конкретного выражения L((а + Ь)*), который, очевидно, представляет собой множество всех цепочек, состоящих из символов а и Ь. В одну из цепочек этого множества можно подставить любую цепочку из L вместо символа а и любую цепочку из М вместо символа Ь. При этом различные вхождения символов а и b можно заменять различными цепочка­ми. Если такую подстановку осуществить для всех цепочек из (а + Ь)*, то в результате получим множество всех цепочек, образованных конкатенацией цепочек из L и/или М в любом порядке.

Сформулированное выше утверждение может показаться очевидным, но, как указано во врезке "Расширение данной проверки за пределы регулярных выражений может ока­заться ошибочным", оно будет неверным, если к трем операциям регулярных выражений добавить некоторые другие операции. В следующей теореме доказывается общий закон для регулярных выражений.

Теорема 3.13. Пусть Е— регулярное выражение с переменными Lx, Ь2, ..., Lm. По­строим конкретное регулярное выражение С, заменив каждое вхождение L, символом а„ i= 1, 2, ..., т. Тогда для произвольных языков Lu L2, ..., Lm любую цепочку w из L(E) можно представить в виде w = wxw2...wк, где каждая принадлежит одному из этих язы­ков, например а цепочка a|laJ2...a|k принадлежит языку ЦС). Говоря менее формально, мы можем построить ЦЕ), исходя из каждой цепочки языка ЦС), скажем, ajXasl...a^, и заменяя в ней каждый из символов asi любой цепочкой из соответствующего языка Ц.

Доказательство. Доказательство проведем структурной индукцией по выражению Е.

Базис. Базисными являются случаи, когда Е представляет собой е, 0 или переменную L. В первых двух случаях нечего доказывать, потому что конкретное выражение С сов­падает с Е. Если же Е есть переменная L, то ЦЕ) = L. Конкретное выражение С равно просто а, где а— символ, соответствующий переменной L. Следовательно, ЦС) = {а}. Если в эту единственную цепочку вместо символа а подставить любую цепочку из L, то получим язык L, который есть также ЦЕ).

Индукция. Рассмотрим три случая в зависимости от заключительной операции вы­ражения Е. Сначала предположим, что Е =F + G, т. е. заключительной является операция объединения. Пусть С и D — конкретные выражения, построенные соответственно по F и G с помощью подстановки в эти выражения определенных символов вместо языковых переменных. Заметим, что в оба выражения F и G вместо всех одинаковых переменных должны быть подставлены одинаковые символы. Тогда конкретное выражение, полу­ченное из выражения Е, равно С + D, и ЦС + D) = L(C) + L(D).

Предположим, что w — цепочка из языка ЦЕ), полученная в результате замены язы­ковых переменных выражения Е некоторыми определенными языками. Тогда w принад­лежит либо L(F), либо L(G). Согласно индуктивной гипотезе цепочка w получена, исходя из некоторой конкретной цепочки wx, принадлежащей ЦС) или L(D), соответственно, с помощью подстановки цепочек из соответствующих языков вместо символов цепочки W], Таким образом, в обоих случаях цепочка w может быть построена, начиная с некото­рой конкретной цепочки Wi из L(C + D), путем одних и тех же подстановок цепочек вме­сто символов.

Необходимо также рассмотреть случаи, когда Е представляет собой FG или F'. Одна­ко доказательства для конкатенации и итерации аналогичны приведенному выше доказа­тельству для объединения, поэтому оставляем их читателю. □

3.4.7. Проверка истинности алгебраических законов для регулярных выражений

Теперь можно сформулировать и обосновать проверку истинности законов для регу­лярных выражений. Проверка истинности закона Е = F, где Е и F— два регулярных вы­ражения с одним и тем же набором переменных, состоит в следующем.

Преобразуем Е и F в конкретные регулярные выражения С и D соответственно, за­меняя каждую переменную конкретным символом. Проверим равенство L(C) = L(D). Если оно выполняется, то закон Е = F истинен, а если нет — ложен. Заметим, что проверять, определяют ли два регулярных выражения один и тот же язык, мы научимся в разделе 4.4. Однако можно использовать некоторые спе­циальные (ad-hoc) средства для проверки равенства пар интересующих нас языков. На­помним, что если языки не совпадают, то достаточно построить контрпример, т. е. най­ти хотя бы одну цепочку, принадлежащую только одному из них.

Теорема 3.14. Предложенная выше проверка правильно определяет истинность зако­нов для регулярных выражений.

Доказательство. Докажем, что L(E) = L(F) для любых языков, подставленных вместо переменных Е иЕ, тогда и только тогда, когда L(C) = L(D).

(Необходимость) Предположим, что L(E) = L(F) для любых языков, подставляемых вместо переменных. В частности, выберем для каждой переменной L конкретный символ а, заменяющий L в выражениях С и D. Тогда L(C) = L(E) и L(D) = L(F). Поскольку мы предположили, что L(E) = L(F), то L(C) = L(D).

(Достаточность) Теперь предположим, что L(C) = L(D). Согласно теореме 3.13 Ь(Е) и L(F) построены с помощью замены конкретных символов в цепочках из L(C) и L(D) цепочками из языков, соответствующих этим символам. Если L(C) и L(D) состоят из од­них и тех же цепочек, то оба языка, построенные таким способом, тоже будут совпадать; т. е. L(E) = L(F). □

Пример 3.15. Проанализируем предполагаемый закон (L + М) = (Z*M*)*. Если заме­нить переменные L и М, соответственно, конкретными символами а и Ь, получим регу­лярные выражения (а + Ь)* и (а*Ь*)\ Легко убедиться в том, что оба эти выражения за­дают язык всех возможных цепочек, составленных из а и Ь. Следовательно, оба конкрет­ных выражения представляют один и тот же язык, и данный закон выполняется.

В качестве еще одного примера рассмотрим закон L* = L*J*. Конкретными языками будут а* и а*а*, соответственно, и каждый из них представляет собой множество всех це­почек, состоящих из а. Снова видим, что данный закон выполняется, т. е. конкатенация итераций одного и того же языка дает ту же самую итерацию.

Наконец, рассмотрим предполагаемый закон L + ML = (L + M)L. Если заменить сим­волами а и Ь переменные L и М, соответственно, то получим два конкретных выражения а + Ьа и (а + Ь)а. Однако языки этих выражений не совпадают. Например, цепочка аа

принадлежит второму языку, но не принадлежит первому. Следовательно, этот предпо­лагаемый закон ложен. □

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

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

Рассмотрим "закон" L П А/Г)N = Lf]M, утверждающий, что пересечение некоторых трех языков равно пересечению только двух первых из них. Очевидно, что этот закон ложен. Например, если L = М= {а}, а N = 0. Но проверка, основанная на конкретиза­ции переменных, может не определить ложность этого закона. Если мы заменим L, М и N символами a, b и с, соответственно, то должны будем проверить равенство {а} П {6} П {с} = {а} П {Ь}- Поскольку обе части этого соотношения являются пус­тым множеством, равенство языков выполняется, и согласно нашей проверке этот "закон" будет истинным, хотя в действительности это не так.

3.4.8. Упражнения к разделу 3.4

Проверьте следующие тождества для регулярных выражений:

а)        (*)R + S = S+R;

б)        (R + S) + Т= R + (S + Т);

в)        (RS)T= R(ST)~,

г)        R(S+ T) = RS + RT;

д)        (R + S)T= RT+ST-,

е)        (*)(Л*)* = Л*;

ж)        (е + R)* = R*;

з)        (R'sy = (R + S)\

(!) Докажите или опровергните каждое из следующих утверждений для регуляр­ных выражений:

а)        (*) (R + S)* = R* + Sf;

б)        (RS + R)'R = R(SR + /?)*;

в)        (*)(RS +R)*RS =(/Уг,5)*;