Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 19
Текст из файла (страница 19)
Определим Л/= (Д, Х, бн, о/о, Р) как эквивалентный ему НКА, где 4, определена следующим правилом. ° Если бо(!/, а/ = р, то 4о(а, а) = (р). Иидукцией по !1е! легко показать, что, если 6 о(</, и) = р, то б н(с/о, и') = (р). Доказательство предоставляется читателю. Как следствие, /Э допускает !с тогда и только тогда, когда Л/ допускает в, т.е. /(/Э) = /(/ч). П 2.3.6. Плохой случай для конструкции подмножеств В примере 2.!О мы обнаружили, что число состояний ДКА и число состояний НКА одинаково. Как мы уже говорили, ситуация, когда количества состояний НКА и построенного по нему ДКА примерно одинаковы, на практике встречается довольно часто. Однако прн переходе от НКА к ДКА возможен и экспоненциальный рост числа состояний, т.е.
все 2' состояний, которые могут быть построены по НКА, имеюшему и состояний, оказываются достижимыми. В следуюшем примере мы немного не дойдем до этого предела, но будет ясно, каким образом наименьший ДКА, построенный по НКА с и е 1 состояниями, может иметь 2" состояний. Пример 2.13. Рассмотрим НКА на рис. 2.15. /(Л/) есть множество всех цепочек из О и 1, у которых и-м символом с конца является 1. Интуиция подсказывает, что ДКА /1, допускаюший данный язык, должен помнить последние и прочитанных символов. Поскольку всего имеется 2" последовательностей, состоящих из последних и символов, то при числе состояний /) меньше 2" нашлось бы состояние !/, в которое Р попадает по прочтении двух разных последовательностей, скажем, а,а,...а„и Ь|Ьь ..Ь„.
О,! 1 Рис. 2./5. Этот НКА не имеет эквиволентногоДКА, число состояний которого меньше 2" Поскольку последовательности различны, они должны различаться символом в некоторой позиции, например, а; иЬ, Предположим (с точностью до симметрии), что а, = 1 и Ь, = О. Если / = 1, то состояние !/ должно быть одновременно и допускаюшим, и недо- 2.3. НЕДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ 81 пускающим, поскольку последовательность а|аз...а„допустима (л-й символ с конца есть 1), а Ь|Ьз...܄— нет. Если же! > 1, то рассмотрим состояние р, в которое 22 попадает из состояния д по прочтении цепочки из ! — 1 нулей. Тогда р вновь должно одновременно и быть, и не быть допускающим, так как цепочка аа; н..а„00...0 допустима, а Ь,Ьнч Ь„ОО...Π— нет.
Теперь рассмотрим, как работает НКА Ф на рис. 2.15. Существует состояние д,, в котором этот НКА находится всегда, независимо от входных символов. Если следующий символ — 1, то Ж может "догадаться", что эта 1 есть л-й символ с конца. Поэтому одновременно с переходом в ц, НКА Ю переходит в состояние дн Из состояния д1 по любому символУ АГ пеРеходит в состоЯние 9з. СледУющий символ пеРеводит У в состоЯние дз и так далее, пока л — 1 последующий символ не переведет Аг в допускающее состояние <у„.
Формальные утверждения о работе состояний А! выглядят следующим образом, 1. А! находится в состоянии 9в по прочтении любой входной последовательности зг. 2. У находится в состоянии д,(! = 1, 2,...,л) по прочтении входной последовательности н тогда и только тогда, когда г-й символ с конца и есть 1, т.е. и имеет вид х!а,аз...аьн где а, — входные символы. "Принцип голубятни" В примере 2.13 мы использовали важный технический прием, применяемый в различных обоснованиях. Он называется принципом голубятни.~ Простыми словами, если у вас больше голубей, чем клеток для них, и каждый голубь залетает в одну из клеток, то хотя бы в одной клетке окажется больше одного голубя. В нашем примере "голубями" являются последовательности из л элементов, а "клетками*' — состояния.
Поскольку состояний меньше, чем последовательностей, две различные последова- тельности должны вести в одно и то же состояние. Принцип голубятни может показаться очевидным, но в действительности он зависит от конечности числа клеток. Поэтому он применим к автоматам с конечным числом состояний и неприменим к автоматам, число состояний которых бесконечно. Чтобы убедиться в том, что конечность числа клеток существенна, рассмотрим случай, когда есть бесконечное число клеток, соответствующих целым числам 1, 2, .... Проиумеруем голубей числами О, 1, 2, ..., т.е.
так, чтобы их было на одного больше, чем клеток. Тогда можно поместить голубя с номером ! в (1+ 1)-ю клетку для всех ! > О. Тогда каждый из бесконечного числа голубей попадет в клетку, и никакие два голубя не окажутся в одной клетке. Мы не доказываем эти утверждения формально. Скажем лишь, что доказательство представляет собой несложную индукцию по ~зг), как в примере 2.9. Завершая доказа- ' В русскоязычной литературе часто употребляется термин "принцип Днрнхле*'. — Прин. лед. ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ 82 тельство того, что данный автомат допускает именно те цепочки, у которых на и-й позиции с конца стоит 1, мы рассмотрим утверждение (2) при 1= и, В нем говорится, что Ф находится в состоянии д„тогда и только тогда, когда и-й символ с конца есть 1.
Но ~у„является единственным допускающим состоянием, поэтому это условие также точно характеризует множество цепочек, допускаемых автоматом Ю, С) 2.3.7. Упражнения к разделу 2.3 2.3.1. Преобразуйте следуюший НКА в эквивалентный НКА. 2.3.2. Преобразуйте следующий НКА в эквиваяентный ДКА 2.3.3. Преобразуйте следующий НКА в эквивалентный ДКА и опишите неформально язык, который он допускает. 2.3,4.
(!)Найдите недетерминированные конечные автоматы, которые допускают следуюшие языки. Постарайтесь максимально использовать возможности не- детерминизма; а) (е) множество цепочек над алфавитом (О, 1, ..., 9), последняя цифра которых встречается еще где-то в них; 83 2.3. НЕДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ Дьявольские состояния и ДКА с неопределенными переходами Формально определяя ДКА, мы требовали, чтобы по каждому входному символу он имел переход в одно и только одно состояние.
Однако иногда бывает более удобно устроить ДКА таким образом, чтобы он 'умирал" в ситуации, когда входная последовательность уже не может быть допустимой, что бы к ней ни добавлялось. Рассмотрим, например, автомат на рис. 1.2, единственной задачей которого является распознавание одиночного ключевого слова 1)зеп. Чисто технически, данный автомат не является ДКА, так как для каждого состояния в нем отсутствуют переходы по большинству входных символов. Но этот автомат является НКА. И если посредством конструкции подмножеств превратить его в ДКА, то вид автомата практически не изменится, хотя при этом в нем появится дьявольское состояние, которое не является допускающим и переходит само в себя по любому символу. Это состояние соответствует И вЂ” пустому множеству состояний автомата на рис. 1.2.
Вообще говоря, можно добавить дьявольское состояние в любой автомат, если он имеет ие более одного перехода для всякого состояния и входного символа. Тогда добавляется переход в дьявольское состояние из остальных состояний а по всем символам, для которых переход из а не определен. В результате получается ДКА в точном смысле слова. Поэтому иногда будем говорить об автомате как о ДКА, если он имеет не более одного перехода из любого состояния по любому входному символу, а не только в случае, когда он имеет только один переход. б) множество цепочек над алфавитом 10, 1, ..., 9), последняя цифра цепочки которых больше нигде в них не встречается; в) множество цепочек из О и 1, в которых содержится два О, разделенных позициями в количестве, кратном 4.
Отметим, что нуль позиций можно также считать кратным 4. (1) В замечании "Дьявольские состояния и ДКА с неопределенными переходами" утверждалось, что если НКА Ф по каждому входному символу содержит переход не более чем в одно состояние (т.е. ЙО, а) есть не более чем одноэлементное множество), то ДКА Р, построенный по Ф с помощью конструкции подмножеств, содержит точно те же состояния и переходы, что и А', плюс переходы в новое дьявольское состояние из тех состояний и по тем входным символам, для которых переходы Ю не определены.
Докажите это 2.3.6. утверждение. ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ 84 2.3.5. В части "необходимость" теоремы 2.!2 было пропущено индуктивное доказательство того, что если б о(су, и ) = р, то б н(~у, зг) = 1р), где индукция велась бы по 1зг~. Приведите это доказательство. 2.3.7. В примере 2.13 утверждалось, что НКА находится в состоянии о, 1! = 1, 2, ..., и) по прочтении входной последовательности и тогда и только тогда, когда 1-й символ с конца есть ! . Докажите это утверждение. 2.4. Приложение: поиск в тексте В предыдущем разделе была рассмотрена абстрактная "проблема", состоявшая в том, что нужно было выяснить, оканчивается ли данная последовательность двоичных чисел на О1. В этом разделе мы увидим, что подобного рода абстракции прекрасно подходят лля описания таких реальных задач, возникающих в приложениях, как поиск в сети 1пгегвез н извлечение информации из текста.
2.4.1. Поиск цепочек в тексте В век 1пзегпег и электронных библиотек с непрерывным доступом обычной является следующая проблема. Задано некоторое множество слов, и требуется найти все документы, в которых содержится одно (или все) из них. Популярным примером такого процесса служит работа поисковой машины, которая использует специальную технологию поиска, называемую обращенными индексами (~пиепед 1пдехез). Для каждого слова, встречающегося в !пзегпез (а их около 100,000,000), хранится список адресов всех мест, где оно встречается. Машины с очень большим объемом оперативной памяти обеспечивают постоянный доступ к наиболее востребованным из этих списков, позволяя многим людям одновременно осуществлять поиск документов. В методе обращенных индексов конечные автоматы не используются, но этот метод требует значительных затрат времени для копирования содержимого сети и переписывания индексов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
