Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 31
Текст из файла (страница 31)
Язык конкретного выражения дает представление о виде цепочек любого языка, об- разованного из исходного выражения в результате подстановки произвольных языков вместо переменных, Например, при анализе выражения (Ь + М) мы отметили, что любая цепочка и, составленная из последовательности цепочек, выбираемых либо из 7„либо из М, принадлежит языку (Ь+ М) . Можно прийти к тому же заключению, рассмотрев язык конкретного выражения Ц(а+ Ь)*), который, очевидно, представляет собой множество всех цепочек, состояших из символов а и Ь.
В одну из цепочек этого множества можно подставить любую цепочку из Ь вместо символа а и любую цепочку из М вместо символа Ь. При этом различные вхождения символов а и Ь можно заменять различными цепочками. Если такую подстановку осушествить для всех цепочек из (а+ Ь)*, то в результате получим множество всех цепочек, образованных конкатенацией цепочек из Ь игили М в любом порядке. ' Для простаты отожлествим регулярные выражения с их языками, чтобы ие повторять фразу "язык выражения" перел каждым регулярным выражением. 3.4. АЛГЕБРАИЧЕСКИЕ ЗАКОНЫ ДЛЯ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙ 137 Сформулированное выше утверждение может показаться очевидным, но, как указано во врезке "Расширение данной проверки за пределы регулярных выражений может оказаться ошибочным", оно будет неверным, если к трем операциям регулярных выражений добавить некоторые другие операции. В следующей теореме доказывается общий закон для регулярных выражений. Теорема 3.13.
Пусть Š— регулярное выражение с переменными Еь Ем ..., Х . Построим конкретное регулярное выражение С, заменив каждое вхождение Е, символом и„ г= 1, 2, ..., и, Тогда для произвольных языков Еь Еъ ..., Е любую цепочку и из Е(Е) можно представить в виде и = и,и,... и ь где каждая и, принадлежит одному из этих языков, например Уя, а цепочка алая...ая принадлежит языку Х(С). Говоря менее формально, мы можем построить ЦЕ), исходя из каждой цепочки языка ЦС), скажем, слал...ал, и заменяя в ней каждый из символов аэ любой цепочкой из соответствующего языка Ея.
Доказательство. Доказательство проведем структурной индукцией по выражению Е. Базис. Базисными являются случаи, когда Е представляет собой я, О или переменную Е, В первых двух случаях нечего доказывать, потому что конкретное выражение С совпадает с Е. Если же Е есть переменная Ц то ЦЕ) = Е. Конкретное выражение С равно просто а, где а — символ, соответствующий переменной Е. Следовательно, ЦС) = (а). Если в эту единственную цепочку вместо символа а подставить любую цепочку из Е, то получим язык Е, который есть также ЦЕ).
Индукции. Рассмотрим три случая в зависимости от заключительной операции выражения Е. Сначала предположим, что Е =Е+ П, т.е. заключительной является операция объединения. Пусть С и Р— конкретные выражения, построенные соответственно по Е и С с помощью подстановки в эти выражения определенных символов вместо языковых переменных. Заметим, что в оба выражения Е и б вместо всех одинаковых переменных должны быть подставлены одинаковые символы. Тогда конкретное выражение, полученное из выражения Е, равно С+ Р, и ЦС э Р) = ЦС) + ЦР). Предположим, что и — цепочка из языка Е(Е), полученная в результате замены языковых переменных выражения Е некоторыми определенными языками.
Тогда и принадлежит либо ЦЕ), либо Цб). Согласно индуктивной гипотезе цепочка и получена, исходя из некоторой конкретной цепочки и ь принадлежащей ЦС) или ЦР), соответственно, с помощью подстановки цепочек из соответствующих языков вместо символов цепочки и ь Таким образом, в обоих случаях цепочка и может быть построена, начиная с некоторой конкретной цепочки ж, из ЦС+ Р), путем одних и тех же подстановок цепочек вме- сто символов. Необходимо также рассмотреть случаи, когда Е представляет собой ЕС или Е .
Одна- ко доказательства для конкатенации и итерации аналогичны приведенному выше доказа- тельству для объединения, поэтому оставляем их читателю. СЗ 138 ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 3.4.7. Проверка истинности алгебраических законов для регулярных выражений Теперь можно сформулировать и обосновать проверку истинности законов для регулярных выражений.
Проверка истинности закона Е = Р", где Е и Š— два регулярных выражения с одним и тем же набором переменных, состоит в следующем. 1. Преобразуем Е и Е в конкретные регулярные выражения С и Р соответственно, заменяя каждую переменную конкретным символом. 2. Проверим равенство ЦС) = ЦР). Если оно выполняется, то закон Е = Е истннен, а если нет — ложен. Заметим, что проверять, определяют ли два регулярных выражения один и тот же язык, мы научимся в разделе 4.4.
Однако можно использовать некоторые специальные (ап-Ьос) средства для проверки равенства пар интересующих нас языков. Напомним, что если языки не совпадают, то достаточно построить контрпример, т.е. найти хотя бы одну цепочку, принадлежащую только одному из ннх. Теорема 3.14. Предложенная выше проверка правильно определяет истинность законов для регулярных выражений. Доказательство. Докажем, что ЦЕ) = Е(Е) для любых языков, подставленных вместо переменных Е и Е, тогда и только тогда, когда ЦС) = Е(Р). (Необходимосгль) Предположим, что ЦЕ) = Е(Е) для любых языков, 'подставляемых вместо переменных. В частности, выберем для каждой переменной Е конкретный символ а, заменяющий Е в выражениях С и Р.
Тогда ЦС) = ЦЕ) и ЦР) = ЦЕ). Поскольку мы предположили, что ЦЕ) = ЦЬ), то ЦС) = Е(Р). (Е(остаточлость) Теперь предположим, что ЦС) = ЦР). Согласно теореме 3.13 Е(Е) и ЦЕ) построены с помощью замены конкретных символов в цепочках из ЦС) и ЦР) цепочками из языков, соответствующих этим символам. Если Е(С) и Е(Р) состоят из одних и тех же цепочек, то оба языка, построенные таким способом, тоже будут совпадать; т.е.
Е(Е) = ЦЕ). ЕЗ Пример ЗЛ5. Проанализируем предполагаемый закон (Е+ М) = (ЕМ)*. Если заменить переменные Е и М, соответственно, конкретными символами а и Ь, получим регупарные выражения (а + Ь) и (а Ь ) . Легко убедиться в том, что оба эти выражения задают язык всех возможных цепочек, составленных из а и Ь. Следовательно, оба конкретных выражения представляют один и эл же язык, и данный закон выполняется. В качестве еще одного примера рассмотрим закон Е = Е Е .
Конкретными языками будут а и а а „соответственно, и каждый из них представляет собой множество всех цепочек, состоящих из а. Снова видим, что данный закон выполняется, т.е, конкатенация итераций одного и того же языка дает ту же самую итерацию. Наконец, рассмотрим предполагаемый закон Е + МЕ = (Е + М)Е. Если заменить символами а и Ь переменные Е и М, соответственно, то получим два конкретных выражения а+ Ьа и (а+ Ь)а.
Однако языки этих выражений не совпадают. Например, цепочка аа 3.4. АЛГКБРАИЧЕСКИЕ ЗАКОНЫ ДЛЯ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙ 139 принадлежит второму языку, но не принадлежит первому. Следовательно, этот предпо- лагаемый закон ложен. П Расширение данной проверки за пределы регулярных выражений может оказаться ошибочным Рассмотрим расширенную алгебру регулярных выражений, включающую операцию пересечения. Интересно, что добавление операции П к трем представленным ранее операциям регулярных выражений не увеличивает множество задаваемых языков, что будет доказано ниже в теореме 4.8. В то же время сформулированная выше проверка алгебраических законов перестает работать. Рассмотрим "закон" Ь П МП Ф = Ь П М, утверждающий, что пересечение некоторых трех языков равно пересечению только двух первых из них, Очевидно, что этот закон ложен.
Например, если ь = М= (а), а ЬГ= 8. Но проверка, основанная на конкретизации переменных, может не определить ложность этого закона. Если мы заменим Ь, М и ЬГ символами а, Ь и с, соответственно, то должны будем проверить равенство (а) П (Ь) П (с) = (а) П (Ь). Поскольку обе части этого соотношения являются пустым множеством, равенство языков выполняется, и согласно нашей проверке этот "закон" будет истинным, хотя в действительности это не так.
3,4.8. Упражнения к разделу 3.4 3.4.1. Проверьте следующие тождества для регулярных выражений: а) («)К-«К=Я+К; б) (К+К)+ Т= К+(Я+ Т)„ в) (Кс)Т= К(57); г) К(Яж Т) =КЯ+ КТ; д) (К+5)Т= КТ+ 5T, е) («)(К) =-К; ж) (с+К)*=К „. з) (К К) =(К+К) . 3.4.2. (1) Докажите или опровергните каждое из следующих утверждений дпя регулярных выражений: а) (в) (К+ 5) = К ж 5"; б) (КК ь К) К = К(ЯК ь К); в) (э)(КБ+ К) Ку=(ККК); г) (К+5)'5=(К'5)'; 140 ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ д) Я(йЯ+ б)'й = И~'3(йй'Я)'.
3.4.3. В примере З.б было построено регулярное выражение (О + 1) 1(0 ь 1) + (О+ 1) 1(0+ 1)(0 ь 1). С помощью дистрибутивных законов преобразуйте его в два различных, более простых, эквивалентных выражения. В начале раздела 3.4.6 приведена часть доказательства того, что (Е М) = (ь'+М) . Завершите это доказательство, показав, что все цепочки из (Е М) принадлежат также (Е ь М) . 3.4.4. Резюме Регулярные вырижения. Этот алгебраический способ описания задает те же языки, что и конечные автоматы, а именно, регулярные языки. Регулярными операторами являются объединение, конкатенация ("точка*') и итерация ("звездочка"). Регулярные выражения на практике.
Системы, подобные ()г(1Х, и различные их команды используют язык расширенных регулярных выражений, существенно упрошаюший записи многих обычных выражений. Классы символов позволяют легко записывать выражения для наборов символов, а такие операторы, как "один или несколько из" и "не более, чем один из", расширяют круг обычных регулярных операторов. Экеивалентносгль регулярных выражений и конечных ивтоматов, Произвольный ДКА можно преобразовать в регулярное выражение с помошью индуктивной процедуры, в которой последовательно строятся выражения для меток путей, проходящих через постепенно увеличиваюшиеся множества состояний. В качестве альтернативы преобразованию ДКА в регулярное выражение можно также использовать метод исключения состояний.
С другой стороны, мы можем рекурсивно построить е-НКА по регулярному выражению, а потом в случае необходимости преобразовать полученный е-НКА в ДКА. Алгебра регулярных выражений. Регулярные выражения подчиняются многим ал- гебраическим законам арифметики, хотя есть и различия. Объединение н конкате- нация ассоциативны, но только объединение коммутативно.
Конкатенация дист- рибутивна относительно обьединения. Обьедннение идемпотентно. Проверка истинности аягебраических тождеств. Чтобы проверить эквивалент- ность регулярных выражений с переменными в качестве аргументов, необходимо подставить вместо этих переменных различные константы и проверить, будут ли совпадать языки, полученные в результате. 141 РВЗЮМЕ 3.4.5. (!) Завершите доказательство теоремы 3.13 для случаев, когда регулярное выражение Е представляет собой ГО или г" . Литература Идея регулярных выражений и доказательство их эквивалентности конечным автоматам представлены в работе Клини !3!. Преобразование регулярного выражения в е-НКА в том виде, как оно выглядит в этой книге, известно как "Метод Мак-Нотона-Ямады" из работы !4), Проверку тождеств регулярных выражений, в которой переменные рассматриваются как константы, предложил Дж.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
