Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 24
Текст из файла (страница 24)
Однако мы избегаем использовать точку в качестве оператора конкатенации в регулярных выражениях . 3. Если Š— регулярное выражение, то Š— регулярное выражение, определяющее итерацию языка ЦЕ). Таким образом, ЦЕ ) = (Е(Е)) . 4. Если Š— регулярное выражение, то (Е) — регулярное выражение, определяющее тот же язык ЦЕ), что и выражение Е. Формально, Ц(Е)) = Е(Е). Выражения и соответствующие языки Строго говоря, регулярное выражение Š— это просто выражение, а не язык. Мы используем ЦЕ) для обозначения языка, который соответствует Е.
Однако довольно часто говорят "Е", на самом деле подразумевая "ЦЕ)". Это соглашение используется в случаях, когда ясно, что речь идет о языке, а не о регулярном выражении. Пример 3.2. Напишем регулярное выражение для множества цепочек из чередующихся нулей и единиц. Сначала построим регулярное выражение для языка, состоящего из одной-единственной цепочки 01. Затем используем оператор "звездочка" для того, чтобы построить выражение для всех цепочек вида 0101...01.
Базисное правило ддя регулярных выражений говорит, что 0 и 1 — зто выражения, обозначающие языки (О) и (1), соответственно. Если соединить эти два выражения, то получится регулярное выражение 01 для языка (01). Как правило, если мы хотим написать выражение для языка, состоящего из одной цепочки ж, то используем саму и как регулярное выражение, Заметим, что в таком регулярном выражении символы цепочки и обычно выделяют жирным шрифтом, но изменение шрифта предназначено лишь для того, чтобы от- личить выражение от цепочки, и не должно восприниматься как что-то существенное.
' В (Лч! Х точка в регулярных выражениях используется для совершенно другой цели — представления любого знака кола АЗСП. 105 3.1. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ Далее, для получения всех цепочек, состоящих из нуля или нескольких вхождений 01, используем регулярное выражение (01) . Заметим, что выражение 01 заключается в скобки, чтобы не путать его с выражением 01*. Цепочки языка 01* начинаются с О, за которым следует любое количество 1. Причина такой интерпретации объясняется в разделе 3.1.3 и состоит в том, что операция "звездочка" имеет высший приоритет по сравнению с операцией "точка", и поэтому аргумент оператора итерации выбирается до выполнения любых конкатенаций. Однако Ц(01) ) — не совсем тот язык, который нам нужен.
Он включает только те цепочки из чередующихся нулей и единиц, которые начинаются с О и заканчиваются 1. Мы должны также учесть возможность того, что вначале стоит 1 и/или в конце О. Одним из решений является построение еще трех регулярных выражений, описывающих три другие возможности. Итак, (10) представляет те чередующиеся цепочки, которые начинаются символом ! и заканчиваются символом О, 0(10) можно использовать для цепочек, которые начинаются и заканчиваются символом О, а 1(01) — для цепочек, которые и начинаются, и заканчиваются символом 1. Полностью это регулярное выражение имеет следующий вид.
(О!) ь(10) ь 0(10) ч- Ц01)* Заметим, что оператор + используется для объединения тех четырех языков, которые вместе дают все цепочки, состоящие из чередующихся символов О и 1. Однако существует еще одно решение, приводящее к регулярному выраженшо, которое имеет значительно отличающийся и к тому же более краткий вид.
Снова начнем с выражения (01) . Можем добавить необязательную единицу в начале, если слева к этому выражению допишем выражение к + 1. Аналогично, добавим необязательный О в конце с помощью конкатенации с выражением к ь О. Например, используя свойства оператора +, получим, что Ць + 1) = Ця) О Ц1) = 1е) (1) = 1е, 1). Если мы допишем к этому языку любой другой язык Ц то выбор цепочки я даст нам все цепочки из Ц а выбрав 1, получим 1и для каждой цепочки ж из Е.
Таким образом, совокупность цепочек из чередующихся нулей и единиц может быть представлена сле- дующим выражением. (в + 1)(01) (в+ 0) Обратите внимание на то, что суммируемые выражения необходимо заключать в скобки, чтобы обеспечить правильную группировку операторов. С) 3.1.3. Приоритеты регулярных операторов Как н в других алгебрах, операторы регулярных выражений имеют определенные "приоритеты", т.е. операторы связываются со своими операндами в определенном порядке.
Мы знакомы с понятием приоритетности для обычных арифметических выраже- 100 ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ ний, Например, мы знаем, что в выражении ху + з умножение ху выполняется перед сложением, так что это выражение эквивалентно выражению со скобками (ху) ч-д, а не х(у ь =). Аналогично, в арифметике мы группируем одинаковые операторы слева направо, поэтому х — у — г эквивалентно выражению (х -у) — -„а не х — (у — =). Для операторов регулярных выражений определен следующий порядок приоритетов. !.
Оператор звездочка" имеет самый высокий приоритет, т.е. этот оператор применяется только к наименьшей последовательности символов, находящейся слева от него и являющейся правильно построенным регулярным выражением. 2. Далее по порядку приоритетности следует оператор конкатенации, или "точка". Связав все "звездочки" с их операндами„связываем операторы конкатенации с соответствующими им операндами, т.е. все смежные (соседние, без промежуточных операторов) выражения группируются вместе.
Поскольку оператор конкатенации является ассоциативным, то не имеет значения, в каком порядке мы группируем последовательные конкатенации. Если же необходимо сделать выбор, то следует группировать их, начиная слева. Например, 012 группируется как (01)2. 3. В заключение, со своими операндами связываются операторы объединения (операторы ь). Поскольку объединение тоже является ассоциативным оператором, то и здесь не имеет большого значения, в каком порядке сгруппированы последовательные объединения, однако мы будем придерживаться группировки, начиная с левого края выражения.
Конечно, иногда нежелательно, чтобы группирование в регулярном выражении определялось только приоритетом опера~оров. В таких случаях можно расставить скобки и сгруппировать операнды по своему усмотрению. Кроме того, не запрецгается заключать в скобки операнды, которые вы хотите сгруппировать, даже если такое группирование подразумеваешься правилами приоритетности операторов.
Пример 3.3. Выражение 01 ь 1 группируется как (0(1 )) + 1. Сначала выполняется оператор "звездочка". Поскольку символ 1, находящийся непосредственно слева от оператора, является допустимым регулярным выражением, то он один будет операндом "звездочки". Далее группируем конкатенацию 0 и (1) и получаем выражение (0(1 )). Наконец, оператор объединения связывает последнее выражение с выражением, которое находится справа, т.е. с 1. Заметим, что язык данного выражения, сгруппированного согласно правилам приоритетности, содержит цепочку ! плюс все цепочки, начинающиеся с О, за которым следует любое количество единиц (в том числе и ни одной). Если бы мы захотели сначала сгруппировать точку, а потом звездочку, то следовало бы использовать скобки: (01) + 1.
Язык этого выражения состоит из цепочки 1 и всех цепочек, в которых 01 повторяется нуль или несколько раз. Для того чтобы сначала выполнить объединение, его нужно заключить в скобки: 0(1 + 1). Язык этого выражения состоит из цепочек, которые начинаются с 0 и продолжаются любым количеством единиц. П 3.1. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ 107 3.1.4.
Упражнения к разделу 3.1 3.1.1. Напишите регулярные выражения для следующих языков: а) (ч) множество цепочек с алфавитом (а, 6, с), содержащих хотя бы один символ а и хотя бы один символ Ь; б) множество цепочек из нулей и единиц, в которых десятый от правого края символ равен 1; в) множество цепочек из нулей и единиц, содержащих не более одной пары последовательных единиц. 3.1.2. (!) Напишите регулярные выражения для следующих языков: а) (ч) множество всех цепочек из нулей и единиц, в которых каждая пара смежных нулей находится перед парой смежных единиц; б) множество цепочек, состоящих из нулей и единиц, в которых число нулей кратно пяти. 3.1.3. (! !) Напишите регулярные выражения для следующих языков: а) множество всех цепочек из нулей и единиц, в которых нет подцепочки ! 01; б) множество всех цепочек, в которых поровну нулей и единиц и ни один их префикс не содержит нулей на два больше, чем единиц, или единиц на две больше, чем нулей; в) множество всех цепочек из нулей и единиц, в которых число нулей делится на пять, а количество единиц четно.
3.1.4. (!) Опишите обычными словами языки следующих регулярных выражений: а) (в) (! + а)(00*1) 0; б) (О 1 ) 000(Оь1); в) (О + 10) 1 . 3.1.5. (в!) В примере 3.1 отмечено, что Π— это один из двух языков, итерация которых является конечным множеством. Укажите второй язык. 3.2. Конечные автоматы и регулярные выражения Хотя описание языков с помощью регулярных выражений принципиально отличается от конечноавтоматного, оказывается, что обе эти нотации представляют одно и то же множество языков, называемых "регулярными".
Выше мы показали, что детерминиро- ванные конечные автоматы, а также два вида недетерминированных конечных автоматов — с а-переходами и без а-переходов — допускают один и тот же класс языков. Для того чтобы показать, что регулярные выражения задают тот же класс языков, необходи- мо доказать следующее. 108 ГЛАВА 8. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ Е Любой язык, задаваемый одним из этих автоматов, может быть также определен регулярным выражением. Для доказательства можно предположить, что язык допускается некоторым ДКА. 2. Любой язык, определяемый регулярным выражением, может быть также задан с помощью одного из вышеуказанных автоматов.
Для этой части доказательства проще всего показать, что существует НКА с епереходами, допускающий тот же самый язык. На рис. 3.! показаны все эквивалентности, которые уже доказаны или будут доказаны. Дуга, ведущая от класса Х к классу У, означает, что каждый язык, определяемый классом Х, определяется также классом К Поскольку данный граф является сильно связным (в нем можно перейти от каждой из четырех вершин к любой другой вершине), по- пятно, что все четыре класса на самом деле эквивалентны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
