ГЛАВА 3

Регулярные выражения и языки

В этой главе вводится система записи «регулярных выражений». Такие выражения пред­ставляют собой еще один способ определения языков, рассмотренный вкратце в разде­ле 1.1.2. Регулярные выражения можно рассматривать также как «язык программирова­ния» для описания некоторых важных приложений, например, программ текстового поиска или компонентов компилятора. Регулярные выражения тесно связаны с НКА и могут служить удобной альтернативой для описания программных компонентов.

Определив регулярные выражения, покажем, что они могут задавать регулярные, и только регулярные, языки. Обсудим также, каким образом регулярные выражения ис­пользуются в различных системах программного обеспечения. Затем исследуем алгеб­раические законы для регулярных выражений. Эти законы во многом подобны алгебраи­ческим законам арифметики, однако между алгебрами регулярных и арифметических выражений есть и существенные различия.

3.1. Регулярные выражения

Перейдем от «машинного» задания языков с помощью ДКА и НКА к алгебраическо­му описанию языков с помощью регулярных выражений. Установим, что регулярные выражения определяют точно те же языки, что и различные типы автоматов, а именно, регулярные языки. В то же время, в отличие от автоматов, регулярные выражения позво­ляют определять допустимые цепочки декларативным способом. Поэтому регулярные выражения используются в качестве входного языка во многих системах, обрабатываю­щих цепочки. Рассмотрим два примера.

1. Команды поиска, например, команда grep операционной системы UNIX или анало­гичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах регулярные выражения ис­пользуются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют регулярное выражение либо в ДКА, либо в НКА и применяют этот автомат к файлу, в котором производится поиск.
2. Генераторы лексических анализаторов, такие как Lex или Flex. Напомним, что лек­сический анализатор — это компонент компилятора, разбивающий исходную про­грамму на логические единицы {лексемы), которые состоят из одного или несколь­ких символов и имеют определенный смысл. Примерами лексем являются ключевые слова (например while), идентификаторы (любая буква, за которой следует нуль или несколько букв и/или цифр) и такие знаки, как + или < = . Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу ре­гулярными выражениями, и создает ДКА, который распознает, какая из лексем по­является на его входе.

3.1.1. Операторы регулярных выражений

Регулярные выражения обозначают (задают, или представляют) языки. В качестве простого примера рассмотрим регулярное выражение 01*+10*. Оно определяет язык всех цепочек, состоящих либо из одного нуля, за которым следует любое количество единиц, либо из одной единицы, за которой следует произвольное количество нулей. В данный момент мы не рассчитываем, что читатель знает, как интерпретируются регулярные вы­ражения, поэтому наше утверждение о языке, задаваемом этим выражением, пока долж­но быть принято на веру. Чтобы понять, почему наша интерпретация заданного регуляр­ного выражения правильна, необходимо определить все использованные в этом выраже­нии символы, поэтому вначале познакомимся со следующими тремя операциями над языками, соответствующими операторам регулярных выражений^[1].

1. Объединение двух языков L и М, обозначаемое L\J М, — это множество цепочек, ко­торые содержатся либо в L, либо в М, либо в обоих языках. Например, если L = {001, 10, 111} и М= {£, 001}, то LUМ= {£, 10, 001, 111}.
2. Конкатенация языков L и М— это множество цепочек, которые можно образовать путем дописывания к любой цепочке из L любой цепочки из М. Выше в разделе 1.5.2 было дано определение конкатенации двух цепочек: результатом ее является запись одной цепочки вслед за другой. Конкатенация языков обозначается либо точкой, ли­бо вообще никак не обозначается, хотя оператор конкатенации часто называют «точкой». Например, если L= {001, 10, 111} и М- {£,001}, то L.M, или просто LM, — это {001, 10, 111, 001001, 10001, 111001}. Первые три цепочки в LM— это цепочки из L, соединенные с £. Поскольку £ является единицей (нейтральным эле­ментом) для операции конкатенации, результирующие цепочки будут такими же, как и цепочки из L. Последние же три цепочки в LM образованы путем соединения каж­дой цепочки из L со второй цепочкой из М, т.е. с 001. Например, 10 из L, соединен­ная с 001 из М, дает 10001 для LM.
3. Итерация («звездочка», или замыкание Клини^[2]) языка I обозначается L* и представ­ляет собой множество всех тех цепочек, которые можно образовать путем конкате­нации любого количества цепочек из L. При этом допускаются повторения, т.е. одна и та же цепочка из L может быть выбрана для конкатенации более одного раза. На­пример, если L = {0, 1}, то L* — это все цепочки, состоящие из нулей и единиц. Если L = {0, 11}, то в L’ входят цепочки из нулей и единиц, содержащие четное количест­во единиц, например, цепочки 011, 11110 или £, и не входят цепочки 01011 или 101. Более формально язык L* можно представить как бесконечное объединение Ueo L\ где L⁰ = {£},/,’=/, и L¹ для i > 1 равен LL…L (конкатенация i копий L).

Пример 3.1. Поскольку идея итерации языка может показаться довольно сложной, рассмотрим несколько примеров. Для начала возьмем L= {0, 11}. L° = {£} независимо от языка L\ нулевая степень означает выбор нулевого количества цепочек из языка L. L^l = L, что означает выбор одной цепочки из L. Таким образом, первые два члена в разложении L* дают {е, 0, 11}.

Далее рассмотрим /Л Выберем две цепочки из L и, поскольку их можно выбирать с повторениями, получим четыре варианта, которые дают L² = {00, 011, 110, 1111}. Анало­гично, Z,^[3] представляет собой множество цепочек, образованных троекратным выбором из двух цепочек языка L. Следовательно, ll имеет вид

{000, 0011,0110, 1100,01111, 11011, 11110, 111111}

Для вычисления L необходимо вычислить L’ для каждого i и объединить все эти язы­ки. Язык Z,¹ содержит 2¹ элементов. Хотя каждое множество V конечно, объединение бес­конечного числа множеств L¹ образует, как правило, бесконечный язык, что справедливо, в частности, и для нашего примера.

Пусть теперь L — множество всех цепочек, состоящих из нулей. Заметим, что такой язык бесконечен, в отличие от предыдущего примера, где был рассмотрен конечный язык. Однако нетрудно увидеть, что представляет собой L*. Как всегда, L⁰ = {£}, l) = L. L² — это множество цепочек, которые можно образовать, если взять одну цепочку из нулей и соединить ее с другой цепочкой из нулей. В результате получим цепочку, так­же состоящую из нулей. Фактически, любую цепочку из нулей можно записать как конкатенацию двух цепочек из нулей (не забывайте, что £ — тоже «цепочка из нулей»; она всегда может быть одной из двух соединяемых цепочек). Следовательно, L² = L. Аналогично, I? = L и так далее. Таким образом, бесконечное объединение L* = Z,⁰ U L^l U L² U •■■ совпадает с L в том особом случае, когда язык L является множеством всех нулевых цепочек.

В качестве последнего примера рассмотрим 0 = {е}. Заметим, что 0°= {£}, тогда как 0¹ для любого / > 1 будет пустым множеством, поскольку мы не можем выбрать ни одной цепочки из пустого множества. Фактически, 0 является одним из всего двух язы­ков, итерация которых не является бесконечным множеством. □

3.1.2. Построение регулярных выражений

Все алгебры начинаются с некоторых элементарных выражений. Обычно это кон­станты и/или переменные. Применяя определенный набор операторов к этим элементар­ным выражениям и уже построенным выражениям, можно конструировать более слож­ные выражения. Обычно необходимо также иметь некоторые методы группирования операторов и операндов, например, с помощью скобок. К примеру, обычная арифмети­ческая алгебра начинается с констант (целые и действительные числа) и переменных и позволяет нам строить более сложные выражения с помощью таких арифметических операторов, как + или х.

Использование оператора «звездочка»

Впервые оператор «звездочка» появился в разделе 1.5.2, где применялся к алфавиту, например Z . С помощью этого оператора образуются все цепочки, символы которых принадлежат алфавиту Z. Оператор итерации в значительной мере похож на «звез­дочку», хотя существует несколько тонких отличий в типах.

Предположим, что L — это язык, содержащий цепочки длины 1, и для каждого сим­вола а из Е существует цепочка а в [.. Тогда, хотя L и £ «выглядят» одинаково, они принадлежат к различным типам: L представляет собой множество цепочек, а 2 — множество символов. С другой стороны, L* обозначает тот же язык, что и £*.

Алгебра регулярных выражений строится по такой же схеме: используются констан­ты и переменные для обозначения языков и операторы для обозначения трех операций из раздела 3.1.1 — объединение, точка и звездочка. Регулярные выражения можно опреде­лить рекурсивно. В этом определении не только характеризуются правильные регуляр­ные выражения, но и для каждого регулярного выражения Е описывается представлен­ный им язык, который обозначается через L(E).

Базис. Базис состоит из трех частей.

1. Константы £ и 0 являются регулярными выражениями, определяющими языки {£} и 0, соответственно, т.е. L(e) = {£} и Ц0) = 0.
2. Если а — произвольный символ, то а — регулярное выражение, определяющее язык {а}, т.е. 1(a) = {а}. Заметим, что для записи выражения, соответствующего символу, используется жирный шрифт. Это соответствие, т.е. что а относится к а, должно быть очевидным.
3. Переменная, обозначенная прописной курсивной буквой, например, L, представляет произвольный язык.

Индукция. Индуктивный шаг состоит из четырех частей, по одной для трех операто­ров и для введения скобок.

1. Если Е и F— регулярные выражения, то E+F— регулярное выражение, опреде­ляющее объединение языков L(E) и L(F), т.е. L(E + F) = L(E) U L(F)-
2. Если E и F — регулярные выражения, то EF — регулярное выражение, определяю­щее конкатенацию языков L(E) и L(F). Таким образом, L(EF) = L(E)L(F). Заметим, что для обозначения оператора конкатенации— как операции над языками, так и оператора в регулярном выражении — можно использовать точку. Например, регу­лярное выражение 0.1 означает то же, что и 01, и представляет язык {01}. Однако мы избегаем использовать точку в качестве оператора конкатенации в регулярных выражениях^[4].
3. Если Е— регулярное выражение, то Е*— регулярное выражение, определяющее итерацию языка Ь(Е). Таким образом, ЦБ’) = (ЦБ))’.
4. Если Е — регулярное выражение, то (Е) — регулярное выражение, определяющее тот же язык L(E), что и выражение Е. Формально, L{{E)) = L(E).

Выражения и соответствующие языки

Строго говоря, регулярное выражение Е— это просто выражение, а не язык. Мы ис­пользуем L(E) для обозначения языка, который соответствует Е. Однако довольно часто говорят «£», на самом деле подразумевая «/,(£)». Это соглашение используется в случаях, когда ясно, что речь идет о языке, а не о регулярном выражении.

Пример 3.2. Напишем регулярное выражение для множества цепочек из чередую­щихся нулей и единиц. Сначала построим регулярное выражение для языка, состоящего из одной-единственной цепочки 01. Затем используем оператор «звездочка» для того, чтобы построить выражение для всех цепочек вида 0101…01.

Базисное правило для регулярных выражений говорит, что 0 и 1 — это выражения, обо­значающие языки {0} и {1}, соответственно. Если соединить эти два выражения, то полу­чится регулярное выражение 01 для языка {01}. Как правило, если мы хотим написать вы­ражение для языка, состоящего из одной цепочки w, то используем саму w как регулярное выражение. Заметим, что в таком регулярном выражении символы цепочки w обычно вы­деляют жирным шрифтом, но изменение шрифта предназначено лишь для того, чтобы от­личить выражение от цепочки, и не должно восприниматься как что-то существенное.

Далее, для получения всех цепочек, состоящих из нуля или нескольких вхождений 01, используем регулярное выражение (01) . Заметим, что выражение 01 заключается в скобки, чтобы не путать его с выражением 01*. Цепочки языка 01* начинаются с 0, за ко­торым следует любое количество 1. Причина такой интерпретации объясняется в разде­ле 3.1.3 и состоит в том, что операция «звездочка» имеет высший приоритет по сравне­нию с операцией «точка», и поэтому аргумент оператора итерации выбирается до выпол­нения любых конкатенаций.

Однако Ц(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(e + 1) = Де) U 1(1) ={£}{/} = {£, 1}.

Если мы допишем к этому языку любой другой язык L, то выбор цепочки е даст нам все цепочки из L, а выбрав 1, получим \м> для каждой цепочки w из L. Таким образом, совокупность цепочек из чередующихся нулей и единиц может быть представлена сле­дующим выражением.

(£+ 1)(01)*(£+0)

Обратите внимание на то, что суммируемые выражения необходимо заключать в скобки, чтобы обеспечить правильную группировку операторов. □

3.1.3. Приоритеты регулярных операторов

Как и в других алгебрах, операторы регулярных выражений имеют определенные «приоритеты», т.е. операторы связываются со своими операндами в определенном по­рядке. Мы знакомы с понятием приоритетности для обычных арифметических выраже­ний. Например, мы знаем, что в выражении ху + z умножение ху выполняется перед сло­жением, так что это выражение эквивалентно выражению со скобками (ху) + z, а не х(у + z). Аналогично, в арифметике мы группируем одинаковые операторы слева напра­во, поэтому x—y — z эквивалентно выражению (x-y)-z, а не х- (у -z). Для операторов регулярных выражений определен следующий порядок приоритетов.

1. Оператор «звездочка» имеет самый высокий приоритет, т.е. этот оператор применя­ется только к наименьшей последовательности символов, находящейся слева от него и являющейся правильно построенным регулярным выражением.
2. Далее по порядку приоритетности следует оператор конкатенации, или «точка». Свя­зав все «звездочки» с их операндами, связываем операторы конкатенации с соответ­ствующими им операндами, т.е. все смежные (соседние, без промежуточных опера­торов) выражения группируются вместе. Поскольку оператор конкатенации является ассоциативным, то не имеет значения, в каком порядке мы группируем последова­тельные конкатенации. Если же необходимо сделать выбор, то следует группировать их, начиная слева. Например, 012 группируется как (01)2.
3. В заключение, со своими операндами связываются операторы объединения (опера­торы +). Поскольку объединение тоже является ассоциативным оператором, то и здесь не имеет большого значения, в каком порядке сгруппированы последовательные объедине­ния, однако мы будем придерживаться группировки, начиная с левого края выражения.

Конечно, иногда нежелательно, чтобы группирование в регулярном выражении опре­делялось только приоритетом операторов. В таких случаях можно расставить скобки и сгруппировать операнды по своему усмотрению. Кроме того, не запрещается заключать в скобки операнды, которые вы хотите сгруппировать, даже если такое группирование подразумевается правилами приоритетности операторов.

Пример 3.3. Выражение 01* + 1 группируется как (0(1*))+ 1. Сначала выполняется оператор «звездочка». Поскольку символ 1, находящийся непосредственно слева от опе­ратора, является допустимым регулярным выражением, то он один будет операндом «звездочки». Далее группируем конкатенацию 0 и (1)* и получаем выражение (0(1*)). На­конец, оператор объединения связывает последнее выражение с выражением, которое находится справа, т.е. с 1.

Заметим, что язык данного выражения, сгруппированного согласно правилам при­оритетности, содержит цепочку 1 плюс все цепочки, начинающиеся с 0, за которым сле­дует любое количество единиц (в том числе и ни одной). Если бы мы захотели сначала сгруппировать точку, а потом звездочку, то следовало бы использовать скобки: (01)* + 1. Язык этого выражения состоит из цепочки 1 и всех цепочек, в которых 01 повторяется нуль или несколько раз. Для того чтобы сначала выполнить объединение, его нужно за­ключить в скобки: 0(1*+ 1). Язык этого выражения состоит из цепочек, которые начи­наются с 0 и продолжаются любым количеством единиц. □

3.1.4. Упражнения к разделу 3.1

• Напишите регулярные выражения для следующих языков:

а)  (*) множество цепочек с алфавитом {а, Ь, с}, содержащих хотя бы один сим­вол а и хотя бы один символ Ь\

б)  множество цепочек из нулей и единиц, в которых десятый от правого края символ равен 1;

в)   множество цепочек из нулей и единиц, содержащих не более одной пары по­следовательных единиц.

• (!) Напишите регулярные выражения для следующих языков:

а)  (*) множество всех цепочек из нулей и единиц, в которых каждая пара смеж­ных нулей находится перед парой смежных единиц;

б)  множество цепочек, состоящих из нулей и единиц, в которых число нулей кратно пяти.

• (!!) Напишите регулярные выражения для следующих языков:

а)  множество всех цепочек из нулей и единиц, в которых нет подцепочки 101;

б)  множество всех цепочек, в которых поровну нулей и единиц и ни один их префикс не содержит нулей на два больше, чем единиц, или единиц на две больше, чем нулей;

в)   множество всех цепочек из нулей и единиц, в которых число нулей делится на пять, а количество единиц четно.

• (!) Опишите обычными словами языки следующих регулярных выражений:

а)  (*) (1 + e)(00*l)V;

б)  (0Y)*000(0 + 1)*;

в)   (0 + 10)*1*.

• (*!) В примере 3.1 отмечено, что 0 — это один из двух языков, итерация кото­рых является конечным множеством. Укажите второй язык.

3.2. Конечные автоматы и регулярные выражения

Хотя описание языков с помощью регулярных выражений принципиально отличается от конечноавтоматного, оказывается, что обе эти нотации представляют одно и то же множество языков, называемых «регулярными». Выше мы показали, что детерминиро­ванные конечные автоматы, а также два вида недетерминированных конечных автома­тов — с £-переходами и без £-переходов — допускают один и тот же класс языков. Для того чтобы показать, что регулярные выражения задают тот же класс языков, необходи­мо доказать следующее.

1. J. Любой язык, задаваемый одним из этих автоматов, может быть также определен ре­гулярным выражением. Для доказательства можно предположить, что язык допуска­ется некоторым ДКА.
2. Любой язык, определяемый регулярным выражением, может быть также задан с по­мощью одного из вышеуказанных автоматов. Для этой части доказательства проще всего показать, что существует НКА с £-переходами, допускающий тот же самый язык.

На рис. 3.1 показаны все эквивалентности, которые уже доказаны или будут доказа­ны. Дуга, ведущая от класса X к классу Y, означает, что каждый язык, определяемый классом X, определяется также классом Y. Поскольку данный граф является сильно связ­ным (в нем можно перейти от каждой из четырех вершин к любой другой вершине), по­нятно, что все четыре класса на самом деле эквивалентны.

Рис. 3.1. План доказательства эквивалентности четырех различных нотаций для регулярных языков

3.2.1. От ДКА к регулярным выражениям

Построение регулярного выражения для языка, допускаемого некоторым ДКА, ока­зывается на удивление сложным. Приблизительно это выглядит так: мы строим выраже­ния, описывающие множества цепочек, которыми помечены определенные пути на диа­грамме ДКА. Однако эти пути могут проходить только через ограниченное подмножест­во состояний. При индуктивном определении таких выражений мы начинаем с самых простых выражений, описывающих пути, которые не проходят ни через одно состояние (т.е. являются отдельными вершинами или дугами). Затем индуктивно строим выраже­ния, которые позволяют этим путям проходить через постепенно расширяющиеся мно­жества состояний. В конце этой процедуры получим пути, которые могут проходить че­рез любые состояния, т.е. сгенерируем выражения, представляющие все возможные пу­ти. Эти идеи используются в доказательстве следующей теоремы.

Теорема 3.4. Если L = L(A) для некоторого ДКА А, то существует регулярное выра­жение R, причем L = L(R).

Доказательство. Предположим, что {1,2, …, п) — множество состояний автомата А для некоторого натурального п. Независимо от того, какими эти состояния являются на самом деле, их конечное число п, поэтому их можно переименовать, используя первые п положительных целых чисел. Нашей первой и наиболее сложной задачей является по­строение набора регулярных выражений, которые описывают постепенно расширяю­щиеся множества путей в диаграмме переходов автомата Л.

Обозначим через R.p регулярное выражение, язык которого состоит из множества меток w путей, ведущих от состояния i к состоянию j автомата А и не имеющих проме­жуточных состояний с номерами больше к. Заметим, что начальная и конечная точки пу­ти не являются «промежуточными», поэтому мы не требуем, чтобы i и/или j были мень­ше или равны к.

Условия, налагаемые на пути выражениями , представлены на рис. 3.2. Здесь на вертикальной оси расположены состояния, начиная с 1 внизу до п вверху, а горизонталь­ная ось представляет движение вдоль пути. Заметим, что на этой диаграмме показан слу­чай, когда i и j больше, чем к, но любое из этих чисел, или оба, могут быть меньше или равны к. Также обратите внимание на то, что путь дважды проходит через вершину к, но только в крайних точках поднимается выше, чем к.

Рис. 3.2. Путь, отметка которого принадлежит языку регулярного выражения

Для построения выражения R-р используют следующее индуктивное определение, которое начинается с к = 0 и достигает к = п. Заметим, что при к = п пути ничем не огра­ничиваются, поскольку нет состояний с номерами, которые больше, чем п.

Базис. В качестве базиса примем к = 0. Поскольку все состояния пронумерованы от 1 и далее, то это условие означает, что у пути вообще нет промежуточных состояний. Су­ществует только два вида путей, удовлетворяющих такому условию.

1. Дуга, ведущая от вершины (состояния) i к вершине j.
2. Путь длины 0, состоящий лишь из некоторой вершины /.

Если i Ф j, то возможен только первый случай. Необходимо проанализировать данный ДКА А и найти такие входные символы а, по которым есть переход из состояния i в со­стояние j:

а) если таких символов нет, то Л^⁰‘ =0;

б)  если существует только один такой символ а, то = а;

в)   если существуют такие символы а_ь а₂, …, а_к, которыми помечены дуги из состояния i в состояние j, то = а, + а₂ + … + а_к.

В то же время, если i =j, то допустимыми путями являются путь длины 0 и все петли, которые начинаются и заканчиваются в состоянии Л Путь длины 0 может быть представ­лен регулярным выражением £, потому что вдоль этого пути нет символов. Следователь­но, добавляем е к выражениям, полученным выше в пунктах (а)—(в). Таким образом, в случае (а) [нет ни одного символа a] получим выражение £, в случае (б) [один символ а] выражение примет вид е + а, и в случае (в) [несколько символов] получим выражение £+ + а₂ + … + а_к.

Индукция. Предположим, что существует путь из состояния i в состояние j, не про­ходящий через состояния с номерами, которые больше, чем к. Необходимо рассмотреть две ситуации.

1. Путь вообще не проходит через состояние к. В этом случае метка пути принадлежит языку Rf~^X).

2. Путь проходит через состояние к по меньшей мере один раз. Тогда мы можем разде­лить путь на несколько частей, как показано на рис. 3.3. Первая часть ведет от со­стояния / к состоянию к, но не проходит через к, последняя ведет из А: в j, также не проходя через к, а все части, расположенные внутри пути, ведут из к в к, не проходя через к. Заметим, что если путь проходит через состояние к только один раз, то «внутренних» частей нет, а есть только путь из / в к и путь из А: в j. Множество меток для всех путей такого вида может быть представлено регулярным выражением К-л ^Ч) (^li» )* • Таким образом, первое выражение представляет часть пути, ве­дущую в состояние к в первый раз, второе — часть, ведущую т кв к нуль или не­сколько раз, и третье выражение— часть пути, которая выходит из состояния к в последний раз и ведет в состояние j.

Нуль или несколько цепочек в

Рис. 3.3. Путь из i в j может быть разбит на несколько сегментов в каждой точке, в которой он проходит через состояние к

После объединения выражений для путей двух рассмотренных выше типов получим следующее выражение для меток всех путей, ведущих из состояния / в состояние j, кото­рые не проходят через состояния с номерами, которые больше, чем к.

/#> = + дГЧдГ’ГдГ»

Поскольку данные выражения строятся в порядке возрастания верхнего индекса, можно построить любое выражение R⁽,p, так как оно зависит только от выражений с меньшими значениями верхнего индекса.

В итоге получим R\»^] для всех i и j. Можно предположить, что состояние 1 является на­чальным, а множество допускающих (заключительных) состояний может быть любым. То­гда регулярным выражением для языка, допускаемого данным автоматом, будет сумма (объединение) всех тех выражений R\»?, в которых состояние j является допускающим. □

Пример 3.5. Преобразуем ДКА, представленный на рис. 3.4, в соответствующее ре­гулярное выражение. Этот ДКА допускает все цепочки, содержащие хотя бы один 0. Чтобы понять, почему это так, заметим, что автомат переходит из начального состояния 1 в заключительное состояние 2, как только на входе появляется 0. Далее автомат остает­ся в заключительном состоянии 2 при любой входной последовательности.

1

Начало          0

Рис. 3.4. ДКА, допускающий все цепочки, которые содержат хотя бы один О Ниже приведены базисные выражения для построений согласно теореме 3.4. <> £ + 1 0 Ы0) 21 0 0(0) 22 (£+0 + 1)

Например, в выражении присутствует член е, потому что и начальным, и конеч­ным является состояние 1. Это выражение включает также 1, поскольку существует путь из состояния 1 в состояние 1 по входу 1. Выражение R^ равно 0, потому что есть дуга с меткой 0, ведущая из состояния 1 в состояние 2. Здесь нет члена £, поскольку начальное и конечное состояния различаются. И, наконец, R^ ⁼ 0, так как нет путей, ведущих из состояния 2 в состояние 1.

Теперь применим индукцию для построения более сложных выражений. Вначале они соответствуют путям, проходящим через состояние 1, а затем путям, которые могут про­ходить через состояния 1 и 2, т.е. любым путям. Правило для вычисления выражения р^Р представляет собой пример общего правила из индуктивной части теоремы 3.4.

4° ^{= +} ^(/ОЧ?                                                                 ^(ЗЛ)

В таблице на рис. 3.5 сначала представлены выражения, полученные с помощью пря­мой подстановки в приведенную выше формулу, а затем упрощенные выражения, кото­рые определяют те же языки, что и более сложные выражения.

	Прямая подстановка	Упрощенное выражение
D( О П11	£+ 1 + (£+ 1)(£+ 1)*(£+ 1)	1*
Rd) 12	0 + (£+ 1)(£+ 1)*0	1*0
D(l) 21	0 + 0(£+1)*(£+1)	0
D( 1) 22	£+0 + 1 +0(£+ 1)*0	£+0+1

Рис. 3.5. Регулярные выражения для путей, которые могут проходить только через состояние 1

Например, рассмотрим выражение Rff. Подставив /= 1 и у = 2 в (3.1), получим

Общим принципом упрощения является следующий: если R— произвольное регу­лярное выражение, то (е + R)* = R*. Он основан на том, что обе части этого равенства описывают язык, образованный конкатенациями нуля или нескольких цепочек из L(R). В нашем случае (£ + 1)* = 1*; отметим, что оба выражения описывают цепочки, состоящие из любого количества единиц. Далее, (£ + 1)1* = 1*. Опять-таки, легко заметить, что оба выражения означают «любое количество единиц». Следовательно, исходное выражение rV> эквивалентно выражению 0 + 1*0. Последнее описывает язык, содержащий цепочку 0 и все цепочки, заканчивающиеся символом 0, перед которым стоит произвольное ко­личество единиц. Такой язык также можно определить более простым выражением 1 *0.

Выражение Я® упрощается аналогично рассмотренному выше выражению R[₂ ■ Уп­рощение /г’,¹» и Я® зависит от двух следующих правил, описывающих операции с 0 и выполнимых для любого регулярного выражения R.

1. 0R = R0 = 0, т.е. 0 является нулем (аннулятором) для конкатенации. В результате конкатенации 0, слева или справа, с любым другим выражением получается 0. Это правило очевидно, поскольку для того, чтобы в результате конкатенации получить некоторую цепочку, мы должны взять цепочки из обоих аргументов конкатенации. Если один из аргументов равен 0, выбор цепочки из него становится невозможным.
2. 0+R-R+0 = R, т.е. 0 является единицей для операции объединения. В результа­те объединения любого выражения с 0 получим то же самое выражение.

Итак, выражение 0(£ + 1)*(£ + 1) можно заменить 0. После сказанного должны быть по­нятны и два последних упрощения.

Теперь вычислим выражения R. Индуктивное правило для к = 2 имеет следующий вид.

«^«f + j^^j’i»                                                                                     (3.2)

Если подставим упрощенные выражения из таблицы на рис. 3.5 в уравнение (3.2), то получим выражения, представленные на рис. 3.6. На этом рисунке также приведены уп­рощенные выражения, полученные согласно правилам, описанным для рис. 3.5.

	Прямая подстановка	Упрощенное выражение
R{2)	1*+ 1*0(£+0 + 1)*0	1*
г>(2) 12	1*0+ 1*0(£+0+ 1)*(£+0+ 1)	1*0(0 + 1)*
Ы2) 21	0 + (£+0+ 1)(£+0 + 1)*0	0
р( 2) 22	£ + 0 + 1 +(£+0 + 1)(£ + 0 + 1)*(£ +0+1)	(0+1)*

Рис. 3.6. Регулярные выражения для путей, которые могут проходить через любое состояние

Окончательное регулярное выражение, эквивалентное автомату, представленному на рис. 3.4, строится путем объединения всех тех выражений, для которых первое состояние является начальным, а второе — заключительным. В нашем примере 1 -— начальное со­стояние, а 2 — заключительное, поэтому нам нужно лишь выражение R^⁾, равное 1*0(0 + 1)*. Оно очень просто интерпретируется. Его язык состоит из всех цепочек, начи­нающихся с нулевого или некоторого количества единиц, за которыми следует 0, а за ним — любая цепочка из нулей и единиц. Иначе говоря, это все цепочки из 0 и 1, содер­жащие хотя бы один 0. □

3.2.2. Преобразование ДКА в регулярное выражение методом исключения состояний

Метод преобразования ДКА в регулярное выражение, представленный в разде­ле 3.2.1, работает всегда. Как вы, возможно, заметили, он на самом деле не зависит от того, детерминирован ли этот автомат, и точно так же применим и к НКА, и даже к е- НКА. Однако такой метод построения регулярного выражения очень трудоемок. Не только потому, что для автомата с п состояниями необходимо построить порядка п вы­ражений, но и потому, что с каждым из п шагов индукции длина выражения может воз­растать в среднем в четыре раза, если эти выражения не упрощать. Таким образом, раз­меры результирующих выражений могут достигать порядка 4″ символов.

Существует аналогичный метод, избавляющий от некоторых повторных действий. Например, во всех выражениях с верхним индексом (к) в доказательстве теоремы 3.4 ис­пользуется одно и то же подвыражение (R.f_k~^l) )*, которое приходится выписывать в об­щей сложности п² раз.

Метод построения регулярных выражений, который мы изучим в этом разделе, пред­полагает исключение состояний. Если исключить некоторое состояние s, то все пути ав­томата, проходящие через это состояние, исчезают. Для того чтобы язык автомата при этом не изменился, необходимо написать на дуге, ведущей непосредственно из некото­рого состояния q в состояние р, метки всех тех путей, которые вели из состояния q в со­стояние р, проходя через состояние s. Поскольку теперь метка такой дуги будет содер­жать цепочки, а не отдельные символы, и таких цепочек может быть даже бесконечно много, то мы не можем просто записать список этих цепочек в качестве метки. К сча­стью, существует простой и конечный способ для представления всех подобных цепочек, а именно, использование регулярных выражений.

Таким образом, мы пришли к рассмотрению автоматов, у которых метками являются регулярные выражения. Язык такого автомата представляет собой объединение по всем путям, ведущим от начального к заключительному состоянию, языков, образуемых с по­мощью конкатенации языков регулярных выражений, расположенных вдоль этих путей. Обратите внимание на то, что это правило согласуется с определением языка для любого рассмотренного выше типа автоматов. Каждый символ а или £, если он разрешен, можно рассматривать как регулярное выражение, языком которого является единственная це­почка, т.е. {а} или {£}. Можно принять это замечание за основу описываемой ниже про­цедуры исключения состояний.

На рис. 3.7 показано состояние s, которое мы собираемся исключить. Предполо­жим, что автомат, содержащий j, содержит состояния q_h q₂, …, qu, предшествующие j, ^и Ри Pi, …,Рпи следующие за s. Возможно, некоторые из состояний q совпадают с со­стояниями р, но мы предполагаем, что среди q и р нет s, даже если существует петля, ко­торая начинается и заканчивается в s, как показано на рис. 3.7. Над каждой дугой, веду­щей к состоянию s, указано регулярное выражение; дуга, ведущая из состояния q_t, поме­чена выражением Qi. Аналогично, регулярным выражением Р_{ помечена дуга, ведущая из s в состояние р\, для каждого г. Петля на s имеет метку S. Наконец, регулярным выраже­нием помечена каждая дуга, ведущая из q_x в p_t для всех i и j. Заметим, что некоторых из этих дуг в автомате может не быть. В этом случае в качестве выражения над дугой ис­пользуется символ 0.

На рис. 3.8 показано, что получится, если исключить состояние s. Все дуги, проходящие через s, удалены. Чтобы это компенсировать, для каждого состояния <у„ предшествующего s, и для каждого р_р следующего за s, вводится регулярное выражение, представляющее все пути, которые начинаются в q-„ идут к s, возможно, проходят петлю на s нуль или несколько раз, и наконец ведут в р_у Выражение для таких путей равно Q\S*P_y Это выражение добавля­ется (с помощью оператора объединения) к выражению над дугой из q\ в р_у Если дуга <7; —> p_i отсутствует, то вначале ей соответствует регулярное выражение 0.

Рис. 3.7. Состояние s, подлежащее исключению

Рис. 3.8. Результат исключения состояния s из автомата, изображенного на рис. 3.7

Стратегия построения регулярного выражения по конечному автомату такова.

1. Для каждого допускающего состояния q применить описанный выше процесс сокра­щения, чтобы построить эквивалентный автомат с дугами, помеченными регулярными выражениями. Исключить все состояния, кроме q и начального состояния q₀.
2. Если q Ф q₀, то должен остаться автомат с двумя состояниями, подобный автомату на рис. 3.9. Регулярное выражение для допустимых цепочек может быть записано по- разному. Один из видов — (R + SU*T)*SU*. Поясним его. Можно переходить из на­чального состояния в него же любое количество раз, проходя путями, метки которых принадлежат либо L(R), либо L(SU*T). Выражение SU*T представляет пути, которые ведут в допускающее состояние по пути с меткой из языка L(S), затем, возможно, несколько раз проходят через допускающее состояние, используя пути с метками из L(U), и наконец возвращаются в начальное состояние, следуя по пути с меткой из 1(7). Отсюда нужно перейти в допускающее состояние, уже никогда не возвращаясь в начальное, вдоль пути с меткой из L(S). Находясь в допускающем состоянии, мож­но сколько угодно раз вернуться в него по пути с меткой из L(U).

Рис. 3.9. Обобщенный автомат с двумя состояниями

3. Если же начальное состояние является допускающим, то необходимо точно так же исключить состояния исходного автомата, удалив все состояния, кроме начального. В результате получим автомат с одним состоянием, подобный представленному на рис. 3.10. Регулярное выражение R’ задает цепочки, допускаемые этим автоматом.

R

4. Искомое выражение представляет собой сумму (объединение) всех выражений, по­лученных с помощью сокращенного автомата для каждого допускающего состояния согласно правилам 2 и 3.

Пример 3.6. Рассмотрим НКА, представленный на рис. 3.11, допускающий цепочки из нулей и единиц, у которых либо на второй, либо на третьей позиции с конца стоит 1. Вна­чале преобразуем этот автомат в автомат с регулярными выражениями в качестве меток.

Пока исключение состояний не производилось, то все, что нам нужно сделать, это заменить метки «О, 1» эквивалентным регулярным выражением 0+1. Результат показан на рис. 3.12.

о, 1

Начало

0,1

0, 1

^{0                                                                                   1} /»»Л

0 + 1 Рис. 3.12. Автомат, изображенный нарис. 3.11, с регулярными выражениями в качестве меток

Исключим сначала состояние В. Поскольку это состояние не является ни начальным, ни допускающим, то его не будет ни в одном из сокращенных автоматов. Мы избавимся от лишней работы, если исключим это состояние до того, как начнем строить два сокра­щенных автомата, соответствующих двум его допускающим состояниям.

Существует одно состояние А, предшествующее В, и одно последующее состояние С. Используя обозначения регулярных выражений диаграммы, представленной на рис. 3.7, получим: Qi = 1, Р\ = 0 + 1, R_n = 0 (потому что из А в С дуги нет) и 5=0 (поскольку нет петли в состоянии В). В результате, выражение над новой дугой из А в С равно 0 + 10*(О + 1).

Для сокращения полученного выражения сначала исключаем первый элемент 0, кото­рый можно игнорировать при объединении. Выражение приобретает вид 10*(О + 1). На­помним, что регулярное выражение 0* эквивалентно регулярному выражению £, поскольку

Рис. 3.11. НКА, допускающий цепочки, у которых 1 находится либо на второй, либо на третьей позиции с конца цепочки

1(0*) = {£} и Ц0) и Ц0)Ц0) и…

Все члены этого объединения, кроме первого, пусты, поэтому 1(0*) = {£}, что совпа­дает с L(e). Следовательно, 10*(О+1) эквивалентно выражению 1(0+1), которое ис­пользовано для дуги А —> С на рис. 3.13.

0 + 1 Рис. 3.13. Исключение состояния В

Далее нужно по отдельности исключить состояния С и D. Процедура исключения со­стояния С аналогична описанному выше исключению состояния В, в результате чего по­лучится автомат, представленный на рис. 3.14.

0 + 1 Рис. 3.14. Автомат с двумя состояниями А и D

В обозначениях обобщенного автомата с двумя состояниями, изображенного на рис. 3.9, соответствующие регулярные выражения для рис. 3.14 равны: R= 0+1, S- 1(0 + 1)(0 + 1), Т= 0 и {/=0. Выражение U* можно заменить на £, т.е. исключить его из конкатенации, поскольку, как показано выше, 0* = е. Кроме того, выражение SU*T эквивалентно 0, потому что Т— один из операндов конкатенации— равен 0. Таким образом, общее выражение (R + SUT) SU в данном случае упрощается до R S, или (0 + 1)1(0 + 1)(0 + 1). Говоря неформально, язык этого выражения состоит из цепочек, заканчивающихся единицей с двумя последующими символами, каждый из которых мо­жет быть либо нулем, либо единицей. Этот язык представляет одну часть цепочек, кото­рые допускаются автоматом, изображенным на рис. 3.11: у них на третьей позиции с конца стоит 1.

Теперь снова нужно вернуться к рис. 3.13 и исключить состояние D. Поскольку в этом автомате нет состояний, следующих за D, то согласно рис. 3.7 необходимо лишь удалить дугу, ведущую из С в D, вместе с состоянием D. В результате получится автомат, показанный на рис. 3.15.

0 + 1

Начало 1(0 +1) S/^S —— Aj             ►ПСП

Рис. 3.15. Автомат с двумя состояниями, полученный в результате исключения состояния D

Порядок исключения состояний

Как было отмечено в примере 3.6, если состояние не является ни начальным, ни до­пускающим, то оно исключается во всех сокращенных автоматах. Таким образом, одно из преимуществ процесса исключения состояний по сравнению с механической генерацией регулярных выражений, описанной в разделе 3.2.1, состоит в том, что сначала мы раз и навсегда исключаем все состояния, которые не являются ни началь­ными, ни допускающими. Мы вынуждены повторять процедуру сокращения, только когда необходимо исключить несколько допускающих состояний. Но даже и в этом случае можно совместить некоторые действия процедуры сокраще­ния. Например, если автомат содержит три допускающих состояния р, q кг, то можно вначале исключить р, а затем отдельно исключить либо q, либо г, получив автоматы для допускающих состояний г и q, соответственно. Затем можно снова начать с трех допускающих состояний и, исключив состояния q и г, получить автомат для р.

Этот автомат очень похож на автомат, изображенный на рис. 3.14; различаются толь­ко метки над дугами, ведущими из начального состояния в допускающее. Следовательно, можно применить правило для автомата с двумя состояниями и упростить данное выра­жение, получив в результате (0 + 1)*1(0 + 1). Это выражение представляет другой тип цепочек, допустимых этим автоматом, — цепочки, у которых 1 стоит на второй пози­ции с конца.

Осталось объединить оба построенные выражения, чтобы получить следующее вы­ражение для всего автомата (см. рис. 3.11).

(О + 1)*1(0 + 1) + (0 + 1)*1(0 + 1)(0 + 1)

□

3.2.3. Преобразование регулярного выражения в автомат

Теперь завершим план, представленный на рис. 3.1, показав, что любой язык L, яв­ляющийся языком L(R) для некоторого регулярного выражения R, будет также языком ЦЕ) для некоторого £-НКА Е. Это доказательство проведем методом структурной ин­дукции по выражению R. Сначала покажем, как строить автоматы для базовых выраже­ний: отдельных символов, £ и 0. Затем опишем, каким образом объединять эти автоматы в большие автоматы, которые допускают объединение, конкатенацию или итерацию языков, допускаемых меньшими автоматами.

Все конструируемые автоматы представляют собой £-НКА с одним допускающим со­стоянием.

Теорема 3.7. Любой язык, определяемый регулярным выражением, можно задать не­которым конечным автоматом.

Доказательство. Предположим, что L = L(R) для регулярного выражения R. Пока­жем, что L = L(E) для некоторого £-НКА Е, обладающего следующими свойствами.

1. Он имеет ровно одно допускающее состояние.
2. У него нет дуг, ведущих в начальное состояние.
3. У него нет дуг, выходящих из допускающего состояния.

Доказательство проводится структурной индукцией по выражению R, следуя рекур­сивному определению регулярных выражений из раздела 3.1.2.

Базис. Базис состоит из трех частей, представленных на рис. 3.16. В части (а) рас­сматривается выражение е. Языком такого автомата является {е}, поскольку единствен­ный путь из начального в допускающее состояние помечен выражением £. В части (б) показана конструкция для 0. Понятно, что, поскольку отсутствуют пути из начального состояния в допускающее, языком этого автомата будет 0. Наконец, в части (в) пред­ставлен автомат для регулярного выражения а. Очевидно, что язык этого автомата со­стоит из одной цепочки а и равен L(а). Кроме того, все эти автоматы удовлетворяют ус­ловиям (1), (2) и (3) индуктивной гипотезы.

___________________ /

©

V_________________ /

б)

V___________ У

В)

Рис. 3.16. Базис построения автомата по регулярному выражению

Индукция. Три части индукции представлены на рис. 3.17. Предположим, что ут­верждение теоремы истинно для непосредственных подвыражений данного регулярного выражения, т.е. языки этих подвыражений являются также языками £-НКА с единствен­ным допускающим состоянием. Возможны четыре случая.

1. Данное выражение имеет вид R + S для некоторых подвыражений R и S. Тогда ему соответствует автомат, представленный на рис. 3.17, а. В этом автомате из нового начального состояния можно перейти в начальное состояние автомата для выраже­ния либо R, либо S. Затем мы попадаем в допускающее состояние одного из этих ав­томатов, следуя по пути, помеченному некоторой цепочкой из языка L(R) или L(S), соответственно. Попав в допускающее состояние автомата для R или S, можно по одному из £-путей перейти в допускающее состояние нового автомата. Следователь­но, язык автомата, представленного на рис. 3.17, а, равен L(R) (J L(S).
2. Выражение имеет вид RS для некоторых подвыражений R и S. Автомат для этой конкатенации представлен на рис. 3.17, б. Отметим, что начальное состояние перво­го автомата становится начальным состоянием для всего автомата, представляющего конкатенацию, а допускающим для него будет допускающее состояние второго ав­томата. Идея состоит в том, что путь, ведущий из начального в допускающее со­стояние, сначала проходит через автомат для R по некоторому пути, помеченному цепочкой из L(R), а потом — через автомат для S по пути, помеченному цепочкой из L(S). Следовательно, путями автомата, представленного на рис. 3.17, б, будут те и только те пути, которые помечены цепочками из языка L(R)L(S>).
3. Выражение имеет вид R* для некоторого подвыражения R. Используем автомат, пред­ставленный на рис. 3.17, е. Этот автомат позволяет пройти по следующим путям:

а)  из начального состояния непосредственно в допускающее по пути, помечен­ному е. Этот путь позволяет допустить цепочку е, которая принадлежит L(R*) независимо от выражения R;

б)  перейти в начальное состояние автомата для R, пройти через этот автомат один или несколько раз, и затем попасть в допускающее состояние. Это множество путей дает возможность допускать цепочки, которые принадле­жат языкам L(R), L(R)L(R), L(R)L(R)L( R) и так далее, порождая таким обра­зом все цепочки из £(/?*), за исключением, возможно, цепочки е. Но она по­лучена в п. 3, а как отметка дуги непосредственно из начального в допус­кающее состояние.

4. Выражение имеет вид (R) для некоторого подвыражения R. Автомат для R мо­жет быть автоматом и для (R), поскольку скобки не влияют на язык, задаваемый выражением.

б)

Рис. 3.17. Индуктивный шаг преобразования регулярного выражения в е-НКА

Легко заметить, что построенные автоматы удовлетворяют всем трем условиям ин­дуктивной гипотезы: одно допускающее состояние, отсутствие дуг, ведущих в начальное состояние, и дуг, выходящих из допускающего состояния. □

Пример 3.8. Преобразуем регулярное выражение (0 + 1)*1(0 + 1) в £-НКА. Постро­им сначала автомат для 0 + 1. Для этого используем два автомата, построенные со­гласно рис. 3.16, в: один с меткой 0 на дуге, другой— с меткой 1. Эти автоматы со­единены с помощью конструкции объединения (см. рис. 3.17, а). Результат изображен на рис. 3.18, а.

Рис. 3.18. Автомат, построенный для примера 3.8

Далее, применим к автомату (см. рис. 3.18, а) конструкцию итерации (см. рис. 3.17, в). Полученный автомат изображен на рис. 3.18, б. На последних двух ша­гах применяется конструкция конкатенации (см. рис. 3.17, б). Сначала автомат, представленный на рис. 3.18, б, соединяется с автоматом, допускающим только це­почку 1. Последний получается путем еще одного применения базисной конструк­ции (см. рис. 3.16, в) с меткой 1 на дуге. Отметим, что для распознавания цепочки 1 необходимо создать новый автомат; здесь нельзя использовать автомат для 1, являю­щийся частью автомата, изображенного на рис. 3.18, а. Третьим автоматом в конкате­нации будет еще один автомат для выражения 0+1. Опять-таки, необходимо создать копию автомата (см. рис. 3.18, а), поскольку нельзя использовать автомат для 0+1, представляющий собой часть автомата (см. рис. 3.18, б).

Полный автомат показан на рис. 3.18, е. Заметим, что если удалить е-переходы, то этот е-НКА будет весьма похож на более простой автомат (см. рис. 3.15), также допус­кающий цепочки с 1 на предпоследней позиции. □

3.2.4. Упражнения к разделу 3.2

3.2.1. ДКА представлен следующей таблицей переходов:

	0	1
~><7i	Яг	<7i
42	<7з	<7i
*<7з	<7з	42

а)  (*) выпишите все регулярные выражения . Замечание. Состояние с/, мож­но рассматривать как состояние с целым номером /;

б)  (*) выпишите все регулярные выражения . Постарайтесь максимально упростить эти выражения;

в)   выпишите все регулярные выражения R⁽²⁾. Постарайтесь максимально упро­стить эти выражения;

г)   напишите регулярное выражение для языка заданного автомата;

д)  (*) постройте диаграмму переходов для этого ДКА и напишите регулярное выражение для его языка, исключив состояние q₂.

3.2.2. Повторите упражнение 3.2.1 для следующего ДКА.

	0	1
~><7i	Яг	<7з
42	<7i	<7з
*<7з	Яг	Я\

Отметим, что решения для пунктов а, 6 и д непригодны в данном упражнении. 3.2.3. Преобразуйте следующий ДКА в регулярное выражение, используя технику ис­ключения состояний из раздела 3.2.2.

	0	1
—> *р	s	Р
ч	р	s
г	г	Ч
s	Я	г

• Преобразуйте следующие регулярные выражения в НКА с £-переходами;

а)   (*) 01*;

б)  (0+ 1)01; в) 00(0+1)*.

• Исключите e-переходы из НКА, полученных вами в упражнении 3.2.4. Решение для пункта а можно найти на Web-страницах этой книги.
• (!) Пусть А = (Q, £, <5, q₀, {<7f}) — это такой £-НКА, в котором нет переходов в состояние q₀ и из состояния с/_{. Опишите язык, допускаемый каждой из следую­щих модификаций автомата А (в терминах языка L = L(A))\

а)   (*) автомат, образованный по А путем добавления ^-перехода из q_{ в д₀;

б)   (*) автомат, построенный по А с помощью добавления е-перехЬда из состоя­ния q₀ в каждое состояние, достижимое из д₀ (по путям, метки которых могут содержать как символы из £, так и е);

в)   автомат, полученный по А посредством добавления ^-перехода в q_f из каждо­го состояния, из которого по какому-либо пути достижимо с/г;

г)   автомат, построенный по А путем одновременного выполнения пунктов бив.

• (!!) Существует несколько упрощений конструкции теоремы 3.7, в которой ре­гулярное выражение преобразовывалось в g-НКА. Вот три из них.
  1. Для оператора объединения вместо создания новых начального и допус­кающего состояний можно сгруппировать оба начальных состояния в одно, сохранив все их переходы. Аналогично, можно сгруппировать оба допус­кающих состояния в одно; к нему ведут все переходы, которые вели к каж­дому из исходных состояний.
  2. Для оператора конкатенации можно объединять допускающее состояние первого автомата с начальным состоянием второго.
  3. Для оператора итерации можно просто добавить ^-переходы из допускающе­го состояния в начальное, и наоборот.

В результате каждого из этих упрощений мы по-прежнему получаем правиль­ную конструкцию, т.е. искомый е-НКА, который для любого регулярного выра­жения допускает язык этого выражения. Сочетание каких усовершенствований (1, 2 или 3) можно применить к этой конструкции, чтобы в результате получался правильный автомат для любого регулярного выражения?

3.2.8. (*!!) Постройте алгоритм, который по данному ДКА А вычисляет количество цепочек длины п, допускаемых ДКА А (п не связано с количеством состояний автомата А). Ваш алгоритм должен быть полиномиальным как относительно п, так и относительно количества состояний А. Указание. Используйте технику, предложенную в доказательстве теоремы 3.4.

3.3. Применение регулярных выражений

Основным средством приложений для поиска образцов (образов, шаблонов) в тексте являются регулярные выражения, задающие «схему» образца, который нужно распо­знать. Регулярные выражения компилируются в детерминированные или недетермини­рованные автоматы, которые затем моделируются для получения программы распозна­вания образов в тексте. В этом разделе мы рассмотрим два важных класса приложений, основанных на регулярных выражениях: лексические анализаторы и поиск в тексте.

3.3.1. Регулярные выражения в UNIX

Прежде чем рассмотреть данные приложения, ознакомимся с системой обозначений, используемой в UNIX для расширенных регулярных выражений. Эти обозначения пре­доставляют много дополнительных возможностей. На самом деле, расширения UNIX включают некоторые особенности, в частности, возможность именовать и ссылаться на предыдущие цепочки, соответствующие шаблону, что, фактически, позволяет распозна­вать нерегулярные языки. Здесь эти особенности не рассматриваются, но вводятся со­кращения, позволяющие записывать сложные регулярные выражения в сжатом виде.

Первое усовершенствование в системе обозначений регулярных выражений связано с тем, что большинство приложений работает с символами в коде ASCII. В наших приме­рах обычно использовался алфавит {0, 1). Наличие только двух символов позволяет ис­пользовать сокращенные выражения вроде 0 + 1 для обозначения «любого символа». Од­нако если алфавит состоит, скажем, из 128 символов, то аналогичное выражение вклю­чало бы список всех этих символов и стало бы весьма неудобным для написания. Таким образом, регулярные выражения в UNIX позволяют задавать классы символов для пред­ставления множеств символов в наиболее кратком виде. Существуют следующие прави­ла для классов символов.

• Символ . (точка) обозначает «любой символ».
• Последовательность [а^-.-а^] обозначает регулярное выражение а_{ + а₂ + … + а_к

Такое обозначение позволяет записывать примерно вдвое меньше символов, по­скольку нет необходимости писать знак «+». Например, четыре символа, исполь­зуемые в операторах сравнения языка С, можно выразить в виде [<>= ! ].

• В квадратных скобках записывается диапазон вида х—у для обозначения всех символов от х до у из последовательности символов в коде ASCII. Поскольку ко­ды цифр, а также символов верхнего и нижнего регистров упорядочены, то мно­гие важные классы символов можно записывать с помощью нескольких ключе­вых цепочек. Например, все цифры могут быть представлены в виде [0-9], символы верхнего регистра могут быть выражены как [A-Z], а множество всех букв и цифр можно записать как [A-Za-z0-9]. Если необходимо включить в такой список символов знак минуса, то его помещают в самом начале или в са­мом конце списка, чтобы не было путаницы с использованием его для обозначе­ния диапазона символов. Например, набор цифр вместе с точкой и знаками плюс и минус, используемый для образования десятичных чисел со знаком, можно за­писать в виде выражения [-+.0-9]. Квадратные скобки и другие символы, имеющие специальные значения в регулярных выражениях UNIX, задаются в ка­честве обычных символов с помощью обратной косой черты (\)перед ними.
• Для некоторых наиболее часто используемых классов символов введены специ­альные обозначения. Рассмотрим несколько примеров:

а)    [: digit: ] обозначает множество из десяти цифр, как и [ 0-9]^[5];

б)    [: alpha: ] обозначает любой символ (латинского) алфавита, как и [ A-Za-z ];

в)    [ :alnum: ] обозначает все цифры и буквы (буквенные и цифровые симво­лы), как и [A-Za-z0-9].

Кроме того, в регулярных выражениях UNIX используется несколько операторов, с которыми мы раньше не сталкивались. Ни один из этих операторов не расширяет мно­жество выражаемых языков, но иногда облегчает выражение того, что нам нужно.

1. Оператор | используется вместо + для обозначения объединения.
2. Оператор ? значит «ни одного или один из». Таким образом, R? в UNIX означает то же, что и £ + R в системе записи регулярных выражений, принятой в этой книге.
3. Оператор + значит «один или несколько из». Следовательно, R+ в UNIX является со­кращением для RR* в наших обозначениях.
4. Оператор {п} обозначает «и копий». Таким образом, R{5} в UNIX является сокра­щенной записью для RRRRR в наших обозначениях.

Отметим, что в регулярных выражениях UNIX для группирования подвыражений ис­пользуются скобки, как и в регулярных выражениях из раздела 3.1.2, и тот же порядок при­оритетов операторов (в этом смысле ?, + и {п} трактуются как *). Оператор * используется в UNIX (конечно же, не как верхний индекс) в рассмотренном выше значении.

3.3.2. Лексический анализ

Одним из наиболее ранних применений регулярных выражений было использование их для спецификации компонента компилятора, называемого «лексическим анализато­ром». Этот компонент сканирует исходную программу и распознает все лексемы, т.е. подцепочки последовательных символов, логически составляющие единое целое. Ти­пичными примерами лексем являются ключевые слова и идентификаторы, но существует и множество других примеров.

Полное описание регулярных выражений в UNIX

Читатель, желающий ознакомиться с полным списком операторов и сокращений, используемых в системе записи регулярных выражений в UNIX, может найти их на учебных страницах для различных команд. Существуют некоторые различия между версиями UNIX, но команда типа man grep выдаст вам обозначения, ис­пользуемые для команды grep, которая является основной. Кстати, «grep» озна­чает «Global (search for) Regular Expression and Print» (Глобальный поиск регуляр­ного выражения и печать).

UNIX-команда lex и ее GNU-версия flex получают на вход список регулярных выражений в стиле UNIX, за каждым из которых в фигурных скобках следует код, ука­зывающий, что должен делать лексический анализатор, если найдет экземпляр этой лексемы. Такая система называется генератором лексического анализатора, посколь­ку на ее вход поступает высокоуровневое описание лексического анализатора и по этому описанию она создает функцию, которая представляет собой работающий лек­сический анализатор.

Такие команды, как lex и flex, оказались очень удобными, поскольку мощность нотации регулярных выражений необходима и достаточна для описания лексем. Эти ко­манды способны использовать процедуру преобразования регулярного выражения в ДКА для того, чтобы генерировать эффективную функцию, разбивающую исходную программу на лексемы. Они превращают задачу построения лексического анализатора в «послеобеденную работу», тогда как до создания этих основанных на регулярных выра­жениях средств построение лексического анализатора вручную могло занимать несколь­ко месяцев. Кроме того, если по какой-либо причине возникает необходимость модифи­цировать лексический анализатор, то намного проще изменить одно или два регулярных выражения, чем забираться внутрь загадочного кода, чтобы исправить дефект.

Пример 3.9. На рис. 3.19 приведен пример фрагмента входных данных команды lex, описывающих некоторые лексемы языка С. В первой строке обрабатывается ключевое слово else, и ее действие заключается в возвращении символьной константы (в данном примере это ELSE) в программу синтаксического анализа для дальнейшей обработки. Вторая строка содержит регулярное выражение, описывающее идентификаторы: буква, за которой следует нуль или несколько букв и/или цифр. Ее действие заключается в сле­дующем. Сначала идентификатор заносится в таблицу символов (если его там еще нет). Затем lex выделяет найденную лексему в буфере, так что в этой части кода известно, какой именно идентификатор был обнаружен. Наконец, лексический анализатор возвра­щает символьную константу ID, с помощью которой в этом примере обозначаются идентификаторы.

Третий вход на рис. 3.19 предназначен для знака >=, который является двухсимволь- ным оператором. В последнем показанном примере обрабатывается односимвольный оператор =. На практике используют выражения, описывающие ключевые слова, знаки и такие символы пунктуации, как запятые или скобки, а также семейства констант, напри­мер, числа или цепочки. Многие из этих выражений чрезвычайно просты — это после­довательности, состоящие из одного или нескольких определенных символов. Однако для некоторых выражений требуется вся мощь нотации регулярных выражений. Другими примерами успешного применения возможностей регулярных выражений в командах типа lex служат целые числа, числа с плавающей точкой, символьные цепочки и ком­ментарии. □

else                       {возвращает (ELSE);}

[A-Za-z][A-Za-zO-9]* {код для ввода найденного идентификатора

в таблицу символов;

возвращает (ID); }

>=                         {возвращает (GE);}

=                          {возвращает (EQ);}

Рис. 3.19. Пример входных данных команды lex

Преобразование набора выражений, подобных представленным на рис. 3.19, в авто­мат происходит почти так же, как это было формально описано в предыдущих разделах. Сначала строится автомат для объединения всех этих выражений. Вообще говоря, этот автомат свидетельствует лишь о том, что распознана какая-то лексема. Однако если учесть конструкцию теоремы 3.7 для объединения выражений, состояние е-НКА точно указывает, к какому типу принадлежит распознанная лексема.

Единственная проблема заключается в том, что лексема может одновременно иметь сразу несколько типов; например, цепочка else соответствует не только регулярному выражению else, но и выражению для идентификаторов. В генераторе лексического ана­лизатора применяется следующее стандартное решение: приоритет отдается выражению, находящемуся в списке первым. Таким образом, если необходимо, чтобы ключевые сло­ва типа else были зарезервированными (т.е. не использовались в качестве идентифика­торов), то они просто перечисляются в списке перед выражением для идентификаторов.

3.3.3. Поиск образцов в тексте

В разделе 2.4.1 мы отметили, что автоматы могут применяться для эффективного по­иска наборов определенных слов в таких больших хранилищах данных, как Web. Хотя инструментальные средства и технология для этого пока не настолько хорошо развиты, как для лексических анализаторов, регулярные выражения все же очень полезны для описания процедур поиска желаемых образцов. Как и для лексических анализаторов, возможность перехода от естественного, описательного представления в виде регуляр­ных выражений к эффективной (основанной на автоматах) реализации является важным интеллектуальным средством решения поставленной задачи.

Общая проблема, для решения которой технология регулярных выражений оказалась весьма полезной, заключается в описании нечетко определенного класса образцов в тек­сте. Нечеткость описания, в сущности, является гарантией того, что с самого начала нет нужды корректно и полно описывать образцы. Не исключено, что мы никогда не сможем получить точное и полное описание. С помощью регулярных выражений можно, не при­лагая больших усилий, описывать такие образцы и быстро изменять эти описания, если результат нас не устраивает. Кроме того, «компилятор» для регулярных выражений при­годен и для преобразования записываемых выражений в выполнимый код.

В качестве примера обсудим одну типичную проблему, возникающую во многих Web- приложениях. Предположим, необходимо просмотреть огромное количество Web-страниц и отметить адреса. Возможно, мы хотим составить список электронных адресов. Или пыта­емся классифицировать фирмы по их месторасположению, чтобы отвечать на запросы типа «найдите мне ресторан в пределах 10-ти минут езды от того места, где я сейчас нахожусь».

В частности, мы сосредоточим внимание на распознавании названий улиц. Что такое название улицы? Необходимо это выяснить, и, если во время тестирования программы будет установлено, что пропущены какие-то варианты, то нужно будет изменять выра­жения таким образом, чтобы включить все, что не было учтено. Начнем с того, что на­звание улицы может заканчиваться словом «Street» (улица) или его сокращением «St.» Однако некоторые люди живут на «Avenues» (проспектах) или «Roads» (шоссе), что тоже может быть записано в сокращенном виде. Таким образом, в качестве окончания нашего выражения можно использовать следующие варианты. Street | St\. I Avenue | Ave\. |Road | Rd\.

В этом выражении использованы обозначения в стиле UNIX с вертикальной чертой вместо + для оператора объединения. Обратите также внимание, что перед точками сто­ит обратная косая черта, поскольку в выражениях UNIX точка имеет специальное значе­ние— «любой символ», а в этом случае нам необходимо, чтобы в конце сокращений стоял символ «точка».

Перед таким обозначением, как Street, должно стоять название улицы. Обычно оно состоит из прописной буквы, за которой следует несколько строчных букв. В UNIX этот образец можно описать с помощью выражения [A-Z] [a-z] *. Однако названия некото­рых улиц состоят из нескольких слов, например, «Rhode Island Avenue in Washington DC». Поэтому, обнаружив, что названия такого вида пропущены, необходимо исправить наше описание таким образом, чтобы получилось следующее выражение. ‘ [A-Z] [a-z]* ( [A-Z] [a-z]*)*’

Это выражение начинается с группы, состоящей из прописной буквы и, возможно, нескольких строчных букв. Далее может следовать несколько групп, состоящих из пробела, еще одной прописной буквы и, возможно, нескольких строчных. В выраже­ниях UNIX пробел является обычным символом, и, чтобы представленное выше вы­ражение не выглядело в командной строке UNIX как два выражения, разделенных пробелом, нужно все выражение заключить в апострофы. Сами апострофы не являют­ся частью выражения.

Теперь в адрес нужно включить номер дома. Большинство номеров домов представ­ляют собой цепочки из цифр. Однако в некоторых номерах после цифр стоит буква, на­пример, «123А Main St.» Поэтому выражение для номеров должно включать необяза­тельную прописную букву после цифр: [ 0-9] + [A-Z] ?. Заметьте, что мы здесь исполь­зовали UNIX-оператор + для «одной или нескольких» цифр и оператор ? для «ни одной или одной» прописной буквы. Полное выражение для адресов улиц будет иметь следую­щий вид.

‘ [0-9] + [A-Z]? [A-Z] [a-z] *( [A-Z] [a-z]*)* (Street ISt\. |Avenue IAve\. |Road|Rd\.) ‘

Используя это выражение, получим вполне приемлемый результат. Однако в какой-то момент мы обнаружим, что пропустили следующие случаи.

1. Улицы, которые называются иначе, чем «street», «avenue» или «road». Например, мы упустили «Boulevard» (бульвар), «Place» (площадь), «Way» (дорога) и их сокращения.
2. Названия улиц, которые являются числами или частично содержат числа, например, «42nd Street» (42-я улица).
3. Почтовые ящики и маршруты сельской доставки.
4. Названия улиц, которые не оканчиваются словом типа «Street». Например, «Е1 Camino Real in Silicon Valley». С испанского это переводится как «Королевское шос­се в Силиконовой Долине», но если сказать «El Camino Real Road» («Королевское

шоссе шоссе»), то это будет повторением. Так что приходится иметь дело с адреса­ми типа «2000 El Camino Real». 5. Все другие странные ситуации, которые мы даже не можем вообразить. А вы можете?

Таким образом, с помощью компилятора регулярных выражений процесс постепен­ного приближения к полному распознавателю адресов существенно упрощается по срав­нению с использованием традиционного языка программирования.

3.3.4. Упражнения к разделу 3.3

• (!) Напишите регулярное выражение для описания телефонных номеров всех видов, которые только можно себе представить. Учтите международные номера, а также тот факт, что в разных странах используется разное количество цифр в кодах областей и в локальных номерах телефонов.
• (!!) Напишите регулярное выражение для представления заработной платы в том виде, в котором она указывается в объявлениях о работе. Учтите, что может быть указан размер зарплаты в час, в неделю, месяц или год. Она может вклю­чать или не включать знак доллара или какой-либо другой единицы, например «К». Рядом может находиться слово или слова, обозначающие, что речь идет о зарплате. Предложение: просмотрите рекламные объявления в газетах или спи­ски вакансий в режиме on-line, чтобы получить представление о том, какие об­разцы могут вам пригодиться.
• (!) В конце раздела 3.3.3 мы привели несколько примеров изменений, которые могут быть внесены в регулярное выражение, описывающее адреса. Модифици­руйте построенное там выражение таким образом, чтобы включить все упомя­нутые варианты.

3.4. Алгебраические законы для регулярных выражений

В примере 3.5 мы столкнулись с необходимостью упрощения регулярных выражений для того, чтобы их размер не превышал разумные пределы. Мы объяснили, почему одно выражение можно было заменить другим. Во всех рассмотренных ситуациях основной вывод заключался в том, что эти выражения оказывались эквивалентными, т.е. задавали один и тот же язык. В этом разделе будет предложен ряд алгебраических законов, позво­ляющих рассматривать вопрос эквивалентности двух регулярных выражений на более высоком уровне. Вместо исследования определенных регулярных выражений, мы рас­смотрим пары регулярных выражений с переменными в качестве аргументов. Два выра­жения с переменными являются эквивалентными, если при подстановке любых языков вместо переменных оба выражения представляют один и тот же язык.

Рассмотрим подобный пример в алгебре обычной арифметики. Одно дело сказать, что 1+2 = 2+1. Данный частный случай закона коммутативности операции сложения легко проверить: выполнив операцию сложения в обеих частях этого равенства, получим 3 = 3. Однако коммутативный закон сложения утверждает большее, а именно, что х+у = у + х, где х и у — переменные, которые можно заменять любыми двумя числами. Сле­довательно, он гласит, что, какие бы числа мы ни складывали, получим один и тот же ре­зультат независимо от порядка суммирования.

Регулярные выражения, подобно обычным арифметическим, подчиняются ряду зако­нов. Многие из них подобны законам арифметики, если рассматривать объединение как сложение, а конкатенацию — как умножение. Однако в некоторых случаях эта аналогия нарушается. Кроме того, существует ряд законов для регулярных выражений, которым в арифметике аналогов нет, особенно если речь идет об операторе итерации. Следующие разделы содержат перечень главных законов для регулярных выражений. В завершение обсуждается вопрос, как вообще можно проверить, является ли некоторый формулируе­мый для регулярных выражений закон на самом деле законом, т.е. выполняется ли он для любых языков, подставляемых вместо его переменных.

3.4.1. Ассоциативность и коммутативность

Коммутативность— это свойство операции, заключающееся в том, что при пере­становке ее операндов результат не меняется. Арифметический пример мы уже приводи­ли выше: х + у = у + х. Ассоциативность— это свойство операции, позволяющее пере­группировывать операнды, если оператор применяется дважды. Например, ассоциатив­ный закон умножения имеет вид: (xxy)xz = xx(yxz). Для регулярных выражений выполняются три закона такого типа.

• L + М= M+L, т.е. коммутативный закон для объединения утверждает, что два языка можно объединять в любом порядке.
• (L + М) + N = L + (М + N). Этот закон— ассоциативный закон объединения — говорит, что для объединения трех языков можно сначала объединить как два первых, так и два последних из них. Обратите внимание на то, что вместе с ком­мутативным законом объединения этот закон позволяет объединять любое коли­чество языков в произвольном порядке, разбивая их на любые группы, и резуль­тат будет одним и тем же. Очевидно, что некоторая цепочка принадлежит объе­динению L\ U L₂ U … U L_k тогда и только тогда, когда она принадлежит одному или нескольким языкам L_v
• (LM)N — L(MN). Этот ассоциативный закон конкатенации гласит, что для конка­тенации трех языков можно сначала соединить как два первых, так и два послед­них из них.

В предложенном списке нет «закона» LM=ML, гласящего, что операция конкатена­ции является коммутативной, поскольку это утверждение неверно.

Пример 3.10. Рассмотрим регулярные выражения 01 и 10. Эти выражения задают языки {01} и {10}, соответственно. Поскольку эти языки различаются, то общий закон LM=ML для них не выполняется. Если бы он выполнялся, то можно было бы подставить регулярное выражение 0 вместо L и 1 вместо Ми получить неверное заключение 01 = 10. □

• Единичные и нулевые элементы

Единичным (нейтральным) элементом (единицей) операции называется элемент, для которого верно следующее утверждение: если данная операция применяется к единич­ному элементу и некоторому другому элементу, то результат равен другому элементу. Например, 0 является единичным элементом операции сложения, поскольку 0 + х = л: + 0 = х, а 1 — единичным элементом для умножения, потому что 1 х х = х х 1 = х. Нуле­вым элементом (нулем, аннулятором) операции называется элемент, для которого ис­тинно следующее: результатом применения данной операции к нулевому и любому дру­гому элементу является нулевой элемент. Например, 0 является нулевым элементом ум­ножения, поскольку 0хх = хх0 = 0. Операция сложения нулевого элемента не имеет.

Для регулярных выражений существует три закона, связанных с этими понятиями.

• 0 + L = L + 0 = L. Этот закон утверждает, что 0 является единицей объединения.
• eL = Le = L. Этот закон гласит, что е является единицей конкатенации.
• 0L = L0 = 0. Этот закон утверждает, что 0 является нулевым элементом конка­тенации.

Эти законы являются мощным средством упрощения выражений. Например, если не­обходимо объединить несколько выражений, часть которых упрощена до 0, то 0 можно исключить из объединения. Аналогично, если при конкатенации нескольких выражений некоторые из них можно упростить до е, то е можно исключить из конкатенации. Нако­нец, если при конкатенации любого количества выражений хотя бы одно из них равно 0, то результат такой конкатенации — 0.

• Дистрибутивные законы

Дистрибутивный закон связывает две операции и утверждает, что одну из операций можно применить отдельно к каждому аргументу другой операции. Арифметическим примером этого закона является дистрибутивный закон умножения относительно сложе­ния, т.е. xx(y + z) = xxy+x~xz. Поскольку умножение коммутативно, то не имеет зна­чения, с какой стороны, слева или справа от суммы, применяется умножение. Для регу­лярных выражений существует аналогичный закон, но, поскольку операция конкатена­ции некоммутативна, то мы сформулируем его в виде следующих двух законов.

• L(M + N) = LM + LN.Этот закон называется левосторонним дистрибутивным за­коном конкатенации относительно объединения.
• (М + N)L= ML+ NL.Этот закон называется правосторонним дистрибутивным законом конкатенации относительно объединения.

Докажем левосторонний дистрибутивный закон. Правосторонний доказывается ана­логично. В доказательстве используются только языки, и оно не зависит от того, сущест­вуют ли для этих языков регулярные выражения.

Теорема 3.11. Если L, MnN— произвольные языки, то

L(M(J N) = LM\J LN

Доказательство. Это доказательство аналогично доказательству дистрибутивного закона, представленного в теореме 1.10. Требуется показать, что цепочка w принадлежит ДА/U N) тогда и только тогда, когда она принадлежит LM U LN.

(Необходимость) Если w принадлежит L(M U N), то w = xy, где х принадлежит L, а у принадлежит либо М, либо N. Если у принадлежит М, то ху принадлежит LM и, следова­тельно, принадлежит LM\JLN. Аналогично, если у принадлежит N, то ху принадлежит LN и, следовательно, принадлежит LM U LN.

(Достаточность) Предположим, что w принадлежит LM (J LN. Тогда w принадлежит либо LM, либо LN. Пусть и> принадлежит LM. Тогда и> = ху, где х принадлежит L, ay при­надлежит М. Если у принадлежит М, то у также содержится в A/U N. Следовательно, ху принадлежит L(M\JN). Если w не принадлежит LM, то она точно содержится в LN, и аналогичные рассуждения показывают, что w принадлежит L(M[j N). □

Пример 3.12. Рассмотрим регулярное выражение 0 + 01 . В объединении можно «вынести за скобки 0», но сначала необходимо представить выражение 0 в виде конкате­нации 0 с чем-то еще, а именно с е. Используем свойства единичного элемента для кон­катенации, меняя 0 на Ое, в результате чего получим выражение 0е + 01*. Теперь можно применить левосторонний дистрибутивный закон, чтобы заменить это выражение на 0(е+ 1*). Далее, учитывая, что е принадлежит L(l’), заметим, что е+ 1* = 1*, и оконча­тельно упростим выражение до 01*. □

3.4.4. Закон идемпотентности

Операция называется идемпотентной, если результат применения этой операции к двум одинаковым значениям как операндам равен этому значению. Обычные арифмети­ческие операции не являются идемпотентными. В общем случаех+х*хяхх.х*х (хотя существуют некоторые значения х, для которых это равенство выполняется, например 0 + 0 = 0). Однако объединение и пересечение являются идемпотентными операциями, поэтому для регулярных выражений справедлив следующий закон.

• L+ L = L. Этот закон — закон идемпотентности операции объединения — ут­верждает, что объединение двух одинаковых выражений можно заменить одним таким выражением.
• Законы, связанные с оператором итерации

Существует ряд законов, связанных с операцией итерации и ее разновидностями + и ? в стиле UNIX. Перечислим эти законы и вкратце поясним, почему они справедливы.

• (L*)* = L*. Этот закон утверждает, что при повторной итерации язык уже итериро­ванного выражения не меняется. Язык выражения (Z,*)* содержит все цепочки, образованные конкатенацией цепочек языка L*. Последние же цепочки построе­ны из цепочек языка L. Таким образом, цепочки языка (X*)* также являются кон- катенациями цепочек из L и, следовательно, принадлежат языку L*.
• 0* = е. Итерация языка 0 состоит из одной-единственной цепочки е, что уже об­суждалось в примере 3.6.
• е* = е. Легко проверить, что единственной цепочкой, которую можно образовать конкатенацией любого количества пустых цепочек, будет все та же пустая цепочка.
• L⁺ = LL* = L*L. Напомним, что V по определению равно L+ LL + LLL + …. По­скольку L* = е + L + LL + LLL + …, то

LL* = Le + LL + LLL + LLLL + …

Если учесть, что Le = L, то очевидно, что бесконечные разложения для LL* и для V совпадают. Это доказывает, что V = LL’. Доказательство того, что L* = L*L, аналогично^[6].

• L* = L⁺ + е. Это легко доказать, поскольку в разложении L+ присутствуют те же члены, что и в разложении Z,*, за исключением цепочки е. Заметим, что если язык L содержит цепочку е, то слагаемое «+е» лишнее, т.е. в этом случае V = V.
• Ll = е + L. В действительности это правило является определением оператора «?».
• Установление законов для регулярных выражений

Каждый из вышеперечисленных законов был доказан, формально или неформально. Однако есть еще бесконечно много законов для регулярных выражений, которые можно было бы сформулировать. Существует ли некая общая методика, с помощью которой можно было бы легко доказывать истинность таких законов? Оказывается, что вопрос о справедливости некоторого закона сводится к вопросу о равенстве двух определенных языков. Интересно, что эта методика тесно связана с регулярными операциями и не мо­жет быть распространена на выражения, использующие некоторые другие операции, на­пример пересечение.

Чтобы проиллюстрировать суть этой методики, рассмотрим следующий закон.

(L + М) = (См*)»

Этот закон утверждает, что в результате итерации объединения двух произвольных язы­ков получим тот же язык, что и в результате итерации языка L*Af’, состоящего из всех цепочек, образованных из нуля или нескольких цепочек из L, за которыми следует нуль или несколько цепочек из М.

Чтобы доказать этот закон, сначала предположим, что цепочка w принадлежит языку выражения (L + M)*^[7]. Тогда vv = vv₁vv₂…vv_k для некоторого к, где каждая цепочка vv, при­надлежит либо L, либо М. Из этого следует, что каждая такая цепочка vv; принадлежит языку L*M*. Действительно, если цепочка vv, принадлежит языку L, то она также принад­лежит языку L . Тогда из М не берем ни одной цепочки, т.е. из М выбираем е. Если w* принадлежит м, доказательство аналогично. Если каждая >v, принадлежит L’a/, то w принадлежит итерации этого языка.

Чтобы завершить доказательство, необходимо доказать обратное утверждение, т.е. что все цепочки из (/,*Л/)* принадлежат также (L + М) . Опустим эту часть доказательст­ва, поскольку нашей целью является не доказательство данного закона, а установление следующего важнейшего свойства регулярных выражений.

Любое регулярное выражение с переменными можно рассматривать как конкретное регулярное выражение, не содержащее переменных, если считать, что каждая перемен­ная — это просто отдельный символ. Например, в выражении (L + М) переменные L и М можно заменить символами а и Ь, соответственно, и получить регулярное выражение (а + Ь)*.

Язык конкретного выражения дает представление о виде цепочек любого языка, об­разованного из исходного выражения в результате подстановки произвольных языков вместо переменных. Например, при анализе выражения (L + М) мы отметили, что любая цепочка w, составленная из последовательности цепочек, выбираемых либо из L, либо из М, принадлежит языку (L + М) . Можно прийти к тому же заключению, рассмотрев язык конкретного выражения L((а + Ь)*), который, очевидно, представляет собой множество всех цепочек, состоящих из символов а и Ь. В одну из цепочек этого множества можно подставить любую цепочку из L вместо символа а и любую цепочку из М вместо символа Ь. При этом различные вхождения символов а и b можно заменять различными цепочка­ми. Если такую подстановку осуществить для всех цепочек из (а + Ь)*, то в результате получим множество всех цепочек, образованных конкатенацией цепочек из L и/или М в любом порядке.

Сформулированное выше утверждение может показаться очевидным, но, как указано во врезке «Расширение данной проверки за пределы регулярных выражений может ока­заться ошибочным», оно будет неверным, если к трем операциям регулярных выражений добавить некоторые другие операции. В следующей теореме доказывается общий закон для регулярных выражений.

Теорема 3.13. Пусть Е— регулярное выражение с переменными L_x, Ь₂, …, L_m. По­строим конкретное регулярное выражение С, заменив каждое вхождение L, символом а„ i= 1, 2, …, т. Тогда для произвольных языков L_u L₂, …, L_m любую цепочку w из L(E) можно представить в виде w = w_xw₂…wк, где каждая принадлежит одному из этих язы­ков, например а цепочка a_|la_J2…a_|k принадлежит языку ЦС). Говоря менее формально, мы можем построить ЦЕ), исходя из каждой цепочки языка ЦС), скажем, a_jXa_sl…a^, и заменяя в ней каждый из символов a_si любой цепочкой из соответствующего языка Ц.

Доказательство. Доказательство проведем структурной индукцией по выражению Е.

Базис. Базисными являются случаи, когда Е представляет собой е, 0 или переменную L. В первых двух случаях нечего доказывать, потому что конкретное выражение С сов­падает с Е. Если же Е есть переменная L, то ЦЕ) = L. Конкретное выражение С равно просто а, где а— символ, соответствующий переменной L. Следовательно, ЦС) = {а}. Если в эту единственную цепочку вместо символа а подставить любую цепочку из L, то получим язык L, который есть также ЦЕ).

Индукция. Рассмотрим три случая в зависимости от заключительной операции вы­ражения Е. Сначала предположим, что Е =F + G, т.е. заключительной является операция объединения. Пусть С и D — конкретные выражения, построенные соответственно по F и G с помощью подстановки в эти выражения определенных символов вместо языковых переменных. Заметим, что в оба выражения F и G вместо всех одинаковых переменных должны быть подставлены одинаковые символы. Тогда конкретное выражение, полу­ченное из выражения Е, равно С + D, и ЦС + D) = L(C) + L(D).

Предположим, что w — цепочка из языка ЦЕ), полученная в результате замены язы­ковых переменных выражения Е некоторыми определенными языками. Тогда w принад­лежит либо L(F), либо L(G). Согласно индуктивной гипотезе цепочка w получена, исходя из некоторой конкретной цепочки w_x, принадлежащей ЦС) или L(D), соответственно, с помощью подстановки цепочек из соответствующих языков вместо символов цепочки W], Таким образом, в обоих случаях цепочка w может быть построена, начиная с некото­рой конкретной цепочки Wi из L(C + D), путем одних и тех же подстановок цепочек вме­сто символов.

Необходимо также рассмотреть случаи, когда Е представляет собой FG или F’. Одна­ко доказательства для конкатенации и итерации аналогичны приведенному выше доказа­тельству для объединения, поэтому оставляем их читателю. □

3.4.7. Проверка истинности алгебраических законов для регулярных выражений

Теперь можно сформулировать и обосновать проверку истинности законов для регу­лярных выражений. Проверка истинности закона Е = F, где Е и F— два регулярных вы­ражения с одним и тем же набором переменных, состоит в следующем.

1. Преобразуем Е и F в конкретные регулярные выражения С и D соответственно, за­меняя каждую переменную конкретным символом.
2. Проверим равенство L(C) = L(D). Если оно выполняется, то закон Е = F истинен, а если нет — ложен. Заметим, что проверять, определяют ли два регулярных выражения один и тот же язык, мы научимся в разделе 4.4. Однако можно использовать некоторые спе­циальные (ad-hoc) средства для проверки равенства пар интересующих нас языков. На­помним, что если языки не совпадают, то достаточно построить контрпример, т.е. най­ти хотя бы одну цепочку, принадлежащую только одному из них.

Теорема 3.14. Предложенная выше проверка правильно определяет истинность зако­нов для регулярных выражений.

Доказательство. Докажем, что L(E) = L(F) для любых языков, подставленных вместо переменных Е иЕ, тогда и только тогда, когда L(C) = L(D).

(Необходимость) Предположим, что L(E) = L(F) для любых языков, подставляемых вместо переменных. В частности, выберем для каждой переменной L конкретный символ а, заменяющий L в выражениях С и D. Тогда L(C) = L(E) и L(D) = L(F). Поскольку мы предположили, что L(E) = L(F), то L(C) = L(D).

(Достаточность) Теперь предположим, что L(C) = L(D). Согласно теореме 3.13 Ь(Е) и L(F) построены с помощью замены конкретных символов в цепочках из L(C) и L(D) цепочками из языков, соответствующих этим символам. Если L(C) и L(D) состоят из од­них и тех же цепочек, то оба языка, построенные таким способом, тоже будут совпадать; т.е. L(E) = L(F). □

Пример 3.15. Проанализируем предполагаемый закон (L + М) = (Z*M*)*. Если заме­нить переменные L и М, соответственно, конкретными символами а и Ь, получим регу­лярные выражения (а + Ь)* и (а*Ь*)\ Легко убедиться в том, что оба эти выражения за­дают язык всех возможных цепочек, составленных из а и Ь. Следовательно, оба конкрет­ных выражения представляют один и тот же язык, и данный закон выполняется.

В качестве еще одного примера рассмотрим закон L* = L*J*. Конкретными языками будут а* и а*а*, соответственно, и каждый из них представляет собой множество всех це­почек, состоящих из а. Снова видим, что данный закон выполняется, т.е. конкатенация итераций одного и того же языка дает ту же самую итерацию.

Наконец, рассмотрим предполагаемый закон L + ML = (L + M)L. Если заменить сим­волами а и Ь переменные L и М, соответственно, то получим два конкретных выражения а + Ьа и (а + Ь)а. Однако языки этих выражений не совпадают. Например, цепочка аа

принадлежит второму языку, но не принадлежит первому. Следовательно, этот предпо­лагаемый закон ложен. □

Расширение данной проверки за пределы регулярных выражений может оказаться ошибочным

Рассмотрим расширенную алгебру регулярных выражений, включающую операцию пересечения. Интересно, что добавление операции П к трем представленным ранее операциям регулярных выражений не увеличивает множество задаваемых языков, что будет доказано ниже в теореме 4.8. В то же время сформулированная выше проверка алгебраических законов перестает работать.

Рассмотрим «закон» L П А/Г)N = Lf]M, утверждающий, что пересечение некоторых трех языков равно пересечению только двух первых из них. Очевидно, что этот закон ложен. Например, если L = М= {а}, а N = 0. Но проверка, основанная на конкретиза­ции переменных, может не определить ложность этого закона. Если мы заменим L, М и N символами a, b и с, соответственно, то должны будем проверить равенство {а} П {6} П {с} = {а} П {Ь}- Поскольку обе части этого соотношения являются пус­тым множеством, равенство языков выполняется, и согласно нашей проверке этот «закон» будет истинным, хотя в действительности это не так.

3.4.8. Упражнения к разделу 3.4

• Проверьте следующие тождества для регулярных выражений:

а)   (*)R + S = S+R;

б)   (R + S) + Т= R + (S + Т);

в)   (RS)T= R(ST)~,

г)   R(S+ T) = RS + RT;

д)   (R + S)T= RT+ST-,

е)   (*)(Л*)* = Л*;

ж)  (е + R)* = R*;

з)   (R’sy = (R + S)\

• (!) Докажите или опровергните каждое из следующих утверждений для регуляр­ных выражений:

а)   (*) (R + S)* = R* + Sf;

б)   (RS + R)’R = R(SR + /?)*;

в)   (*)(RS +R)*RS =(/Уг^,5)*;

г)    (R+S)*S=(R’S)*;

д) S(RS + S)’R = RR’S(RR’S)’.

• В примере 3.6 было построено регулярное выражение (О + 1)*1(0 + 1) + (0 + 1)*1(0 + 1)(0 + 1).

С помощью дистрибутивных законов преобразуйте его в два различных, более простых, эквивалентных выражения.

• В начале раздела 3.4.6 приведена часть доказательства того, что (L*м’)’ = (L + М) . Завершите это доказательство, показав, что все цепочки из (£*Л/)* принадлежат также (L + М) .
• (!) Завершите доказательство теоремы 3.13 для случаев, когда регулярное выра­жение Е представляет собой FG или F*.

Резюме

• Регулярные выраженш. Этот алгебраический способ описания задает те же языки, что и конечные автоматы, а именно, регулярные языки. Регулярными операторами являются объединение, конкатенация («точка») и итерация («звездочка»).
• Регулярные выраженш на практике. Системы, подобные UNIX, и различные их команды используют язык расширенных регулярных выражений, существенно уп­рощающий записи многих обычных выражений. Классы символов позволяют лег­ко записывать выражения для наборов символов, а такие операторы, как «один или несколько из» и «не более, чем один из», расширяют круг обычных регуляр­ных операторов.
• Эквивалентность регулярных выражений и конечных автоматов. Произвольный ДКА можно преобразовать в регулярное выражение с помощью индуктивной про­цедуры, в которой последовательно строятся выражения для меток путей, прохо­дящих через постепенно увеличивающиеся множества состояний. В качестве аль­тернативы преобразованию ДКА в регулярное выражение можно также использо­вать метод исключения состояний. С другой стороны, мы можем рекурсивно построить е-НКА по регулярному выражению, а потом в случае необходимости преобразовать полученный е-НКА в ДКА.
• Алгебра регулярных выражений. Регулярные выражения подчиняются многим ал­гебраическим законам арифметики, хотя есть и различия. Объединение и конкате­нация ассоциативны, но только объединение коммутативно. Конкатенация дист­рибутивна относительно объединения. Объединение идемпотентно.
• Проверка истинности алгебраических тождеств. Чтобы проверить эквивалент­ность регулярных выражений с переменными в качестве аргументов, необходимо подставить вместо этих переменных различные константы и проверить, будут ли совпадать языки, полученные в результате.

Литература

Идея регулярных выражений и доказательство их эквивалентности конечным автома­там представлены в работе Клини [3]. Преобразование регулярного выражения в £-НКА в том виде, как оно выглядит в этой книге, известно как «Метод Мак-Нотона-Ямады» из работы [4]. Проверку тождеств регулярных выражений, в которой переменные рассмат­риваются как константы, предложил Дж. Гишер [2]. В его отчете, который считается устным, продемонстрировано, как добавление нескольких других операций, например, пересечения или перемешивания (см. упражнение 7.3.4), приводит к ошибочности дан­ной проверки, хотя класс задаваемых языком при этом не изменяется.

Еще до появления системы UNIX К. Томпсон исследовал возможность применения регулярных выражений в таких командах, как grep, и придуманный им алгоритм вы­полнения таких команд можно найти в [5]. На ранней стадии развития UNIX появились другие команды, в которых активно использовались расширенные регулярные выраже­ния, например, команда lex, предложенная М. Леском. Описание этой команды и дру­гих технологий, связанных с регулярными выражениями, можно найти в [1].

1. А. V. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, Ad­dison-Wesley, Reading MA, (Ахо А. В., Сети P., Ульман Дж. Компиляторы: принципы, технологии и инструменты. — М.: Издательский дом «Вильяме», 2001.)
2. L. Gisher, STAN-CS-TR-84-1033 (1984).
3. С. Kleene, «Representation of events in nerve nets and finite automata», In С. E. Shannon and J. McCarthy, Automata Studies, Princeton Univ. Press, 1956, pp. 3-42. (Клини С.К. Представление событий в нервных сетях. / сб. «Автоматы». — М.: ИЛ, 1956, — С. 15-67.)
4. McNaughton and Н. Yamada, «Regular expressions and state graphs for automata», IEEE Trans. Electronic Computers 9:1 (Jan., 1960), pp. 39-47.
5. Thompson, «Regular expression search algorithm», Comm. ACM 11:6 (June, 1968), pp. 419-422.

^[1] Будем употреблять также термины «регулярные операции» и «регулярные операторы», при­нятые в русскоязычной литературе. — Прим. ред.

^[2] Термин «замыкание Клини» связан с именем С. К. Клини, который ввел понятие регулярного

выражения и, в частности, эту операцию.

^[4] В UNIX точка в регулярных выражениях используется для совершенно другой цели — пред­ставления любого знака кода ASCII.

^[5] Преимущество обозначения [: digit: ] состоит в том, что если вместо кода ASCII исполь­зуется другой, в котором коды цифр расположены не по порядку, то [: digi t: ] все так же будет обозначать [0123456789], тогда как [0-9] будет представлять все символы, коды которых на­ходятся в промежутке между кодами для 0 и для 9 включительно.

^[6] Как следствие, отметим, что любой язык коммутирует со своей итерацией: LZ,* = Ь’Ь. Это свой­ство не противоречит тому, что в общем случае конкатенация не является коммутативной.

^[7] Для простоты отождествим регулярные выражения с их языками, чтобы не повторять фразу «язык выражения» перед каждым регулярным выражением.