Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 18
Текст из файла (страница 18)
Применив утверждение 2 к х, получим, что 6 (дь, х) содержит дь Поскольку по символу 1 существует переход из д, в дз, приходим к выводу, что 6 (дь, ю) содержит щ. (Необходихюсть) Допустим, что 6 (дь, и) содержит дь По диаграмме на рис. 2.9 видно, что в состояние дз можно попасть тогда и только тогда, когда эе имеет вид х! 76 ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ и б (дм х) содержит дь Применяя утверждение 2 к х, получим, что х оканчивается на О.
Таким образом, и оканчивается на 01, и утверждение 3 доказано. 2.3.5. Эквивалентность детерминированных и недетерминированных конечных автоматов Для многих языков, в частности, для языка цепочек, оканчивающихся на 01 (пример 2,6), построить соответствующий НКА гораздо легче, чем ДКА. Несмотря на это, всякий язык, который описывается некоторым НКА, можно также описать и некоторым ДКА. Кроме того, этот ДКА имеет, как правило, примерно столько же состояний, сколько и НКА, хотя часто содержит больше переходов. Однако в худшем случае наименьший ДКА может содержать 2" состояний, в то время как НКА для того же самого языка имеет всего п состояний.
В доказательстве того, что ДКА обладают всеми возможностями НКА, используется одна важная конструкция, называемая конструкцией лоджножеспгв, поскольку включает построение всех подмножеств множества состояний НКА. Вообще, в доказательствах утверждений об автоматах часто по одному автомату строится другой. Для нас конструкция подмножеств важна в качестве примера того, как один автомат описывается в терминах состояний и переходов другого автомата без знания специфики последнего. Построение подмножеств начинается, исходя из НКА %= Як, Х, 4,, г),, Р;~). Целью является описание ДКА ьЗ = Яо, Х, 4э, (д,), г"о), у которого С(Лг) = 7.(Р). Отметим, что входные алфавиты этих двух автоматов совпалают, а начальное состояние !) есть множество, содержащее только начальное состояние Ф.
Остальные компоненты В строятся следующим образом. ° До есть множество всех подмножеств Дн или булеан множества Дн Отметим, что если Дв содержит и состояний, то До будет содержать уже 2" состояний. Однако часто не все они достижимы из начального состояния автомата О. Такие недостижимые состояния можно "отбросить", поэтому фактически число состояний !Э может быть гораздо меньше, чем 2". ° го есть множество подмножеств э множества Дн, для которых э П г"и в 8, т.е. Р'о состоит из всех множеств состояний Ф, солержащих хотя бы одно допускающее состояние Ж. ° Для каждого множества Я ~ Дн и каждого входного символа а из Х Дэ(э, а) = ( ) бг(р, а). Таким образом, для того, чтобы найти Дэ(о, а), мы рассматриваем все состояния р из о, ищем те состояния Ж, в которые можно попасть из состояния р по 2.3.
НЕДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ 77 символу а, а затем берем объединение множеств найденных состояний по всем состояниям р. Пример 2.10. Пусть У вЂ” автомат на рис. 2.9, допускающий цепочки, которые окан- чиваютсЯ на 01. ПосколькУ множество состоЯний У есть 19т дь дз1, то констРУкциа подмножеств дает ДКА с 2' = 8 состояниями, отвечающими всем подмножествам, составленным из этих трех состояний. На рис. 2.12 приведена таблица переходов для полученных восьми состояний.
Объясним вкратце, как были получены элементы этой таблицы. Рис. 2.12. Полная конструкция нодмноясеств дяя автомата на рис. 2.9 Заметим, что данная таблица, элементами которой являются множества, соответствует детерминированному конечному автомату, поскольку состояния построенного ДКА сами являются множествами.
Для ясности можно переобозначить состояния. Например, 0 обозначить как А, (до1 — как В и т.д. Таблица переходов для ДКА на рис. 2.13 определяет в точности тот же автомат, что и на рис. 2.12, и из ее вида понятно, что элементами таблицы являются одиночные состояния ДКА. Рис. 2.13. Переименование состояний на рис. 2.
12 78 ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ Начиная в состоянии В, из всех восьми состояний мы можем попасть только в со- стояния В, Е и Е. Остальные пять состояний из начального недостижимы, и поэтому их можно исключить из таблицы. Часто можно избежать построения элементов таблицы переходов для всех подмножеств, что требует экспоненциального времени. Для этого выполняется следующее "ленивое вычисление" подмножеств.
Базис. Мы точно знаем, что одноэлементное множество, состояшее из начального состояния Аг, является достижимым. Индукции. Предположим, мы установили, что множество состояний 5 является достижимым. Тогда для каждого входного символа а нужно найти множество состояний бо(5, а). Найденные таким образом множества состояний также будут достижимы.
ЭлементаРный пРимеР: нам известно, что (Че) есть одно из состоЯний ДКА с). Находам, что глг((Че), 0) = (Чы Ч1) и гх>((Чо), 1) = (Че). Оба эти факта следуют из диаграммы переходов для автомата на рис. 2.9; как видно, по символу 0 есть переходы из Чо в Чс и Ч„ а по символу 1 — только в Чы Таким образом, получена вторая строка таблицы переходов ДКА на рис. 2.12. Одно из найденных множеств, (Чо), Уже РассматРивалось. Но втоРое, (Чо, Ч ), — новое, и переходы для него нужно найти: бо((Чо, Чг), 0) = (суы Ч~) н ечг((Чо Чд, 1) = (Чо Чг). Проследить последние вьгчисления можно, например, так: А~((Чы ЧЖ), 1) = МЧо, 1) 0 бч(Чь 1) = (Чо) 0 (Чг) = (Чо, Чг).
Теперь получена пятая строка таблицы на рис. 2.12 и одно новое состояние (Чо, Чг). Аналогичные вычисления показывают, что гспг((Чо Чг), О) = бч(Чо О) 0 бч(Чг О) = (Чо, Ч1) 0 юг = (Чы Чд Й((Чо Чг) 1) = генг(Чо 1) 0 4~(Чг 1) = (Чо) 0 8 = (Чо) . Зти вычисления дают шестую строку таблицы на рис. 2.12, но при этом не получено ни одного нового множества состояний.
Итак, конструкция подмножеств сошлась; известны все допустимые состояния и соотаетствуюшне им переходы. Полностью ДКА показан на рис. 2.14. Заметим, что он имеет лишь три состояния. Это число случайно оказалось равным числу состояний НКА на рис. 2.9, по которому строился этот ДКА. Но ДКА на рис. 2.14 имеет шесть переходов, а автомат на рис. 2.9 — лишь четыре. П нач Рис. 2.14. ДКА, построенный по НКА на рис. 2,9 2.3. НЕДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ 29 На последнем примере мы убедились, что конструкция подмножеств успешно работает. Теперь докажем это формально.
По прочтении последовательности символов зо построенный нами ДКА находится в состоянии, представляющем собой множество состояний НКА, в которые тот попадает, прочитав эту цепочку. Но допускающие состояния ДКА — это состояния, которые содержат хотя бы одно допускающее состояние НКА, а допустимыми для НКА являются цепочки, приводящие его хотя бы в одно из допускающих состояний.
Поэтому можно заключить, что ДКА и НКА допускают в точности одни и те же цепочки. Следовательно, они допускают один и тот же язык. Теорема 2.11. Если ДКА О = (До, Х, до, о)о, го) построен по НКА Ж = (Ь)оь Х, дн, о)о, гч) посредством конструкции подмножеств, то Цьо) = ь(дг). Доказательство. Вначале с помощью индукции по )ч( покажем, что б о((чо), эо) = бил зо) Заметим, что как для одной, так и для другой функции б, значением является множество состояний из Дн.
При этом б о интерпретирует его как состояние из Ь)о (являющегося булеаном Дн), а б н — как подмножество Дн. Базис. Пусть ~н1 — — О, т.е. н = ж Из базисных частей определений б для ДКА и НКА имеем, что как 6 о((с)о), я), так и б н(с)о е) равны (о)о) Индукция. Пусть н имеет длину и + 1, и предположим, что утверждение справедливо для цепочки длины и. Разобьем н на эо = ха, где а — последний символ цепочки и. Согласно гипотезе индукции б р((с)о), х) = д н(до, х). Пусть оба этн множества состояний Ф представляют собой (рь рь ..., ро). По индуктивной части определения для НКА б нйо, ж) = Цб н(рь а).
гм С другой стороны, конструкция подмножеств дает б ((рь рк ." р о), а) = Об н(р, а). (2.3) Теперь, подставляя (2.3) в индуктивную часть определения для ДКА и используя тот факт, что б о((о)о), х) = (рь р„..., рь), получаем; б о((суо), зо) = бо( б о(о)о, х), а)) = бо((рь рь ..., ро) а) = Цб н(рь а). Таким образом, из уравнений (2,2) и (2.4) видно, что б о((до), м ) = 6 к(до, зо).
Далее, замечая, что и 11, н Ф допускают и тогда и только тогда, когда б о((до), н') или б н(до, н ) соответственно содержат некоторое состояние из Е;„, получаем полное доказательство того, что ь(В) = ь(Ф). С) Теорема 2.12. Язык 1, допустим некоторым ДКА тогда и только тогда, когда он допускается некоторым НКА. 80 ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ Доказательство. Достаточность следует из конструкции подмножеств и теоремы 2.11. (Необходимость) Доказательство этой части не представляет трудности; нам нужно лишь перейти от ДКА к идентичному НКА. Диаграмму переходов для некоторого ДКА можно рассматривать неформально как диаграмму переходов для некоторого НКА, причем последний имеет по любому входному символу лишь один переход. Точнее, пусть 0 = Я, Х, б!„!/„Р) есть некоторый ДКА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
