dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 30
Текст из файла (страница 30)
Если бы он выполнялся, то можно было бы подставить регулярноевыражение 0 вместо L и 1 вместо M и получить неверное заключение 01 = 10. 3.4.2. Åäèíè÷íûå è íóëåâûå ýëåìåíòûЕдиничным (нейтральным) элементом (единицей) операции называется элемент, длякоторого верно следующее утверждение: если данная операция применяется к единичному элементу и некоторому другому элементу, то результат равен другому элементу.Например, 0 является единичным элементом операции сложения, поскольку 0 + x =x + 0 = x, а 1 — единичным элементом для умножения, потому что 1 × x = x × 1 = x. Нулевым элементом (нулем, аннулятором) операции называется элемент, для которого истинно следующее: результатом применения данной операции к нулевому и любому другому элементу является нулевой элемент.
Например, 0 является нулевым элементом умножения, поскольку 0 × x = x × 0 = 0. Операция сложения нулевого элемента не имеет.Для регулярных выражений существует три закона, связанных с этими понятиями.• ∅ + L = L + ∅ = L. Этот закон утверждает, что ∅ является единицей объединения.• εL = Lε = L. Этот закон гласит, что ε является единицей конкатенации.• ∅L = L∅ = ∅.
Этот закон утверждает, что ∅ является нулевым элементом конкатенации.Эти законы являются мощным средством упрощения выражений. Например, если необходимо объединить несколько выражений, часть которых упрощена до ∅, то ∅ можноисключить из объединения. Аналогично, если при конкатенации нескольких выраженийнекоторые из них можно упростить до ε, то ε можно исключить из конкатенации. Наконец, если при конкатенации любого количества выражений хотя бы одно из них равно ∅,то результат такой конкатенации — ∅.3.4.3.
Äèñòðèáóòèâíûå çàêîíûДистрибутивный закон связывает две операции и утверждает, что одну из операцийможно применить отдельно к каждому аргументу другой операции. Арифметическимпримером этого закона является дистрибутивный закон умножения относительно сложения, т.е. x × (y + z) = x × y + x × z. Поскольку умножение коммутативно, то не имеет значения, с какой стороны, слева или справа от суммы, применяется умножение.
Для регулярных выражений существует аналогичный закон, но, поскольку операция конкатенации некоммутативна, то мы сформулируем его в виде следующих двух законов.134Стр. 134ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈ• L(M + N) = LM + LN. Этот закон называется левосторонним дистрибутивным законом конкатенации относительно объединения.• (M + N)L = ML + NL.
Этот закон называется правосторонним дистрибутивнымзаконом конкатенации относительно объединения.Докажем левосторонний дистрибутивный закон. Правосторонний доказывается аналогично. В доказательстве используются только языки, и оно не зависит от того, существуют ли для этих языков регулярные выражения.Теорема 3.11. Если L, M и N — произвольные языки, тоL(M U N) = LM U LNДоказательство. Это доказательство аналогично доказательству дистрибутивногозакона, представленного в теореме 1.10.
Требуется показать, что цепочка w принадлежитL(M U N) тогда и только тогда, когда она принадлежит LM U LN.(Необходимость) Если w принадлежит L(M U N), то w = xy, где x принадлежит L, а yпринадлежит либо M, либо N. Если y принадлежит M, то xy принадлежит LM и, следовательно, принадлежит LM U LN. Аналогично, если y принадлежит N, то xy принадлежитLN и, следовательно, принадлежит LM U LN.(Достаточность) Предположим, что w принадлежит LM U LN. Тогда w принадлежитлибо LM, либо LN. Пусть w принадлежит LM. Тогда w = xy, где x принадлежит L, а y принадлежит M.
Если y принадлежит M, то y также содержится в M U N. Следовательно, xyпринадлежит L(M U N). Если w не принадлежит LM, то она точно содержится в LN, ианалогичные рассуждения показывают, что w принадлежит L(M U N). Пример 3.12. Рассмотрим регулярное выражение 0 + 01*. В объединении можно“вынести за скобки 0”, но сначала необходимо представить выражение 0 в виде конкатенации 0 с чем-то еще, а именно с ε. Используем свойства единичного элемента для конкатенации, меняя 0 на 0ε, в результате чего получим выражение 0ε + 01*. Теперь можноприменить левосторонний дистрибутивный закон, чтобы заменить это выражение на0(ε + 1*).
Далее, учитывая, что ε принадлежит L(1*), заметим, что ε + 1* = 1*, и окончательно упростим выражение до 01*. 3.4.4. Çàêîí èäåìïîòåíòíîñòèОперация называется идемпотентной, если результат применения этой операции кдвум одинаковым значениям как операндам равен этому значению. Обычные арифметические операции не являются идемпотентными. В общем случае x + x ≠ x и x × x ≠ x (хотясуществуют некоторые значения x, для которых это равенство выполняется, например0 + 0 = 0).
Однако объединение и пересечение являются идемпотентными операциями,поэтому для регулярных выражений справедлив следующий закон.3.4. ÀËÃÅÁÐÀÈ×ÅÑÊÈÅ ÇÀÊÎÍÛ ÄËß ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉСтр. 135135• L + L = L. Этот закон — закон идемпотентности операции объединения — утверждает, что объединение двух одинаковых выражений можно заменить однимтаким выражением.3.4.5. Çàêîíû, ñâÿçàííûå ñ îïåðàòîðîì èòåðàöèèСуществует ряд законов, связанных с операцией итерации и ее разновидностями + и ?в стиле UNIX. Перечислим эти законы и вкратце поясним, почему они справедливы.• (L*)* = L*.
Этот закон утверждает, что при повторной итерации язык уже итерированного выражения не меняется. Язык выражения (L*)* содержит все цепочки,образованные конкатенацией цепочек языка L*. Последние же цепочки построены из цепочек языка L. Таким образом, цепочки языка (L*)* также являются конкатенациями цепочек из L и, следовательно, принадлежат языку L*.• ∅* = ε. Итерация языка ∅ состоит из одной-единственной цепочки ε, что уже обсуждалось в примере 3.6.• ε* = ε.
Легко проверить, что единственной цепочкой, которую можно образоватьконкатенацией любого количества пустых цепочек, будет все та же пустая цепочка.• L+ = LL* = L*L. Напомним, что L+ по определению равно L + LL + LLL + …. Поскольку L* = ε + L + LL + LLL + …, тоLL* = Lε + LL + LLL + LLLL + …Если учесть, что Lε = L, то очевидно, что бесконечные разложения для LL* и дляL+ совпадают.
Это доказывает, что L+ = LL*. Доказательство того, что L+ = L*L,аналогично5.• L* = L+ + ε. Это легко доказать, поскольку в разложении L+ присутствуют те жечлены, что и в разложении L*, за исключением цепочки ε. Заметим, что если языкL содержит цепочку ε, то слагаемое “+ε” лишнее, т.е. в этом случае L+ = L*.• L? = ε + L. В действительности это правило является определением оператора “?”.3.4.6. Óñòàíîâëåíèå çàêîíîâ äëÿ ðåãóëÿðíûõ âûðàæåíèéКаждый из вышеперечисленных законов был доказан, формально или неформально.Однако есть еще бесконечно много законов для регулярных выражений, которые можнобыло бы сформулировать. Существует ли некая общая методика, с помощью которойможно было бы легко доказывать истинность таких законов? Оказывается, что вопрос осправедливости некоторого закона сводится к вопросу о равенстве двух определенных5Как следствие, отметим, что любой язык коммутирует со своей итерацией: LL* = L*L.
Это свойство не противоречит тому, что в общем случае конкатенация не является коммутативной.136Стр. 136ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈязыков. Интересно, что эта методика тесно связана с регулярными операциями и не может быть распространена на выражения, использующие некоторые другие операции, например пересечение.Чтобы проиллюстрировать суть этой методики, рассмотрим следующий закон.(L + M)* = (L*M*)*Этот закон утверждает, что в результате итерации объединения двух произвольных языков получим тот же язык, что и в результате итерации языка L*M*, состоящего из всехцепочек, образованных из нуля или нескольких цепочек из L, за которыми следует нульили несколько цепочек из M.Чтобы доказать этот закон, сначала предположим, что цепочка w принадлежит языкувыражения (L + M)*6.
Тогда w = w1w2...wk для некоторого k, где каждая цепочка wi принадлежит либо L, либо M. Из этого следует, что каждая такая цепочка wi принадлежитязыку L*M*. Действительно, если цепочка wi принадлежит языку L, то она также принадлежит языку L*. Тогда из M не берем ни одной цепочки, т.е. из M* выбираем ε. Если wiпринадлежит M, доказательство аналогично. Если каждая wi принадлежит L*M*, то wпринадлежит итерации этого языка.Чтобы завершить доказательство, необходимо доказать обратное утверждение, т.е.что все цепочки из (L*M*)* принадлежат также (L + M)*. Опустим эту часть доказательства, поскольку нашей целью является не доказательство данного закона, а установлениеследующего важнейшего свойства регулярных выражений.Любое регулярное выражение с переменными можно рассматривать как конкретное регулярное выражение, не содержащее переменных, если считать, что каждая переменная — этопросто отдельный символ.
Например, в выражении (L + M)* переменные L и M можно заменить символами a и b, соответственно, и получить регулярное выражение (a + b)*.Язык конкретного выражения дает представление о виде цепочек любого языка, образованного из исходного выражения в результате подстановки произвольных языковвместо переменных. Например, при анализе выражения (L + M)* мы отметили, что любаяцепочка w, составленная из последовательности цепочек, выбираемых либо из L, либо изM, принадлежит языку (L + M)*. Можно прийти к тому же заключению, рассмотрев языкконкретного выражения L((a + b)*), который, очевидно, представляет собой множествовсех цепочек, состоящих из символов a и b. В одну из цепочек этого множества можноподставить любую цепочку из L вместо символа a и любую цепочку из M вместо символаb.
При этом различные вхождения символов a и b можно заменять различными цепочками. Если такую подстановку осуществить для всех цепочек из (a + b)*, то в результатеполучим множество всех цепочек, образованных конкатенацией цепочек из L и/или M влюбом порядке.6Для простоты отождествим регулярные выражения с их языками, чтобы не повторять фразу“язык выражения” перед каждым регулярным выражением.3.4. ÀËÃÅÁÐÀÈ×ÅÑÊÈÅ ÇÀÊÎÍÛ ÄËß ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉСтр. 137137Сформулированное выше утверждение может показаться очевидным, но, как указаново врезке “Расширение данной проверки за пределы регулярных выражений может оказаться ошибочным”, оно будет неверным, если к трем операциям регулярных выраженийдобавить некоторые другие операции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
