Регулярные выражения и языки (стр. 2 )

Строго говоря, регулярное выражение Е— это просто выражение, а не язык. Мы ис­пользуем 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). Для операторов регулярных выражений определен следующий порядок приоритетов.

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

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

Пример 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. Конечные автоматы и регулярные выражения

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

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

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

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

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

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

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