dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 25
Текст из файла (страница 25)
Путь из i в j может быть разбит на несколько сегментов в каждой точке,в которой он проходит через состояние k3.2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ È ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр. 111111После объединения выражений для путей двух рассмотренных выше типов получимследующее выражение для меток всех путей, ведущих из состояния i в состояние j, которые не проходят через состояния с номерами, которые больше, чем k.Rij(k ) = Rij( k −1) + Rik( k −1) ( Rkk( k −1) )* Rkj( k −1)Поскольку данные выражения строятся в порядке возрастания верхнего индекса,можно построить любое выражение Rij(k ) , так как оно зависит только от выражений сменьшими значениями верхнего индекса.В итоге получим Rij(n ) для всех i и j.
Можно предположить, что состояние 1 является начальным, а множество допускающих (заключительных) состояний может быть любым. Тогда регулярным выражением для языка, допускаемого данным автоматом, будет сумма(объединение) всех тех выражений R1( nj ) , в которых состояние j является допускающим.
Пример 3.5. Преобразуем ДКА, представленный на рис. 3.4, в соответствующее регулярное выражение. Этот ДКА допускает все цепочки, содержащие хотя бы один 0.Чтобы понять, почему это так, заметим, что автомат переходит из начального состояния1 в заключительное состояние 2, как только на входе появляется 0. Далее автомат остается в заключительном состоянии 2 при любой входной последовательности.НачалоРис.
3.4. ДКА, допускающий все цепочки, которые содержат хотя бы один 0Ниже приведены базисные выражения для построений согласно теореме 3.4.R11( 0)ε+1R12( 0)0( 0)R21∅( 0)R22(ε + 0 + 1)Например, в выражении R11( 0) присутствует член ε, потому что и начальным, и конечным является состояние 1. Это выражение включает также 1, поскольку существует путьиз состояния 1 в состояние 1 по входу 1. Выражение R12( 0) равно 0, потому что есть дуга сметкой 0, ведущая из состояния 1 в состояние 2. Здесь нет члена ε, поскольку начальное( 0)и конечное состояния различаются. И, наконец, R21= ∅, так как нет путей, ведущих изсостояния 2 в состояние 1.Теперь применим индукцию для построения более сложных выражений. Вначале онисоответствуют путям, проходящим через состояние 1, а затем путям, которые могут про112Стр.
112ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈходить через состояния 1 и 2, т.е. любым путям. Правило для вычисления выраженияRij(1) представляет собой пример общего правила из индуктивной части теоремы 3.4.Rij(1) = Rij( 0) + Ri(10) ( R11( 0) )* R1( 0j )(3.1)В таблице на рис. 3.5 сначала представлены выражения, полученные с помощью прямой подстановки в приведенную выше формулу, а затем упрощенные выражения, которые определяют те же языки, что и более сложные выражения.Прямая подстановкаУпрощенное выражениеR11(1)ε + 1 + (ε + 1)(ε + 1)*(ε + 1)1*R12(1)0 + (ε + 1)(ε + 1)*01*0(1)R21∅ + ∅(ε + 1)*(ε + 1)∅(1)R22ε + 0 + 1 + ∅(ε + 1)*0ε+0+1Рис.
3.5. Регулярные выражения для путей, которые могут проходить только через состояние 1Например, рассмотрим выражение R12(1) . Подставив i = 1 и j = 2 в (3.1), получимR12( 0) + R11( 0) ( R11( 0) )* R12( 0) .Общим принципом упрощения является следующий: если R — произвольное регулярное выражение, то (ε + R)* = R*.
Он основан на том, что обе части этого равенстваописывают язык, образованный конкатенациями нуля или нескольких цепочек из L(R). Внашем случае (ε + 1)* = 1*; отметим, что оба выражения описывают цепочки, состоящиеиз любого количества единиц. Далее, (ε + 1)1* = 1*. Опять-таки, легко заметить, что обавыражения означают “любое количество единиц”.
Следовательно, исходное выражение*R12(1) эквивалентно выражению 0 + 1 0. Последнее описывает язык, содержащий цепочку0 и все цепочки, заканчивающиеся символом 0, перед которым стоит произвольное количество единиц. Такой язык также можно определить более простым выражением 1*0.Выражение R11(1) упрощается аналогично рассмотренному выше выражению R12(1) . Упрощение R11(1) и R12(1) зависит от двух следующих правил, описывающих операции с ∅ ивыполнимых для любого регулярного выражения R.1.∅R = R∅ = ∅, т.е.
∅ является нулем (аннулятором) для конкатенации. В результатеконкатенации ∅, слева или справа, с любым другим выражением получается ∅. Этоправило очевидно, поскольку для того, чтобы в результате конкатенации получитьнекоторую цепочку, мы должны взять цепочки из обоих аргументов конкатенации.Если один из аргументов равен ∅, выбор цепочки из него становится невозможным.2.∅ + R = R + ∅ = R, т.е. ∅ является единицей для операции объединения. В результате объединения любого выражения с ∅ получим то же самое выражение.3.2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ È ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈßСтр.
113113Итак, выражение ∅(ε + 1)*(ε + 1) можно заменить ∅. После сказанного должны быть понятны и два последних упрощения.Теперь вычислим выражения Rij( 2) . Индуктивное правило для k = 2 имеет следующий вид.Rij( 2) = Rij(1) + Ri(11) ( R11(1) )* R1(1j)(3.2)Если подставим упрощенные выражения из таблицы на рис. 3.5 в уравнение (3.2), тополучим выражения, представленные на рис. 3.6. На этом рисунке также приведены упрощенные выражения, полученные согласно правилам, описанным для рис. 3.5.Прямая подстановкаУпрощенное выражениеR11( 2)1* + 1*0(ε + 0 + 1)*∅1*R12( 2)1*0 + 1*0(ε + 0 + 1)*(ε + 0 + 1)1*0(0 + 1)*( 2)R21∅ + (ε + 0 + 1)(ε + 0 + 1)*∅∅( 2)R22ε + 0 + 1 + (ε + 0 + 1)(ε + 0 + 1)*(ε + 0 + 1)(0 + 1)*Рис.
3.6. Регулярные выражения для путей, которые могут проходить через любое состояниеОкончательное регулярное выражение, эквивалентное автомату, представленному нарис. 3.4, строится путем объединения всех тех выражений, для которых первое состояниеявляется начальным, а второе — заключительным. В нашем примере 1 — начальное состояние, а 2 — заключительное, поэтому нам нужно лишь выражение R12( 2) , равное1*0(0 + 1)*. Оно очень просто интерпретируется. Его язык состоит из всех цепочек, начинающихся с нулевого или некоторого количества единиц, за которыми следует 0, а заним — любая цепочка из нулей и единиц.
Иначе говоря, это все цепочки из 0 и 1, содержащие хотя бы один 0. 3.2.2. Ïðåîáðàçîâàíèå ÄÊÀ â ðåãóëÿðíîå âûðàæåíèå ìåòîäîìèñêëþ÷åíèÿ ñîñòîÿíèéМетод преобразования ДКА в регулярное выражение, представленный в разделе 3.2.1, работает всегда. Как вы, возможно, заметили, он на самом деле не зависит оттого, детерминирован ли этот автомат, и точно так же применим и к НКА, и даже к εНКА. Однако такой метод построения регулярного выражения очень трудоемок. Нетолько потому, что для автомата с n состояниями необходимо построить порядка n3 выражений, но и потому, что с каждым из n шагов индукции длина выражения может возрастать в среднем в четыре раза, если эти выражения не упрощать.
Таким образом, размеры результирующих выражений могут достигать порядка 4n символов.Существует аналогичный метод, избавляющий от некоторых повторных действий.Например, во всех выражениях с верхним индексом (k) в доказательстве теоремы 3.4 ис114Стр. 114ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈпользуется одно и то же подвыражение ( Rkk( k −1) )*, которое приходится выписывать в общей сложности n2 раз.Метод построения регулярных выражений, который мы изучим в этом разделе, предполагает исключение состояний.
Если исключить некоторое состояние s, то все пути автомата, проходящие через это состояние, исчезают. Для того чтобы язык автомата приэтом не изменился, необходимо написать на дуге, ведущей непосредственно из некоторого состояния q в состояние p, метки всех тех путей, которые вели из состояния q в состояние p, проходя через состояние s. Поскольку теперь метка такой дуги будет содержать цепочки, а не отдельные символы, и таких цепочек может быть даже бесконечномного, то мы не можем просто записать список этих цепочек в качестве метки.
К счастью, существует простой и конечный способ для представления всех подобных цепочек,а именно, использование регулярных выражений.Таким образом, мы пришли к рассмотрению автоматов, у которых метками являютсярегулярные выражения. Язык такого автомата представляет собой объединение по всемпутям, ведущим от начального к заключительному состоянию, языков, образуемых с помощью конкатенации языков регулярных выражений, расположенных вдоль этих путей.Обратите внимание на то, что это правило согласуется с определением языка для любогорассмотренного выше типа автоматов. Каждый символ a или ε, если он разрешен, можнорассматривать как регулярное выражение, языком которого является единственная цепочка, т.е. {a} или {ε}. Можно принять это замечание за основу описываемой ниже процедуры исключения состояний.На рис.
3.7 показано состояние s, которое мы собираемся исключить. Предположим, что автомат, содержащий s, содержит состояния q1, q2, …, qk, предшествующие s,и p1, p2, …, pm, следующие за s. Возможно, некоторые из состояний q совпадают с состояниями p, но мы предполагаем, что среди q и p нет s, даже если существует петля, которая начинается и заканчивается в s, как показано на рис. 3.7. Над каждой дугой, ведущей к состоянию s, указано регулярное выражение; дуга, ведущая из состояния qi, помечена выражением Qi.
Аналогично, регулярным выражением Pi помечена дуга, ведущая изs в состояние pi, для каждого i. Петля на s имеет метку S. Наконец, регулярным выражением Rij помечена каждая дуга, ведущая из qi в pj для всех i и j. Заметим, что некоторыхиз этих дуг в автомате может не быть. В этом случае в качестве выражения над дугой используется символ ∅.На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
