Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 25
Текст из файла (страница 25)
Рис. З.А План доказательства эквивалентности четырех различных нотаций для регулярных языков 3.2,1. От ДКА к регулярным выражениям Построение регулярного выражения лля языка, допускаемого некоторым ДКА, оказывается на удивление сложным. Приблизительно это выглядит так: мы строим выраже- ния, описывающие множества цепочек, которыми помечены определенные пути на диаграмме ДКА. Однако эти пути могут проходить только через ограниченное подмножество состояний. При индуктивном определении таких выражений мы начинаем с самых простых выражений, описывающих пути, которые не проходят ни через одно состояние (т.е. являются отдельными вершинами или дугами). Затем индуктивно строим выраже- ния, которые позволякп этим пугям проходить через постепенно расширяющиеся множества состояний. В конце этой процедуры получим пути, которые могут проходить через любые состояния, т.е. сгенерируем выражения, представляющие все возможные пути. Эти идеи используются в доказательстве следующей теоремы.
Теорема 3.4. Если 1. = ЦА) для некоторого ДКА А, то существует регулярное выражение й, причем 1. = Цй). Доказательство. Предположим, что (), 2, ..., л) — множество состояний автомата А для некоторого натурального п. Независимо от того, какими эти состояния являются на 3.2. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ 109 самом деле, их конечное число и, поэтому их можно переименовать, используя первые п положительных целых чисел. Нашей первой и наиболее сложной задачей является построение набора регулярных выражений, которые описывают постепенно расширяющиеся множества путей в диаграмме переходов автомата А. Обозначим через й~" регулярное выражение, язык которого состоит из множества меток ч путей, ведущих от состояния г к состоянию г автомата А и не имеющих промежуточных состояний с номерами больше Е Заметим, что начальная и конечная точки пути не являются "промежуточными", поэтому мы не требуем, чтобы г и/илиГ' были меньше или равны /с.
Условия, налагаемые на пути выражениями Р~"', представлены на рис. 3.2. Здесь на вертикальной оси расположены состояния, начиная с 1 внизу до л вверху, а горизонтальная ось представляет движение вдоль пути. Заметим, что на этой диаграмме показан случай, когда г и г' больше, чем 1, но любое из этих чисел, или оба, могут быть меньше или равны 1. Также обратите внимание на то, что путь дважды проходит через вершину 1, но только в крайних точках поднимается выше, чем /с. Уие.
3.2 Путь, отметка которого оринадлеокит языкурегулярного выралеения о~ ~ и) Для построения выражения и„' ' используют следующее индуктивное определение, которое начинается с 1 = 0 и достигает 1 = п. Заметим, что при 1 = и пути ничем не ограничиваются, поскольку нет состояний с номерами, которые больше, чем п. Базис. В качестве базиса примем 1 = О. Поскольку все состояния пронумерованы от 1 и далее, то это условие означает, что у пути вообще нет промежуточных состояний. Сушествует только два вида путей, удовлетворяющих такому условию. 1.
Дуга, ведущая от вершины (состояния) 1 к вершине г'. 2. Путь длины О, состоящий лишь из некоторой вершины ~'. Если 1 я г', то возможен только первый случай. Необходимо проанализировать данный ДКА А и найти такие входные символы а, по которым есть переход из состояния 1 в со- стояние у: а) если таких символов нет, то и'„'" = О„ ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 110 После объединения выражений для путей двух рассмотренных выше типов получим следующее выражение для меток всех путей, ведущих из состояния ! в состояние >, которые не проходят через состояния с номерами, которые больше, чем >1. Лп> = гн '> ч- Лп '> ! Лн ") Л" '> и е и ! и ) Ч Поскольку данные выражения строятся в порядке возрастания верхнего индекса, можно построить любое выражение )1>", так как оно зависит только от выражений с меньшими значениями верхнего индекса.
В итоге получим )1,',"> лля всех > и /. Можно предположить, что состояние 1 является на- чальным, а множество допускающих (заключительных) состояний может быть любым. Тогда регулярным выражением для языка, допускаемого данным автоматом, будет сумма (объединение) всех тех выражений )!»',",, в которых состояние ) является допускающим.
1:3 Пример 3.5. Преобразуем ДКА, представленный на рис. 3.4, в соответствующее регулярное выражение. Этот ДКА допускает все цепочки, содержащие хотя бы один О. Чтобы понять, почему это так, заметим, что автомат переходит из начального состояния 1 в заключительное состояние 2, как только на входе появляется О. Далее автомат остается в заключительном состоянии 2 при любой входной последовательности. Начал Рис.
3.4. ДКА, допускающий есе Челочки, которые содержат котя оы один О Ниже приведены базисные выражения для построений согласно теореме 3.4. Например, в выражении К„присутствует член в, потому что и начальным, и конеч- >о> ным является состояние 1. Это выражение включает также 1, поскольку существует путь из состояния 1 в состояние 1 по входу 1. Выражение )!» равно О, потому что есть дуга с >о> меткой О, ведущая из состояния 1 в состояние 2.
Здесь нет члена л, поскольку начальное и конечное состояния различаются. И, наконе>ь )1,'» = О, так как нет путей, ведущих из >а> состояния 2 в состояние !. Теперь применим индукцию для построения более сложных выражений. Вначале они соответствуют путям, проходящим через состояние 1, а затем путям, которые могут про- ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 112 ходить через состояния ! и 2, т.е. любым путям. Правило для вычисления выражения р>о представляет собой пример общего правила из индуктивной части теоремы 3.4.
(3.!) о<о Е>о> „Е>в>г о>о> '~з>о> !/ е ~> ( и ) >> В таблице на рнс. 3.5 сначала представлены выражения, полученные с помощью прямой подстановки в приведенную выше формулу, а затем упрощенные выражения, которые определяют те же языки, что и более сложные выражения. Рнс. 3.5. Регулярные выражения для путей, которые могут проходыть только через состояние ! Например, рассмотрим выражение !!>з". Подставив >= 1 и 5= 2 в (3.!), получим В<о»о> (Е>о>)'й~о> ц и и и Общим принципом упрощения является следующий; если !г — произвольное регулярное выражение, то (в+ !1) =)1*.
Он основан на том, что обе части этого равенства описывают язык, образованный конкатенациями нуля или нескольких цепочек из Ц!!). В нашем случае (в+ 1) = 1; отметим, что оба выражения описывают цепочки, состоящие из любого количества единиц. Далее, (к+ 1)1 = 1 . Опять-таки, легко заметить, что оба выражения означают "любое количество единиц".
Следовательно, исходное выражение !1<» эквивалентно выражению О+ 1 О. Последнее описывает язык, содержащий цепочку и О и все цепочки, заканчивающиеся символом О, перед которым стоит произвольное количество единиц. Такой язык также можно определить более простым выражением 1 О. Выражение !!»'> упрощается аналогично рассмотренному выше выражению !!>з>. УпРощение !г»л и !!>зо зависит от двУх следУющих пРавил, описывающих опеРации с И и выполнимых лля любого регулярного выражения г!. !.
И!г = !!И = И, т.е. И является нулем (аннулятором) для конкатенации. В результате конкатенации И, слева или справа, с любым другим выражением получается И. Это правило очевидно, поскольку для того, чтобы в результате конкатенации получить некоторую цепочку, мы должны взять цепочки из обоих аргументов конкатенации. Если один из аргументов равен И, выбор цепочки из него становится невозможным. 2. И + !г = )! ч- И = !1, т.е.
И является единицей для операции объединения. В результа- те объединения любого выражения с И получим то же самое выражение. 3.2. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ 113 Итак, выражение И(к + 1)*1в ч- 1) можно заменить О. После сказанного должны быть по- нятны и два последних упрощения. Теперь вычислим выражения 1Г„". Индуктивное правило для я = 2 имеет следующий вид. р(п Кю е )1%()Гю)')Го) е е н и н (3.2) Если подставим упрощенные выражения из таблицы на рис, 3.5 в уравнение 13.2), то получим выражения, представленные на рис.
3.6. На этом рисунке также приведены упрощенные выражения, полученные согласно правилам, описанным для рцс. 3.5. Рис. 3.6 Регулярные выражения для путей, которые могут проходить через любое состояние 3.2.2. Преобразование ДКА в регулярное выражение методом исключения состояний Метод преобразования ДКА в регулярное выражение, представленный в разделе 3.2.1, работает всегда. Как вы, возможно, заметили, он на самом деле не зависит от того, детерминирован ли этот автомат, и точно так же применим и к НКА, и даже к в- НКА.
Однако такой метод построения регулярного выражения очень трудоемок. Не только потому, что для автомата с и состояниями необходимо построить порядка и вы- 3 ражений, но и потому, что с каждым из и шагов индукции длина выражения может возрастать в среднем в четыре раза, если эти выражения не упрощать. Таким образом, размеры результирующих выражений могут достигать порядка 4" символов.
Существует аналогичный метод, избавляющий от некоторых повторных действий. Например, во всех выражениях с верхним индексом ф) в доказательстве теоремы 3.4 ис- ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 114 Окончательное регулярное выражение, эквивалентное автомату, представленному на рис. 3.4, строится путем объединения всех тех выражений, для которых первое состояние является начальным, а второе — заключительным. В нашем примере ! — началыюе состояние, а 2 — заключительное, поэтому нам нужно лишь выражение )с,',", равное 1 0(0 н- 1) . Оно очень просто интерпретируется. Его язык состоит из всех цепочек, начинающихся с нулевого или некоторого количества единиц, за которыми следует О, а за ним — любая цепочка из нулей и единиц. Иначе говоря, это все цепочки из О и 1, содержащие хотя бы один О.
Е3 пользуется одно и то же подвыражение (д„", "), которое приходится выписывать в обшей сложности п' раз. Метод построения регулярных выражений, который мы изучим в этом разделе, предполагает исключение состояний. Если исключить некоторое состояние ж то все пути автомата, проходящие через это состояние, исчезают. Для того чтобы язык автомата при этом не изменился, необходимо написать на дуге, ведущей непосредственно из некоторого состояния д в состояние р, метки всех тех путей, которые вели из состояния д в состояние р, проходя через состояние з. Поскольку теперь метка такой дуги будет содержать цепочки, а не отдельные символы, н таких цепочек может быть даже бесконечно много, то мы не можем просто записать список этих цепочек в качестве метки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
