dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 23
Текст из файла (страница 23)
Как всегда, L0 = {ε}, L1 = L.L2 — это множество цепочек, которые можно образовать, если взять одну цепочку изнулей и соединить ее с другой цепочкой из нулей. В результате получим цепочку, также состоящую из нулей. Фактически, любую цепочку из нулей можно записать какконкатенацию двух цепочек из нулей (не забывайте, что ε — тоже “цепочка из нулей”;она всегда может быть одной из двух соединяемых цепочек).
Следовательно, L2 = L.Аналогично, L3 = L и так далее. Таким образом, бесконечное объединение L* = L0 UL1 U L2 U … совпадает с L в том особом случае, когда язык L является множествомвсех нулевых цепочек.2Термин “замыкание Клини” связан с именем С. К. Клини, который ввел понятие регулярноговыражения и, в частности, эту операцию.3.1. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр. 103103В качестве последнего примера рассмотрим ∅* = {ε}. Заметим, что ∅0 = {ε}, тогдакак ∅i для любого i ≥ 1 будет пустым множеством, поскольку мы не можем выбрать ниодной цепочки из пустого множества. Фактически, ∅ является одним из всего двух языков, итерация которых не является бесконечным множеством.
3.1.2. Ïîñòðîåíèå ðåãóëÿðíûõ âûðàæåíèéВсе алгебры начинаются с некоторых элементарных выражений. Обычно это константы и/или переменные. Применяя определенный набор операторов к этим элементарным выражениям и уже построенным выражениям, можно конструировать более сложные выражения. Обычно необходимо также иметь некоторые методы группированияоператоров и операндов, например, с помощью скобок. К примеру, обычная арифметическая алгебра начинается с констант (целые и действительные числа) и переменных ипозволяет нам строить более сложные выражения с помощью таких арифметическихоператоров, как + или ×.Èñïîëüçîâàíèå îïåðàòîðà “çâåçäî÷êà”Впервые оператор “звездочка” появился в разделе 1.5.2, где применялся к алфавиту,например Σ*.
С помощью этого оператора образуются все цепочки, символы которыхпринадлежат алфавиту Σ. Оператор итерации в значительной мере похож на “звездочку”, хотя существует несколько тонких отличий в типах.Предположим, что L — это язык, содержащий цепочки длины 1, и для каждого символа а из Σ существует цепочка a в L. Тогда, хотя L и Σ “выглядят” одинаково, онипринадлежат к различным типам: L представляет собой множество цепочек, а Σ —множество символов. С другой стороны, L* обозначает тот же язык, что и Σ*.Алгебра регулярных выражений строится по такой же схеме: используются константы и переменные для обозначения языков и операторы для обозначения трех операций израздела 3.1.1 — объединение, точка и звездочка. Регулярные выражения можно определить рекурсивно.
В этом определении не только характеризуются правильные регулярные выражения, но и для каждого регулярного выражения E описывается представленный им язык, который обозначается через L(E).Базис. Базис состоит из трех частей.1.Константы ε и ∅ являются регулярными выражениями, определяющими языки {ε} и∅, соответственно, т.е. L(ε) = {ε} и L(∅) = ∅.2.Если а — произвольный символ, то а — регулярное выражение, определяющее язык{a}, т.е. L(a) = {a}. Заметим, что для записи выражения, соответствующего символу,используется жирный шрифт.
Это соответствие, т.е. что а относится к а, должнобыть очевидным.104Стр. 104ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈПеременная, обозначенная прописной курсивной буквой, например, L, представляетпроизвольный язык.3.Индукция. Индуктивный шаг состоит из четырех частей, по одной для трех операторов и для введения скобок.Если E и F — регулярные выражения, то E + F — регулярное выражение, опреде-1.ляющее объединение языков L(E) и L(F), т.е. L(E + F) = L(E) U L(F).Если E и F — регулярные выражения, то EF — регулярное выражение, определяющее конкатенацию языков L(E) и L(F).
Таким образом, L(EF) = L(E)L(F). Заметим,что для обозначения оператора конкатенации — как операции над языками, так иоператора в регулярном выражении — можно использовать точку. Например, регулярное выражение 0.1 означает то же, что и 01, и представляет язык {01}. Однакомы избегаем использовать точку в качестве оператора конкатенации в регулярныхвыражениях3.2.3.Если E — регулярное выражение, то E* — регулярное выражение, определяющееитерацию языка L(E). Таким образом, L(E*) = (L(E))*.4.Если E — регулярное выражение, то (E) — регулярное выражение, определяющеетот же язык L(E), что и выражение E. Формально, L((E)) = L(E).Âûðàæåíèÿ è ñîîòâåòñòâóþùèå ÿçûêèСтрого говоря, регулярное выражение Е — это просто выражение, а не язык.
Мы используем L(E) для обозначения языка, который соответствует E. Однако довольночасто говорят “E”, на самом деле подразумевая “L(E)”. Это соглашение используетсяв случаях, когда ясно, что речь идет о языке, а не о регулярном выражении.Пример 3.2. Напишем регулярное выражение для множества цепочек из чередующихся нулей и единиц. Сначала построим регулярное выражение для языка, состоящегоиз одной-единственной цепочки 01.
Затем используем оператор “звездочка” для того,чтобы построить выражение для всех цепочек вида 0101...01.Базисное правило для регулярных выражений говорит, что 0 и 1 — это выражения, обозначающие языки {0} и {1}, соответственно. Если соединить эти два выражения, то получится регулярное выражение 01 для языка {01}. Как правило, если мы хотим написать выражение для языка, состоящего из одной цепочки w, то используем саму w как регулярноевыражение.
Заметим, что в таком регулярном выражении символы цепочки w обычно выделяют жирным шрифтом, но изменение шрифта предназначено лишь для того, чтобы отличить выражение от цепочки, и не должно восприниматься как что-то существенное.3В UNIX точка в регулярных выражениях используется для совершенно другой цели — представления любого знака кода ASCII.3.1. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр. 105105Далее, для получения всех цепочек, состоящих из нуля или нескольких вхождений 01,используем регулярное выражение (01)*. Заметим, что выражение 01 заключается вскобки, чтобы не путать его с выражением 01*. Цепочки языка 01* начинаются с 0, за которым следует любое количество 1.
Причина такой интерпретации объясняется в разделе 3.1.3 и состоит в том, что операция “звездочка” имеет высший приоритет по сравнению с операцией “точка”, и поэтому аргумент оператора итерации выбирается до выполнения любых конкатенаций.Однако L((01)*) — не совсем тот язык, который нам нужен. Он включает только тецепочки из чередующихся нулей и единиц, которые начинаются с 0 и заканчиваются 1.Мы должны также учесть возможность того, что вначале стоит 1 и/или в конце 0. Однимиз решений является построение еще трех регулярных выражений, описывающих тридругие возможности.
Итак, (10)* представляет те чередующиеся цепочки, которые начинаются символом 1 и заканчиваются символом 0, 0(10)* можно использовать для цепочек, которые начинаются и заканчиваются символом 0, а 1(01)* — для цепочек, которыеи начинаются, и заканчиваются символом 1. Полностью это регулярное выражение имеет следующий вид.(01)* + (10)* + 0(10)* + 1(01)*Заметим, что оператор + используется для объединения тех четырех языков, которыевместе дают все цепочки, состоящие из чередующихся символов 0 и 1.Однако существует еще одно решение, приводящее к регулярному выражению, которое имеет значительно отличающийся и к тому же более краткий вид.
Снова начнем свыражения (01)*. Можем добавить необязательную единицу в начале, если слева к этомувыражению допишем выражение ε + 1. Аналогично, добавим необязательный 0 в конце спомощью конкатенации с выражением ε + 0. Например, используя свойства оператора +,получим, чтоL(ε + 1) = L(ε) U L(1) = {ε}{1} = {ε, 1}.Если мы допишем к этому языку любой другой язык L, то выбор цепочки ε даст намвсе цепочки из L, а выбрав 1, получим 1w для каждой цепочки w из L. Таким образом,совокупность цепочек из чередующихся нулей и единиц может быть представлена следующим выражением.(ε + 1)(01)*(ε + 0)Обратите внимание на то, что суммируемые выражения необходимо заключать вскобки, чтобы обеспечить правильную группировку операторов.
3.1.3. Ïðèîðèòåòû ðåãóëÿðíûõ îïåðàòîðîâКак и в других алгебрах, операторы регулярных выражений имеют определенные“приоритеты”, т.е. операторы связываются со своими операндами в определенном порядке. Мы знакомы с понятием приоритетности для обычных арифметических выраже106Стр. 106ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈний. Например, мы знаем, что в выражении xy + z умножение xy выполняется перед сложением, так что это выражение эквивалентно выражению со скобками (xy) + z, а неx(y + z).
Аналогично, в арифметике мы группируем одинаковые операторы слева направо, поэтому x – y – z эквивалентно выражению (x – y) – z, а не x – (y – z). Для оператороврегулярных выражений определен следующий порядок приоритетов.1.Оператор “звездочка” имеет самый высокий приоритет, т.е. этот оператор применяется только к наименьшей последовательности символов, находящейся слева от негои являющейся правильно построенным регулярным выражением.2.Далее по порядку приоритетности следует оператор конкатенации, или “точка”. Связав все “звездочки” с их операндами, связываем операторы конкатенации с соответствующими им операндами, т.е. все смежные (соседние, без промежуточных операторов) выражения группируются вместе.
Поскольку оператор конкатенации являетсяассоциативным, то не имеет значения, в каком порядке мы группируем последовательные конкатенации. Если же необходимо сделать выбор, то следует группироватьих, начиная слева. Например, 012 группируется как (01)2.3.В заключение, со своими операндами связываются операторы объединения (операторы +). Поскольку объединение тоже является ассоциативным оператором, то и здесь неимеет большого значения, в каком порядке сгруппированы последовательные объединения, однако мы будем придерживаться группировки, начиная с левого края выражения.Конечно, иногда нежелательно, чтобы группирование в регулярном выражении определялось только приоритетом операторов. В таких случаях можно расставить скобки исгруппировать операнды по своему усмотрению.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
