Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 17

Пример 2.6. На рис. 2.9 изображен недетерминированный конечный автомат, допускаюший те и только те цепочки из 0 и 1, которые оканчиваются на 01. Начальным является состояние ды и можно считать, что автомат находится в этом состоянии (а также, возможно, и в других состояниях) до тех пор, пока не "догадается*', что на входе началась замыкаюшая подцепочка 01.

Всегда существует вероятность того, что следуюший символ не является начальным для замыкаюшей подцепочки О1, даже если это символ О. Поэтому состояние да может иметь переходы в себя как по 1, так и по О. Нач Рис. 2.9 сгйА, допускающий цепочки, которые оканчиааютсн на О1 Если очередной входной символ — О, то НКА может предположить, что уже началась замыкающая подпоследовательность 01.

Таким образом, дуга с меткой 0 ведет из со- стоЯниЯ да в дп Заметим, что из 9а выходЯт две дУги, отмеченные символом О. НКА может перейти как в Ем так и в дь и в действительности переходит в оба эти состояния. Мы убедимся в этом, когда дадим строгое определение НКА.

В состоянии д~ наш НКА проверяет, является ли следующий входной символ единицей. Если это так, то он переходит в состояние д и считает цепочку допустимой. Заметим, что из состояния д, дуга, отмеченная нулем, не выходит, а состояние дз вообше не имеет выходящих дуг. В этих состояниях пути НКА "умирают", хотя другие пути по- прежнему сушествуют, В то время как ДКА имеет в каждом состоянии ровно одну выхо- 72 ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ дяшую дугу лля каждого входного символа, для НКА такого ограничения нет.

На примере рис. 2.9 мы убедились, что числом дуг может быть, например, нуль, один или два. На рис. 2.10 видно, как НКА обрабатывает цепочку. Показано, что происходит„когда автомат (см. рнс. 2.9) получает на вход последовательность 00101. Движение начинается нз единственного начального состояния де. Когда прочитан первый символ О, НКА может перейти в состояние либо де, либо дь а потому переходит в оба эти состояния. Эти два пути представлены на рис.

2.10 вторым столбцом. (гупик) Чг Чг (гупик) о о 1 о ! Рис. 2.!О. Состояния, в которых нагодится НКА в процессе обработки цепочки 00г'Ог' Затем читается второй символ О. Из состояния ае вновь можно перейти в сге и дп Однако состояние г(г не имеет переходов по символу О, и поэтому оно "умирает". Когда появляется третий входной символ, 1, нужно рассмотреть переходы из обоих состояний г7е и дь Из состояния ае по 1 есть переход только в гуе, а из г)г — только в г71. Таким образом, прочитав цепочку 001, НКА находится в состояниях г)е и аг. НКА допускает ее, посколь- водит к тому, что ветвь, соответствующая г71, отмирает, в то время как ае переходит в гге и дь По последнемУ символУ! пРоисходит пеРеход из де в г7„а из г(г — в г) . ПосколькУ мы вновь попали в допускающее состояние, то цепочка 00101 допустима. П 2.3.2.

Определение недетерминированного конечного автомата Теперь мы определим формально понятия, связанные с недетерминнрованными конечными автоматами, выделив по ходу различия между ДКА и НКА. Структура НКА в основном повторяет структуру ДКА: А = (а, Х, б, г(е, Р). Эти обозначения имеют следующий смысл, 1. Д есть конечное множество состоя!!ай. 2.

Х есть конечное множество входных сичволов. 3. ае, один из элементов Д, — начальное состояние. 4. г, подмножество Д, — множество заключипгельных (или допускающих) состояний. 2.3. НЕДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ 73 ку дг — допускающее состояние. Однако чтение входных данных еще не завершено. Четвертый входной символ 0 при- 5, б, функция лереходоо, — это функция, аргументами которой являются состояние из Д и входной символ из Х, а значением — некоторое подмножество множества Д.

Заметим, что единственное различие между НКА и ДКА состоит в типе значений функции б, Для НКА — это множество состояний, а для ДКА — одиночное состояние. Пример 2.7. НКА на рис. 2,9 можно формально задать, как ((г?о, Ф е?г) (О, 1), б, 4?о, (г?г) ), где функция переходов б задается таблицей на рис. 2.11. ьЗ Рис, 2.?Д Таблица переходов для Д?СА, допускающего цепочки, которые оканчиваются на О! Заметим, что, как и для ДКА, функцию переходов НКА можно задавать таблицей. Единственное различие состоит в том, что в таблице для НКА на пересечениях строк и столбцов стоят множества, хотя, возможно, и одноэлаиентные, т.е.

содержащие один элемент (згпя?е!оп). Заметим также, что, когда из некоторого состояния по определенному символу перехода нет, на пересечении соответствующих строки и столбца должно стоять И вЂ” пустое множество. 2.3.3. Расширенная функция переходов Для НКА, так же, как и для ДКА, нам потребуется расширить функцию б до функции б, аргументами которой являются состояние д и цепочка входных символов щ, а значением — множество состояний, в которые НКА попадает из состояния д, обработав цепочку и. Эта идея проиллюстрирована на рис. 2.10. По сути, б (д, и) есть столбец состояний, которые получаются при чтении цепочки щ, при условии, что г? — единственное состояние в первом столбце. Так, на рис.

2.10 видно, что б (ао, 001) = (г?е, г?г). Формально б для НКА определяется следующим образом. Базис. б (д, я) = (г?), т.е., не прочитав никаких входных символов, НКА находится только в том состоянии, в котором начинал. Индукции. Предположим, цепочка и имеет вид и = ха, где о — последний символ цепочки и, ах — ее оставшаяся часп . Кроме того, предположим, что б (е? «) = (Р| Ръ " Рь) . Пусть Цб (Ри а) = («„«г, ..., «и). ы ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ 74 Тогда 6 (9, и) = (г„гъ ..., и». ГовоРЯ менее фоРмально, длЯ того, чтобы найти 6 (су, и), нужно найти 6 (су, х), а затем совершить из всех полученных состояний все пе- реходы по символу а.

Пример 2.8. Используем б для описания того, как НКА на рис. 2.9 обрабатывает цепочку 00101. 6 (9о о) = (суо». г. 6 (йм О) = 6(9,, О) = (9„9,». 3. б (суо 00) = 6(суо, 0) (» б (сус, О) = (суо, сус» () И = (суо, сус». 4. 6 (суо, 001) = б (~м 1) () б(йь 1) = (~д» () (су~» = (~м суз». 5. б (суо 0010) = 6(суо 0)(3 6(суз О) = (суо, сус» () И = (суо, (ус». б. 6(йм 00101) = 6(9.,1)() 6(9и !) = (Оо» () (Оз» = (9.,9з» Строка (1) повторяет основное правило. Строку (2) получаем, применяя 6 к единственному состоянию суо из предыдущей строки.

В результате получаем множество (суо, сус». Строка (3) получается объединением двух состояний предыдущего множества и применением к каждому из них 6 с входным символом О, т.е. с)(9о, 0) = (су„сус», и с)(сус, 0) = И. Для того чтобы получить строку (4), берется объединение су(су„1) = (суо» и 6(9с, 1) = (суз». Строки (5) и (6) получены так же, как строки (3) и (4).

ь2 2.3.4. Язык НКА По нашему описанию НКА допускает цепочку и, если в процессе чтения этой цепочки символов можно выбрать хотя бы одну последовательность переходов в следующие состояния так, чтобы прийти из начального состояния в одно из допускающих. Тот факт, что при другом выборе последовательности переходов по символам цепочки и мы можем попасть в недопускаюшее состояние или вообще не попасть ни в какое (т.е. последовательность состояний 'умирает" ), отнюдь не означает, что ж не является допустимой для НКА в целом. Формально, если А = Я, Х, б, йи 6) — некоторый НКА, то У(А) = (~ ! 6 (суо, ) Й б = И». Таким образом, У(А) есть множество цепочек со из Х, для которых среди состояний б (Оо, и ) есть хотя бы одно допускающее. Пример 2.9.

В качестве примера докажем формально, что НКА на рис. 2.9 допускает язык У. = (и ( и оканчивается на 01». Доказательство представляет собой совместную индукцию следующих трех утверждений, характеризующих три состояния. 1. б (суо, со) содержит суо для всякой цепочки и. 2. б (суо, и) содержит сус тогда и только тогда, когда и оканчивается на О. 2.3. НЕДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ 3. 6 (уь, и ) содержит 9з тогда и только тогда, когда и оканчивается на 01. Чтобы доказать эти утверждения, нужно рассмотреть, каким образом А может попасть в каждое из этих состояний, т.е. каким был последний входной символ, и в каком состоянии находился А непосредственно перед тем, как прочитал этот символ. Поскольку язык этого автомата есть множество цепочек и, для которых 6 (е(„и ) содержит дз (так как 9з — единственное допускающее состояние), то доказательство этих трех утверждений, в частности, доказательство 3, гарантирует, что язык данного НКА есть множество цепочек, оканчивающихся на О!.

Доказательство этой теоремы представляет собой индукцию по (и ), длине цепочки ж, начиная с нуля. Базис. Если (и! = О, то ж = ж В утверждении! говорится, что 6 (<усь я) содержит е)ь. Но это действительно так в силу базисной части определения 6 .

Рассмотрим теперь утверждение 2. Мы знаем, что я не заканчивается на О, и, кроме того, опять же в силу базисной части определения 6 (дь, е) не содержит дь Таким образом, гипотезы утверждения 2 типа тогда и только тогда" в обе стороны ложны. Поэтому само утверждение является ис~инным в обе стороны. Доказательство утверждения 3, по сути, повторяет доказательство утверждения 2. Индукция.

Допустим, что ж = ха, где а есть символ 0 или !. Можно предположить, что утверждения 1-3 выполняются для х. Нужно доказать их для и, предположив, что ~и ~ = и+ 1, а !х~ = а. Предполагая, что гипотеза индукции верна для а, докажем ее для и+ 1. 1. Нам известно, что 6 (е)ь, х) содержит дь, Посколысу по обоим входным символам 0 и 1 существуют переходы из аь в себя, то 6 (а„эе) также содержит аь. Таким образом, утверждение 1 доказано для м, 2. Яостаточность) Предположим, что и оканчивается на О, т.е.

а = О. Применяя утверждение 1 к х, получаем, что 6 (дь, х) содержит йь Поскольку по символу 0 существУет пеРеход из е(ь в ди заключаем, что 6 (д„и) содеРжит е(ь (Необходимость) Допустим, что 6(й,„ж) содержит ~уь По диаграмме на рис.2.9 видно, что единственная возможность попасть в состояние е(, реализуется, когда и имеет вид хО. Это доказывает необходимость в утверждении 2. 3. (Достаточность) Предположим, что ж оканчивается на 01. Тогда если и =ха„то мы знаем, что а = 1, а х оканчивается на О.