Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 30
Текст из файла (страница 30)
Ассоциативность — это свойство операции, позволяющее перегруппировывать операнды, если оператор применяется дважды. Например, ассоциативный закон умножения имеет вид: (х ху) хя = хх(ухе). Для регулярных выражений выполняются три закона такого типа. ° ь'+ М= М+ ь, т.е. коммутативный закон для объединения утверждает, что два языка можно объединять в любом порядке. ° (ь' ц М) + )у= ь'+ (М+ з). Этот закон — ассоциативный закон обьединения— говорит, что для объединения трех языков можно сначала объединить как два первых, так и два последних из них.
Обратите внимание на то, что вместе с коммутативным законом объединения этот закон позволяет объединять любое количество языков в произвольном порядке, разбивая их на любые группы, и результат будет одним и тем же. Очевидно, что некоторая цепочка принадлежит объединению ь1 0 ьз Ц ... Ц Ль тогда и только тогда, когда она принадлежит одному или нескольким языкам Аь ° (ьМ)Ф = ь(Мц), Этот ассоциативный закон конкатенации гласит, что для конкатенации трех языков можно сначала соединить как два первых, так и два последних из них. 3.4. АЛГЕБРАИЧЕСКИЕ ЗАКОНЫ ДЛЯ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙ 133 В предложенном списке нет "закона" 1,М= МЕ, гласящего, что операция конкатенации является коммутативной, поскольку это утверждение неверно. Пример 3.10.
Рассмотрим регулярные выражения 01 и 10. Эти выражения задают языки !01) и ! ! 0), соответственно. Поскольку эти языки различаются, то общий закон ЬМ = МЕ для них не выполняется, Если бы он выполнялся, то можно было бы подставить регулярное выражение 0 вместо 1. и 1 вместо М и получить неверное заключение 01 = 10. 1:) 3.4.2. Единичные и нулевые элементы Единичным (нейтральным) элементом (единиией) операции называется элемент, для которого верно следующее утверждение: если данная операция применяется к единич- ному элементу и некоторому другому элементу, то результат равен другому элементу.
Например, О является единичным элементом операции сложения, поскольку О+х= х+ О = х, а 1 — единичным элементом для умножения, потому что ! х х = т х ! = х. Нулевым элементом (кулем, аннулятором) операции называется элемент, для которого истинно следующее: результатом применения данной операции к нулевому и любому другому элементу является нулевой элемент. Например, О является нулевым элементом умножения, поскольку О х х = х х О = О.
Операция сложения нулевого элемента не имеет. Для регулярных выражений существует три закона, связанных с этими понятиями. ° И + Ь = 1, + И = Е. Этот закон утверждает, что И является единицей объединения. ь еь = 1,е = Е. Этот закон гласит, что е является единицей конкатенации. ° И1, = ЕИ = И.
Этот закон утверждает, что И является нулевым элементом конкатенации, Эти законы являются мощным средством упрощения выражсний. Например, если необходимо объединить несколько выражений, часть которых упрощена до И, то И можно исключить из объединения. Аналогично, если при конкатенации нескольких выражений некоторые из них можно ущэостить до Е то е можно исключить из конкатенации. Наконец, если при конкатенации любого количества выражений хотя бы одно из них равно И, то результат такой конкатенации — И. 3.4.3. Дистрибутивные законы Дистрибуиивный закон связывает две операции и утверждает, что одну из операций можно применить отдельно к каждому аргументу другой операции.
Арифметическим примером этого закона является дистрибутивный закон умножения относительно сложения, т е. х х (у+ х) = х ху + х х х. Поскольку умножение коммутативно, то не имеет значения, с какой стороны, слева или справа от суммы, применяется умножение. Для регулярных выражений существует аналогичный закон, но, поскольку операция конкатенации некоммутативна, то мы сформулируем его в виде следующих двух законов. ГЛАВА 3, РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 134 ° ЦМ+ )т) = ЕМ+ ЕАГ. Этот закон называется левосторонним дистрибутивным законом конкатенации атноситазъно объединения. ° (Мч-Аг)Е = МЕ+)тЕ. Этот закон называется правосторанним дистрибутивным законом конкатенации относительно объединения.
Докажем левосторонний дистрибутивный закон. Правосторонннй доказывается аналогично. В доказательстве используются только языки, н оно не зависит от того, сущест- вуют ли для этих языков регулярные выражения. Теорема 3.11. Если Е, М и У вЂ” произвольные языки, то ЕЕМ0Ф) = ЕМ!) ЕА' Доказательство. Это доказательство аналогично доказательству дистрибутивного закона, представленного в теореме 1.10. Требуется показать, что цепочка и принадлежит ЦМ1) Ф) тогда и только тогда, когда она принадлежит ЕМО ЕФ. (гЕеобходимасть) Если и принадлежит ЦМ0Ю), то и =ху, где х принадлежит Е, ау принадлежит либо М, либо У. Если у принадлежит М, то ху принадлежит ЕМ н, следовательно, принадлежит ЕМЦ ЕУ. Аналогично, если у принадлежит Ф, то ху принадлежит ЕлГ и, следовательно, принадлежит ЕМ 1) ЕУ.
1ЕЕостаточность) Предположим, что эс принадлежит ЕМ 1) ЕФ. Тогда в принадлежит либо ЕМ, либо ЕУ. Пусть и принадлежит ЕМ. Тогда и = ху, где х принадлежит Е, а у принадлежит М. Если у принадлежиг М, то у также содержится в МО Ф. Следовательно, ху принадлежит ЦМ0 Ф). Если и не принадлежит ЕМ, то она точно содержится в ЕФ, и аналогичные рассуждения показывают, что и принадлежит ЦМ 1) Щ П Пример 3.12. Рассмотрим регулярное выражение 0+ 01. В объединении можно "вынести за скобки 0", но сначала необходимо представить выражение 0 в виде конкатенации 0 с чем-то еще, а именно с е.
Используем свойства единичного элемента для конкатенации, меняя 0 на Ое, в результате чего получим выражение Ое+ 01 . Теперь можно применить левосторонний дистрибутивный закон, чтобы заменить это выражение на 0(е+ 1 ). Далее, учитывая, что е принадлежит Е(1 ), заметим, что е+ 1 = 1, и окончательно упростим выражение до 01 . П 3.4.4. Закон идеяяпотентности Операция называется идемпотентной если результат применения этой операции к двум одинаковым значениям как операндам равен этому значению. Обычные арифметические операции не являются идемпотентными. В общем случае х + х в х и х х х в х (хотя существуют некоторые значения х, для которых это равенство выполняется, например О+ 0 = О).
Однако объединение и пересечение являются идемпотентными операциями, поэтому для регулярных выражений справедлив следующий закон. 3.4. АЛГЕБРАИЧЕСКИЕ ЗАКОНЫ ДЛЯ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙ 135 ° ?. +?. =?.. Этот закон — закон идемпотеитиости операции объединения — утверждает, что объединение двух одинаковых выражений можно заменить одним таким выражением. 3.4.5. Законы, связанные с оператором итерации Существует ряд законов, связанных с операцией итерации и ее разновидностями + и? в стиле ()гч1Х. Перечислим эти законы и вкратце поясним, почему они справедливы.
° (Т. ) =?.. Этот закон утверждает, что при повторной итерации язык уже итерированного выражения не меняется. Язык выражения (?. ) содержит все цепочки, образованные конкатенацией цепочек языка 1. Последние же цепочки построены из цепочек языка1. Таким образом, цепочки языка(1 ) также являются конкатенациями цепочек из?, и, следовательно, принадлежат языку 1 .
° О = е. Итерация языка И состоит из одной-единственной цепочки е, что уже обсуждалось в примере 3.6. ° е =е. Легко проверить, что единственной цепочкой, которую можно образовать конкатенацией любого количества пустых цепочек, будет все та же пустая цепочка. ° 1 = 11, =?,?.. Напомним, что?. по определению равно 1+?? +??Т. + .... Поскольку ?,* = еч-?. + 1?. + 11?.
+ ..., то Т.Т. = 1е+ Ы +?,1?. + й??.? + .. Если учесть, что 1е =?„то очевидно, что бесконечные разложения для?.Т, и для 1 совпадают. Это доказывает, что?. =??.. Доказательство того, что?, =Т,?., аналогично . 5 ° Т, =?. + ж Это легко доказать, поскольку в разложении?.+ присутствуют те же члены, что и в разложении 1, за исключением цепочки ж Заметим, что если язык 1 содержит цепочку е, то слагаемое "+е" лишнее, т.е.
в этом случае?. = 1 . ° ь? = е ч?.. В действительности это правило является определением оператора '"?". 3.4.6. Установление законов для реп~лярных выражений Каждый из вышеперечисленных законов был доказан, формально или неформально. Однако есть еще бесконечно много законов для регулярных выражений, которые можно было бы сформулировать. Существует ли некая общая методика, с помощью которой можно было бы легко доказывать истинность таких законов? Оказывается, что вопрос о справедливости некоторого закона сводится к вопросу о равенстве двух определенных языков.
Интересно, что эта методика тесно связана с регулярными операциями и не мо- Как следствие, отметим, что любой язык коммугируег со своей итерацией: 11* = й й Это свойство нс противоречит тому, что в общем случае конкатенация не являегсв коммутвтивной. ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ жет быть распространена на выражения, использующие некоторые другие операции, на- пример пересечение. Чтобы проиллюстрировать суть этой методики, рассмотрим следующий закон. (Ь + М) = (Ь*М ) Этот закон утверждает, что в результате итерации объединения двух произвольных языков получим тот же язык, что и в результате итерации языка Ь М, состоящего из всех цепочек, образованных из нуля или нескольких цепочек из Ь, за которыми следует нуль или несколько цепочек из М. Чтобы доказать этот закон, сначала предположим, что цепочка и принадлежит языку выражения (Ь е М) .
Тогда и = и,иь..иь для некоторого 1, где каждая цепочка и, при- 6 надлежит либо 7„либо М. Из этого следует, что каждая такая цепочка ж, принадлежит языку Ь М. Действительно, если цепочка зг, принадлежит языку Ь, то она также принадлежит языку Ь . Тогда из М не берем ни одной цепочки, т.е. из М выбираем ж Если и; принадлежит М, доказательство аналогично.
Если каждая и, принадлежит Ь М, то и принадлежит итерации этого языка. Чтобы завершить доказательство, необходимо доказать обратное утверждение, т.е. что все цепочки из (Ь М )* принадлежат также (Ь + М) . Опустим эту часть доказательства, поскольку нашей целью является не доказательство данного закона, а установление следуюшего важнейшего свойства регулярных выражений. Любое регулярное выражение с переменными можно рассматривать как конкретное регулярное выражение, не содержащее переменных, если считать, что каждая переменная — это просто отдельный символ. Например, в выражении (Ь + М)* переменные Ь и М можно заменить символами и и Ь, соответственно, и получить регулярное выражение (а + Ь) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
