dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 31
Текст из файла (страница 31)
В следующей теореме доказывается общий закондля регулярных выражений.Теорема 3.13. Пусть E — регулярное выражение с переменными L1, L2, …, Lm. Построим конкретное регулярное выражение С, заменив каждое вхождение Li символом ai,i = 1, 2, …, m. Тогда для произвольных языков L1, L2, …, Lm любую цепочку w из L(E)можно представить в виде w = w1w2…wk, где каждая wi принадлежит одному из этих языков, например Lji, а цепочка aj1aj2...ajk принадлежит языку L(C). Говоря менее формально,мы можем построить L(E), исходя из каждой цепочки языка L(C), скажем, aj1aj2…ajk, изаменяя в ней каждый из символов aji любой цепочкой из соответствующего языка Lji.Доказательство.
Доказательство проведем структурной индукцией по выражению Е.Базис. Базисными являются случаи, когда E представляет собой ε, ∅ или переменнуюL. В первых двух случаях нечего доказывать, потому что конкретное выражение С совпадает с Е. Если же Е есть переменная L, то L(E) = L. Конкретное выражение С равнопросто a, где a — символ, соответствующий переменной L.
Следовательно, L(C) = {a}.Если в эту единственную цепочку вместо символа a подставить любую цепочку из L, тополучим язык L, который есть также L(E).Индукция. Рассмотрим три случая в зависимости от заключительной операции выражения E. Сначала предположим, что E =F + G, т.е. заключительной является операцияобъединения. Пусть C и D — конкретные выражения, построенные соответственно по Fи G с помощью подстановки в эти выражения определенных символов вместо языковыхпеременных. Заметим, что в оба выражения F и G вместо всех одинаковых переменныхдолжны быть подставлены одинаковые символы. Тогда конкретное выражение, полученное из выражения E, равно C + D, и L(C + D) = L(C) + L(D).Предположим, что w — цепочка из языка L(E), полученная в результате замены языковых переменных выражения E некоторыми определенными языками. Тогда w принадлежит либо L(F), либо L(G). Согласно индуктивной гипотезе цепочка w получена, исходяиз некоторой конкретной цепочки w1, принадлежащей L(C) или L(D), соответственно, спомощью подстановки цепочек из соответствующих языков вместо символов цепочкиw1.
Таким образом, в обоих случаях цепочка w может быть построена, начиная с некоторой конкретной цепочки w1 из L(C + D), путем одних и тех же подстановок цепочек вместо символов.Необходимо также рассмотреть случаи, когда E представляет собой FG или F*.
Однако доказательства для конкатенации и итерации аналогичны приведенному выше доказательству для объединения, поэтому оставляем их читателю. 138Стр. 138ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈ3.4.7. Ïðîâåðêà èñòèííîñòè àëãåáðàè÷åñêèõ çàêîíîâäëÿ ðåãóëÿðíûõ âûðàæåíèéТеперь можно сформулировать и обосновать проверку истинности законов для регулярных выражений. Проверка истинности закона E = F, где E и F — два регулярных выражения с одним и тем же набором переменных, состоит в следующем.1.Преобразуем E и F в конкретные регулярные выражения C и D соответственно, заменяя каждую переменную конкретным символом.2.Проверим равенство L(C) = L(D).
Если оно выполняется, то закон E = F истинен, а еслинет — ложен. Заметим, что проверять, определяют ли два регулярных выражения одини тот же язык, мы научимся в разделе 4.4. Однако можно использовать некоторые специальные (ad-hoc) средства для проверки равенства пар интересующих нас языков. Напомним, что если языки не совпадают, то достаточно построить контрпример, т.е. найти хотя бы одну цепочку, принадлежащую только одному из них.Теорема 3.14. Предложенная выше проверка правильно определяет истинность законов для регулярных выражений.Доказательство. Докажем, что L(E) = L(F) для любых языков, подставленных вместопеременных E и F, тогда и только тогда, когда L(C) = L(D).(Необходимость) Предположим, что L(E) = L(F) для любых языков, подставляемыхвместо переменных. В частности, выберем для каждой переменной L конкретный символa, заменяющий L в выражениях C и D.
Тогда L(C) = L(E) и L(D) = L(F). Поскольку мыпредположили, что L(E) = L(F), то L(C) = L(D).(Достаточность) Теперь предположим, что L(C) = L(D). Согласно теореме 3.13 L(E)и L(F) построены с помощью замены конкретных символов в цепочках из L(C) и L(D)цепочками из языков, соответствующих этим символам. Если L(C) и L(D) состоят из одних и тех же цепочек, то оба языка, построенные таким способом, тоже будут совпадать;т.е. L(E) = L(F). Пример 3.15.
Проанализируем предполагаемый закон (L + M)* = (L*M*)*. Если заменить переменные L и M, соответственно, конкретными символами a и b, получим регулярные выражения (a + b)* и (a*b*)*. Легко убедиться в том, что оба эти выражения задают язык всех возможных цепочек, составленных из a и b. Следовательно, оба конкретных выражения представляют один и тот же язык, и данный закон выполняется.В качестве еще одного примера рассмотрим закон L* = L*L*. Конкретными языкамибудут a* и a*a*, соответственно, и каждый из них представляет собой множество всех цепочек, состоящих из a. Снова видим, что данный закон выполняется, т.е. конкатенацияитераций одного и того же языка дает ту же самую итерацию.Наконец, рассмотрим предполагаемый закон L + ML = (L + M)L. Если заменить символами a и b переменные L и M, соответственно, то получим два конкретных выраженияa + ba и (a + b)a. Однако языки этих выражений не совпадают.
Например, цепочка aa3.4. ÀËÃÅÁÐÀÈ×ÅÑÊÈÅ ÇÀÊÎÍÛ ÄËß ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉСтр. 139139принадлежит второму языку, но не принадлежит первому. Следовательно, этот предполагаемый закон ложен. Ðàñøèðåíèå äàííîé ïðîâåðêè çà ïðåäåëû ðåãóëÿðíûõ âûðàæåíèéìîæåò îêàçàòüñÿ îøèáî÷íûìРассмотрим расширенную алгебру регулярных выражений, включающую операциюпересечения. Интересно, что добавление операции I к трем представленным ранееоперациям регулярных выражений не увеличивает множество задаваемых языков, чтобудет доказано ниже в теореме 4.8. В то же время сформулированная выше проверкаалгебраических законов перестает работать.Рассмотрим “закон” L I M I N = L I M, утверждающий, что пересечение некоторыхтрех языков равно пересечению только двух первых из них.
Очевидно, что этот законложен. Например, если L = M = {a}, а N = ∅. Но проверка, основанная на конкретизации переменных, может не определить ложность этого закона. Если мы заменим L, Mи N символами a, b и c, соответственно, то должны будем проверить равенство{a} I {b} I {c} = {a} I {b}. Поскольку обе части этого соотношения являются пустым множеством, равенство языков выполняется, и согласно нашей проверке этот“закон” будет истинным, хотя в действительности это не так.3.4.8. Óïðàæíåíèÿ ê ðàçäåëó 3.43.4.1.Проверьте следующие тождества для регулярных выражений:а) (∗) R + S = S + R;б) (R + S) + T = R + (S + T);в) (RS)T = R(ST);г) R(S + T) = RS + RT;д) (R + S)T = RT + ST;е) (∗) (R*)* = R*;ж) (ε + R)* = R*;з) (R*S*)* = (R + S)*.3.4.2.(!) Докажите или опровергните каждое из следующих утверждений для регулярных выражений:а) (∗) (R + S)* = R* + S*;б) (RS + R)*R = R(SR + R)*;в) (∗) (RS + R)*RS = (RR*S)*;г) (R + S)*S = (R*S)*;140Стр.
140ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈд) S(RS + S)*R = RR*S(RR*S)*.3.4.3.В примере 3.6 было построено регулярное выражение(0 + 1)*1(0 + 1) + (0 + 1)*1(0 + 1)(0 + 1).С помощью дистрибутивных законов преобразуйте его в два различных, болеепростых, эквивалентных выражения.3.4.4.В начале раздела 3.4.6 приведена часть доказательства того, что (L*M*)* =(L + M)*. Завершите это доказательство, показав, что все цепочки из (L*M*)*принадлежат также (L + M)*.3.4.5.(!) Завершите доказательство теоремы 3.13 для случаев, когда регулярное выражение E представляет собой FG или F*.Ðåçþìå♦ Регулярные выражения. Этот алгебраический способ описания задает те же языки,что и конечные автоматы, а именно, регулярные языки. Регулярными операторамиявляются объединение, конкатенация (“точка”) и итерация (“звездочка”).♦ Регулярные выражения на практике.
Системы, подобные UNIX, и различные ихкоманды используют язык расширенных регулярных выражений, существенно упрощающий записи многих обычных выражений. Классы символов позволяют легко записывать выражения для наборов символов, а такие операторы, как “одинили несколько из” и “не более, чем один из”, расширяют круг обычных регулярных операторов.♦ Эквивалентность регулярных выражений и конечных автоматов. ПроизвольныйДКА можно преобразовать в регулярное выражение с помощью индуктивной процедуры, в которой последовательно строятся выражения для меток путей, проходящих через постепенно увеличивающиеся множества состояний. В качестве альтернативы преобразованию ДКА в регулярное выражение можно также использовать метод исключения состояний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
