dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 24
Текст из файла (страница 24)
Кроме того, не запрещается заключатьв скобки операнды, которые вы хотите сгруппировать, даже если такое группированиеподразумевается правилами приоритетности операторов.Пример 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.
ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр. 1071073.1.4. Óïðàæíåíèÿ ê ðàçäåëó 3.13.1.1.Напишите регулярные выражения для следующих языков:а) (∗) множество цепочек с алфавитом {a, b, c}, содержащих хотя бы один символ a и хотя бы один символ b;б) множество цепочек из нулей и единиц, в которых десятый от правого краясимвол равен 1;в) множество цепочек из нулей и единиц, содержащих не более одной пары последовательных единиц.3.1.2.(!) Напишите регулярные выражения для следующих языков:а) (∗) множество всех цепочек из нулей и единиц, в которых каждая пара смежных нулей находится перед парой смежных единиц;б) множество цепочек, состоящих из нулей и единиц, в которых число нулейкратно пяти.3.1.3.(!!) Напишите регулярные выражения для следующих языков:а) множество всех цепочек из нулей и единиц, в которых нет подцепочки 101;б) множество всех цепочек, в которых поровну нулей и единиц и ни один ихпрефикс не содержит нулей на два больше, чем единиц, или единиц на двебольше, чем нулей;в) множество всех цепочек из нулей и единиц, в которых число нулей делитсяна пять, а количество единиц четно.3.1.4.(!) Опишите обычными словами языки следующих регулярных выражений:а) (∗) (1 + ε)(00*1)*0*;б) (0*1*)*000(0 + 1)*;в) (0 + 10)*1*.3.1.5.(∗!) В примере 3.1 отмечено, что ∅ — это один из двух языков, итерация которых является конечным множеством.
Укажите второй язык.3.2. Êîíå÷íûå àâòîìàòû è ðåãóëÿðíûå âûðàæåíèÿХотя описание языков с помощью регулярных выражений принципиально отличаетсяот конечноавтоматного, оказывается, что обе эти нотации представляют одно и то жемножество языков, называемых “регулярными”. Выше мы показали, что детерминированные конечные автоматы, а также два вида недетерминированных конечных автоматов — с ε-переходами и без ε-переходов — допускают один и тот же класс языков. Длятого чтобы показать, что регулярные выражения задают тот же класс языков, необходимо доказать следующее.108Стр.
108ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈ1.Любой язык, задаваемый одним из этих автоматов, может быть также определен регулярным выражением. Для доказательства можно предположить, что язык допускается некоторым ДКА.2.Любой язык, определяемый регулярным выражением, может быть также задан с помощью одного из вышеуказанных автоматов.
Для этой части доказательства прощевсего показать, что существует НКА с ε-переходами, допускающий тот же самый язык.На рис. 3.1 показаны все эквивалентности, которые уже доказаны или будут доказаны. Дуга, ведущая от класса X к классу Y, означает, что каждый язык, определяемыйклассом X, определяется также классом Y. Поскольку данный граф является сильно связным (в нем можно перейти от каждой из четырех вершин к любой другой вершине), понятно, что все четыре класса на самом деле эквивалентны.ε−НКАНКАРВДКАРис. 3.1.
План доказательства эквивалентности четырехразличных нотаций для регулярных языков3.2.1. Îò ÄÊÀ ê ðåãóëÿðíûì âûðàæåíèÿìПостроение регулярного выражения для языка, допускаемого некоторым ДКА, оказывается на удивление сложным. Приблизительно это выглядит так: мы строим выражения, описывающие множества цепочек, которыми помечены определенные пути на диаграмме ДКА. Однако эти пути могут проходить только через ограниченное подмножество состояний. При индуктивном определении таких выражений мы начинаем с самыхпростых выражений, описывающих пути, которые не проходят ни через одно состояние(т.е.
являются отдельными вершинами или дугами). Затем индуктивно строим выражения, которые позволяют этим путям проходить через постепенно расширяющиеся множества состояний. В конце этой процедуры получим пути, которые могут проходить через любые состояния, т.е. сгенерируем выражения, представляющие все возможные пути. Эти идеи используются в доказательстве следующей теоремы.Теорема 3.4. Если L = L(A) для некоторого ДКА A, то существует регулярное выражение R, причем L = L(R).Доказательство.
Предположим, что {1, 2, …, n} — множество состояний автомата Адля некоторого натурального n. Независимо от того, какими эти состояния являются на3.2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ È ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр. 109109самом деле, их конечное число n, поэтому их можно переименовать, используя первые nположительных целых чисел. Нашей первой и наиболее сложной задачей является построение набора регулярных выражений, которые описывают постепенно расширяющиеся множества путей в диаграмме переходов автомата А.Обозначим через Rij(k ) регулярное выражение, язык которого состоит из множестваметок w путей, ведущих от состояния i к состоянию j автомата А и не имеющих промежуточных состояний с номерами больше k. Заметим, что начальная и конечная точки пути не являются “промежуточными”, поэтому мы не требуем, чтобы i и/или j были меньше или равны k.Условия, налагаемые на пути выражениями Rij(k ) , представлены на рис.
3.2. Здесь навертикальной оси расположены состояния, начиная с 1 внизу до n вверху, а горизонтальная ось представляет движение вдоль пути. Заметим, что на этой диаграмме показан случай, когда i и j больше, чем k, но любое из этих чисел, или оба, могут быть меньше илиравны k. Также обратите внимание на то, что путь дважды проходит через вершину k, нотолько в крайних точках поднимается выше, чем k.Рис. 3.2.
Путь, отметка которого принадлежит языку регулярного выражения Rij(k )Для построения выражения Rij(k ) используют следующее индуктивное определение,которое начинается с k = 0 и достигает k = n. Заметим, что при k = n пути ничем не ограничиваются, поскольку нет состояний с номерами, которые больше, чем n.Базис. В качестве базиса примем k = 0. Поскольку все состояния пронумерованы от 1и далее, то это условие означает, что у пути вообще нет промежуточных состояний. Существует только два вида путей, удовлетворяющих такому условию.1.Дуга, ведущая от вершины (состояния) i к вершине j.2.Путь длины 0, состоящий лишь из некоторой вершины i.Если i ≠ j, то возможен только первый случай.
Необходимо проанализировать данныйДКА А и найти такие входные символы а, по которым есть переход из состояния i в состояние j:а) если таких символов нет, то Rij( 0) = ∅;110Стр. 110ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈб) если существует только один такой символ a, то Rij( 0) = a;в) если существуют такие символы a1, a2, …, ak, которыми помечены дуги изсостояния i в состояние j, то Rij( 0) = a1 + a2 + … + ak.В то же время, если i = j, то допустимыми путями являются путь длины 0 и все петли,которые начинаются и заканчиваются в состоянии i.
Путь длины 0 может быть представлен регулярным выражением ε, потому что вдоль этого пути нет символов. Следовательно, добавляем ε к выражениям, полученным выше в пунктах (а)–(в). Таким образом, вслучае (а) [нет ни одного символа а] получим выражение ε, в случае (б) [один символ а]выражение примет вид ε + a, и в случае (в) [несколько символов] получим выражениеε + a1 + a2 + … + ak.Индукция. Предположим, что существует путь из состояния i в состояние j, не проходящий через состояния с номерами, которые больше, чем k.
Необходимо рассмотретьдве ситуации.1.Путь вообще не проходит через состояние k. В этом случае метка пути принадлежитязыку Rij( k −1) .2.Путь проходит через состояние k по меньшей мере один раз. Тогда мы можем разделить путь на несколько частей, как показано на рис. 3.3. Первая часть ведет от состояния i к состоянию k, но не проходит через k, последняя ведет из k в j, также непроходя через k, а все части, расположенные внутри пути, ведут из k в k, не проходячерез k. Заметим, что если путь проходит через состояние k только один раз, то“внутренних” частей нет, а есть только путь из i в k и путь из k в j. Множество метокдля всех путей такого вида может быть представлено регулярным выражениемRik( k −1) ( Rkk( k −1) )* Rkj( k −1) .
Таким образом, первое выражение представляет часть пути, ве-дущую в состояние k в первый раз, второе — часть, ведущую из k в k нуль или несколько раз, и третье выражение — часть пути, которая выходит из состояния k впоследний раз и ведет в состояние j.ikkkkВ R(k-1)ikkВ R(k-1)kiНуль или несколько цепочек в R kk(k-1)Рис. 3.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
