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

Рассмотрим подобный пример в алгебре обычной арифметики. Одно дело сказать, что 1+2 = 2+1. Данный частный случай закона коммутативности операции сложения легко проверить: выполнив операцию сложения в обеих частях этого равенства, получим 3 = 3. Однако коммутативный закон сложения утверждает большее, а именно, что х+у = у + х, где х и у — переменные, которые можно заменять любыми двумя числами. Сле­довательно, он гласит, что, какие бы числа мы ни складывали, получим один и тот же ре­зультат независимо от порядка суммирования.

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

3.4.1. Ассоциативность и коммутативность

Коммутативность— это свойство операции, заключающееся в том, что при пере­становке ее операндов результат не меняется. Арифметический пример мы уже приводи­ли выше: х + у = у + х. Ассоциативность— это свойство операции, позволяющее пере­группировывать операнды, если оператор применяется дважды. Например, ассоциатив­ный закон умножения имеет вид: (xxy)xz = xx(yxz). Для регулярных выражений выполняются три закона такого типа.

L + М= M+L, т. е. коммутативный закон для объединения утверждает, что два языка можно объединять в любом порядке. (L + М) + N = L + (М + N). Этот закон— ассоциативный закон объединения — говорит, что для объединения трех языков можно сначала объединить как два первых, так и два последних из них. Обратите внимание на то, что вместе с ком­мутативным законом объединения этот закон позволяет объединять любое коли­чество языков в произвольном порядке, разбивая их на любые группы, и резуль­тат будет одним и тем же. Очевидно, что некоторая цепочка принадлежит объе­динению L\ U L2 U... U Lk тогда и только тогда, когда она принадлежит одному или нескольким языкам Lv (LM)N - L(MN). Этот ассоциативный закон конкатенации гласит, что для конка­тенации трех языков можно сначала соединить как два первых, так и два послед­них из них.

В предложенном списке нет "закона" LM=ML, гласящего, что операция конкатена­ции является коммутативной, поскольку это утверждение неверно.

Пример 3.10. Рассмотрим регулярные выражения 01 и 10. Эти выражения задают языки {01} и {10}, соответственно. Поскольку эти языки различаются, то общий закон LM=ML для них не выполняется. Если бы он выполнялся, то можно было бы подставить регулярное выражение 0 вместо L и 1 вместо Ми получить неверное заключение 01 = 10. □

Единичные и нулевые элементы

Единичным (нейтральным) элементом (единицей) операции называется элемент, для которого верно следующее утверждение: если данная операция применяется к единич­ному элементу и некоторому другому элементу, то результат равен другому элементу. Например, 0 является единичным элементом операции сложения, поскольку 0 + х = л: + 0 = х, а 1 — единичным элементом для умножения, потому что 1 х х = х х 1 = х. Нуле­вым элементом (нулем, аннулятором) операции называется элемент, для которого ис­тинно следующее: результатом применения данной операции к нулевому и любому дру­гому элементу является нулевой элемент. Например, 0 является нулевым элементом ум­ножения, поскольку 0хх = хх0 = 0. Операция сложения нулевого элемента не имеет.

Для регулярных выражений существует три закона, связанных с этими понятиями.

0 + L = L + 0 = L. Этот закон утверждает, что 0 является единицей объединения. eL = Le = L. Этот закон гласит, что е является единицей конкатенации. 0L = L0 = 0. Этот закон утверждает, что 0 является нулевым элементом конка­тенации.

Эти законы являются мощным средством упрощения выражений. Например, если не­обходимо объединить несколько выражений, часть которых упрощена до 0, то 0 можно исключить из объединения. Аналогично, если при конкатенации нескольких выражений некоторые из них можно упростить до е, то е можно исключить из конкатенации. Нако­нец, если при конкатенации любого количества выражений хотя бы одно из них равно 0, то результат такой конкатенации — 0.

Дистрибутивные законы

Дистрибутивный закон связывает две операции и утверждает, что одну из операций можно применить отдельно к каждому аргументу другой операции. Арифметическим примером этого закона является дистрибутивный закон умножения относительно сложе­ния, т. е. xx(y + z) = xxy+x~xz. Поскольку умножение коммутативно, то не имеет зна­чения, с какой стороны, слева или справа от суммы, применяется умножение. Для регу­лярных выражений существует аналогичный закон, но, поскольку операция конкатена­ции некоммутативна, то мы сформулируем его в виде следующих двух законов.

L(M + N) = LM + LN. Этот закон называется левосторонним дистрибутивным за­коном конкатенации относительно объединения. (М + N)L = ML + NL. Этот закон называется правосторонним дистрибутивным законом конкатенации относительно объединения.

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

Теорема 3.11. Если L, MnN— произвольные языки, то

L(M(J N) = LM\J LN

Доказательство. Это доказательство аналогично доказательству дистрибутивного закона, представленного в теореме 1.10. Требуется показать, что цепочка w принадлежит ДА/U N) тогда и только тогда, когда она принадлежит LM U LN.

(Необходимость) Если w принадлежит L(M U N), то w = xy, где х принадлежит L, а у принадлежит либо М, либо N. Если у принадлежит М, то ху принадлежит LM и, следова­тельно, принадлежит LM\JLN. Аналогично, если у принадлежит N, то ху принадлежит LN и, следовательно, принадлежит LM U LN.

(Достаточность) Предположим, что w принадлежит LM (J LN. Тогда w принадлежит либо LM, либо LN. Пусть и> принадлежит LM. Тогда и> = ху, где х принадлежит L, ay при­надлежит М. Если у принадлежит М, то у также содержится в A/U N. Следовательно, ху принадлежит L(M\JN). Если w не принадлежит LM, то она точно содержится в LN, и аналогичные рассуждения показывают, что w принадлежит L(M[j N). □

Пример 3.12. Рассмотрим регулярное выражение 0 + 01 . В объединении можно "вынести за скобки 0", но сначала необходимо представить выражение 0 в виде конкате­нации 0 с чем-то еще, а именно с е. Используем свойства единичного элемента для кон­катенации, меняя 0 на Ое, в результате чего получим выражение 0е + 01*. Теперь можно применить левосторонний дистрибутивный закон, чтобы заменить это выражение на 0(е+ 1*). Далее, учитывая, что е принадлежит L(l'), заметим, что е+ 1* = 1*, и оконча­тельно упростим выражение до 01*. □

3.4.4. Закон идемпотентности

Операция называется идемпотентной, если результат применения этой операции к двум одинаковым значениям как операндам равен этому значению. Обычные арифмети­ческие операции не являются идемпотентными. В общем случаех+х*хяхх. х*х (хотя существуют некоторые значения х, для которых это равенство выполняется, например 0 + 0 = 0). Однако объединение и пересечение являются идемпотентными операциями, поэтому для регулярных выражений справедлив следующий закон.

L+ L = L. Этот закон — закон идемпотентности операции объединения — ут­верждает, что объединение двух одинаковых выражений можно заменить одним таким выражением.

Законы, связанные с оператором итерации

Существует ряд законов, связанных с операцией итерации и ее разновидностями + и? в стиле UNIX. Перечислим эти законы и вкратце поясним, почему они справедливы.

(L*)* = L*. Этот закон утверждает, что при повторной итерации язык уже итериро­ванного выражения не меняется. Язык выражения (Z,*)* содержит все цепочки, образованные конкатенацией цепочек языка L*. Последние же цепочки построе­ны из цепочек языка L. Таким образом, цепочки языка (X*)* также являются кон - катенациями цепочек из L и, следовательно, принадлежат языку L*. 0* = е. Итерация языка 0 состоит из одной-единственной цепочки е, что уже об­суждалось в примере 3.6. е* = е. Легко проверить, что единственной цепочкой, которую можно образовать конкатенацией любого количества пустых цепочек, будет все та же пустая цепочка. L+ = LL* = L*L. Напомним, что V по определению равно L+ LL + LLL + .... По­скольку L* = е + L + LL + LLL + ..., то

LL* = Le + LL + LLL + LLLL + ...

Если учесть, что Le = L, то очевидно, что бесконечные разложения для LL* и для V совпадают. Это доказывает, что V = LL'. Доказательство того, что L* = L*L, аналогично6.

L* = L+ + е. Это легко доказать, поскольку в разложении L+ присутствуют те же члены, что и в разложении Z,*, за исключением цепочки е. Заметим, что если язык L содержит цепочку е, то слагаемое "+е" лишнее, т. е. в этом случае V = V. Ll = е + L. В действительности это правило является определением оператора "?".

Установление законов для регулярных выражений

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