dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 19
Текст из файла (страница 19)
2.3.7. Óïðàæíåíèÿ ê ðàçäåëó 2.32.3.1.Преобразуйте следующий НКА в эквивалентный НКА.01{p, q}{p}q{r}{r}r{s}∅*s{s}{s}→p2.3.2.Преобразуйте следующий НКА в эквивалентный ДКА01{q, s}{q}*q{r}{q, r}r{s}{p}*s∅{p}→p2.3.3.2.3.4.4Преобразуйте следующий НКА в эквивалентный ДКА и опишите неформальноязык, который он допускает.01→p{p, q}{p}q{r, s}{t}r{p, r}{t}*s∅∅*t∅∅(!) Найдите недетерминированные конечные автоматы, которые допускаютследующие языки. Постарайтесь максимально использовать возможности недетерминизма:В русскоязычной литературе часто употребляется термин “принцип Дирихле”. — Прим.
ред.2.3. ÍÅÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр. 8383а) (∗) множество цепочек над алфавитом {0, 1, …, 9}, последняя цифра которыхвстречается еще где-то в них;Äüÿâîëüñêèå ñîñòîÿíèÿ è ÄÊÀ ñ íåîïðåäåëåííûìè ïåðåõîäàìèФормально определяя ДКА, мы требовали, чтобы по каждому входному символу онимел переход в одно и только одно состояние. Однако иногда бывает более удобноустроить ДКА таким образом, чтобы он “умирал” в ситуации, когда входная последовательность уже не может быть допустимой, что бы к ней ни добавлялось.
Рассмотрим, например, автомат на рис. 1.2, единственной задачей которого является распознавание одиночного ключевого слова then. Чисто технически, данный автомат неявляется ДКА, так как для каждого состояния в нем отсутствуют переходы по большинству входных символов.Но этот автомат является НКА. И если посредством конструкции подмножеств превратить его в ДКА, то вид автомата практически не изменится, хотя при этом в немпоявится дьявольское состояние, которое не является допускающим и переходит само в себя по любому символу. Это состояние соответствует ∅ — пустому множествусостояний автомата на рис. 1.2.Вообще говоря, можно добавить дьявольское состояние в любой автомат, если онимеет не более одного перехода для всякого состояния и входного символа.
Тогда добавляется переход в дьявольское состояние из остальных состояний q по всем символам, для которых переход из q не определен. В результате получается ДКА в точномсмысле слова. Поэтому иногда будем говорить об автомате как о ДКА, если он имеетне более одного перехода из любого состояния по любому входному символу, а нетолько в случае, когда он имеет только один переход.б) множество цепочек над алфавитом {0, 1, …, 9}, последняя цифра цепочкикоторых больше нигде в них не встречается;в) множество цепочек из 0 и 1, в которых содержится два 0, разделенных позициями в количестве, кратном 4.
Отметим, что нуль позиций можно такжесчитать кратным 4.2.3.5.В части “необходимость” теоремы 2.12 было пропущено индуктивное доказа∧∧тельство того, что если δ D(q, w) = p, то δ N(q, w) = {p}, где индукция велась быпо |w|. Приведите это доказательство.2.3.6.84Стр. 84(!) В замечании “Дьявольские состояния и ДКА с неопределенными переходами” утверждалось, что если НКА N по каждому входному символу содержит переход не более чем в одно состояние (т.е. δ(q, a) есть не более чемодноэлементное множество), то ДКА D, построенный по N с помощью конструкции подмножеств, содержит точно те же состояния и переходы, что и N,ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛплюс переходы в новое дьявольское состояние из тех состояний и по темвходным символам, для которых переходы N не определены.
Докажите этоутверждение.2.3.7.В примере 2.13 утверждалось, что НКА находится в состоянии qi (i = 1, 2, …, n)по прочтении входной последовательности w тогда и только тогда, когда i-йсимвол с конца есть 1. Докажите это утверждение.2.4. Ïðèëîæåíèå: ïîèñê â òåêñòåВ предыдущем разделе была рассмотрена абстрактная “проблема”, состоявшая в том,что нужно было выяснить, оканчивается ли данная последовательность двоичных чиселна 01. В этом разделе мы увидим, что подобного рода абстракции прекрасно подходятдля описания таких реальных задач, возникающих в приложениях, как поиск в сети Internet и извлечение информации из текста.2.4.1.
Ïîèñê öåïî÷åê â òåêñòåВ век Internet и электронных библиотек с непрерывным доступом обычной являетсяследующая проблема. Задано некоторое множество слов, и требуется найти все документы, в которых содержится одно (или все) из них. Популярным примером такого процессаслужит работа поисковой машины, которая использует специальную технологию поиска,называемую обращенными индексами (inverted indexes).
Для каждого слова, встречающегося в Internet (а их около 100,000,000), хранится список адресов всех мест, где оновстречается. Машины с очень большим объемом оперативной памяти обеспечивают постоянный доступ к наиболее востребованным из этих списков, позволяя многим людямодновременно осуществлять поиск документов.В методе обращенных индексов конечные автоматы не используются, но этот методтребует значительных затрат времени для копирования содержимого сети и переписывания индексов.
Существует множество смежных приложений, в которых применить технику обращенных индексов нельзя, зато можно с успехом использовать методы на основе автоматов. Те приложения, для которых подходит технология поиска на основе автоматов, имеют следующие отличительные особенности.1.Содержимое хранилища текста, в котором производится поиск, быстро меняется.Вот два примера:а) каждый день аналитики ищут статьи со свежими новостями по соответствующим темам. К примеру, финансовый аналитик может искать статьи с определенными аббревиатурами ценных бумаг или названиями компаний;б) “робот-закупщик” по требованию клиента отслеживает текущие цены по определенным наименованиям товаров.
Он извлекает из сети страницы, содер-2.4. ÏÐÈËÎÆÅÍÈÅ: ÏÎÈÑÊ Â ÒÅÊÑÒÅСтр. 8585жащие каталоги, а затем просматривает эти страницы в поисках информациио ценах по конкретному наименованию.2.Документы, поиск которых осуществляется, не могут быть каталогизированы. Например, очень непросто отыскать в сети все страницы, содержащие информациюобо всех книгах, которые продает компания Amazon.com, поскольку эти страницыгенерируются как бы “на ходу” в ответ на запрос. Однако мы можем отправить запрос на книги по определенной теме, скажем, “конечные автоматы”, а затем искать втой части текста, которая содержится на появившихся страницах, определенное слово, например слово “прекрасно”.2.4.2.
Íåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû äëÿ ïîèñêà â òåêñòåПусть нам дано множество слов, которые мы в дальнейшем будем называть ключевыми словами, и нужно отыскать в тексте места, где встречается любое из этих слов. Вподобных приложениях бывает полезно построить недетерминированный конечный автомат, который, попадая в одно из допускающих состояний, дает знать, что встретил одно из ключевых слов. Текст документа, символ за символом, подается на вход НКА, который затем распознает в нем ключевые слова.
Существует простая форма НКА, распознающего множество ключевых слов.1.Есть начальное состояние с переходом в себя по каждому входному символу, например, печатному символу ASCII при просмотре текста. Начальное состояниеможно представлять себе, как “угадывание” того, что ни одно из ключевых слов ещене началось, даже если несколько букв одного из ключевых слов уже прочитано.2.Для каждого ключевого слова a1a2…ak имеется k состояний, скажем q1, q2, …, qk.Для входного символа a1 есть переход из начального состояния в q1, для входногосимвола a2 — переход из q1 в q2 и т.д. Состояние qk является допускающим и сигнализирует о том, что ключевое слово a1a2…ak обнаружено.Пример 2.14. Предположим, что мы хотим построить НКА, распознающий словаweb и ebay.
Диаграмма переходов данного НКА, изображенная на рис. 2.16, построенас помощью изложенных выше правил. Начальное состояние — это состояние 1, а Σ обозначает множество печатаемых символов ASCII. Состояния 2–4 отвечают за распознавание слова web, а состояния 5–8 — за распознавание слова ebay.
86Стр. 86ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ235641Начало78Рис. 2.16. НКА, осуществляющий поиск слов web и ebayБезусловно, НКА — не программа. Для реализации данного НКА у нас есть две основные возможности.1.Написать программу, имитирующую работу данного НКА путем вычисления множества состояний, в которых он находится по прочтении каждого из входных символов. Такая реализация была рассмотрена на рис. 2.10.2.Преобразовать данный НКА в эквивалентный ему ДКА, используя конструкциюподмножеств. Затем непосредственно реализовать ДКА.В некоторых программах, обрабатывающих текст, таких, например, как наиболеепродвинутые версии команды grep (egrep и fgrep) операционной системы UNIX,используется комбинация этих двух подходов. Однако в нашем случае более удобно преобразование к ДКА, так как это, во-первых, просто, а во-вторых, гарантирует, что числосостояний при этом не возрастет.2.4.3. ÄÊÀ, ðàñïîçíàþùèé ìíîæåñòâî êëþ÷åâûõ ñëîâКонструкция подмножеств применима к любому НКА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
