dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 12
Текст из файла (страница 12)
Тогда теорему о построенных таким способом объектах можно доказывать индукцией по числу шагов, использованных приих построении. Этот тип индукции называют структурной индукцией.♦ Алфавиты. Алфавитом является некоторое конечное множество символов.♦ Цепочки. Цепочкой называют конечную последовательность символов.♦ Языки и проблемы. Язык есть (вообще говоря, бесконечное) множество цепочек,состоящих из символов некоторого фиксированного алфавита. Если цепочки языка должны быть проинтерпретированы некоторым способом, вопрос о принадлежности определенной цепочки этому языку иногда называют проблемой.ËèòåðàòóðàДля углубленного изучения материала этой главы, посвященной основополагающимматематическим понятиям информатики, мы рекомендуем книгу [1].1.52Стр.
52A. V. Aho and J. D. Ullman, Foundations of Computer Science, Computer Science Press,New York, 1994.ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßÃËÀÂÀ 2Êîíå÷íûåàâòîìàòûВ этой главе мы введем класс языков, известных как “регулярные”. Это языки, которые могутбыть описаны конечными автоматами. Последние мы уже обсудили вкратце в разделе 1.1.1.Перед тем как формально определить конечные автоматы, рассмотрим развернутый пример,из которого станет ясной мотивация последующего изучения этих объектов.Как указывалось ранее, конечный автомат состоит из множества состояний и“управления”, переводящего из одного состояния в другое в зависимости от получаемыхизвне “входных данных”.
Классы автоматов существенно различаются по типу этогоуправления. Управление может быть “детерминированным” в том смысле, что автоматможет находиться в каждый момент времени не более чем в одном состоянии, и“недетерминированным”, т.е. автомат может одновременно находиться в нескольких состояниях. Мы выясним, что добавление недетерминизма не позволяет определять языки,которые нельзя было бы определить с помощью детерминированных конечных автоматов. Тем не менее, недетерминированные автоматы оказываются весьма эффективными вприложениях. Именно недетерминизм позволяет нам “программировать” решение задач,используя языки высокого уровня.
В этой главе рассматривается алгоритм “компиляции”недетерминированного конечного автомата в детерминированный, который затем можетбыть “выполнен” на обычной вычислительной машине.В заключительной части главы изучается расширенный недетерминированный автомат,который имеет дополнительную возможность переходить из состояния в состояние спонтанно, т.е.
по пустой цепочке в качестве входа. Эти автоматы также описывают только регулярные языки. Тем не менее, они окажутся совершенно необходимыми в главе 3 при изучении регулярных выражений и доказательстве их эквивалентности автоматам.Изучение регулярных языков продолжается в главе 3. Там представлен еще одинважный способ их описания посредством такой алгебраической нотации, как регулярноевыражение. Мы изучим регулярные выражения и покажем их эквивалентность конечнымавтоматам, чтобы в главе 4 использовать и те, и другие как инструменты для доказательства некоторых важных свойств регулярных языков.
Например, свойства “замкнутости”,позволяющие утверждать, что некоторый язык является регулярным, на том основании,что один или несколько других языков регулярны. Еще один пример — “разрешимые”свойства, т.е. наличие алгоритмов, позволяющих ответить на вопросы, касающиеся автомата или регулярного выражения, например, представляют ли два различных автоматаили регулярных выражения один и тот же язык.Стр. 532.1.
Íåôîðìàëüíîå çíàêîìñòâî ñ êîíå÷íûìè àâòîìàòàìèВ этом разделе рассматривается развернутый пример реальной проблемы, в решениикоторой важную роль играют конечные автоматы. Мы изучим протоколы, поддерживающие операции с “электронными деньгами” — файлами, которые клиент используетдля платы за товары в Internet, а продавец получает с гарантией, что “деньги” — настоящие. Для этого продавец должен знать, что эти файлы не были подделаны или скопированы и отосланы продавцу, хотя клиент сохраняет копию этого файла и вновь используетее для оплаты.Невозможность подделки файла должна быть гарантирована банком и стратегиейшифрования. Таким образом, третий участник, банк, должен выпускать и шифровать“денежные” файлы так, чтобы исключить возможность подделки. Но у банка есть и другая важная задача: хранить в своей базе данных информацию о всех выданных им деньгах, годных к платежу. Это нужно для того, чтобы банк мог подтвердить, что полученный магазином файл представляет реальные деньги и может быть переведен на счет магазина.
Мы не будем останавливаться на криптографическом аспекте проблемы, а такжена том, каким образом банк может хранить и обрабатывать биллионы “электронных денежных счетов”. Весьма маловероятно, чтобы эти проблемы привели к каким-нибудьдолговременным затруднениям в концепции электронных денег, тем более что они используются в относительно небольших масштабах с конца 1990-х годов.Однако для того, чтобы использовать электронные деньги, необходимо составитьпротоколы, позволяющие производить с этими деньгами различные действия в зависимости от желания пользователя. Поскольку в монетарных системах всегда возможномошенничество, нужно проверять правильность использования денег, какая бы система шифрования ни применялась. Иными словами, нужно гарантировать, что произойтимогут только предусмотренные события. Это не позволит нечистому на руку пользователю украсть деньги у других или их “напечатать”.
В конце раздела приводится оченьпростой пример (плохого) протокола расчета электронными деньгами, моделируемогоконечными автоматами, и показывается, как конструкции на основе автоматов можноиспользовать для проверки протоколов (или, как в нашем случае, для поиска в протоколе изъянов).2.1.1. Îñíîâíûå ïðàâèëàЕсть три участника: клиент, магазин и банк. Для простоты предположим, что естьвсего один “денежный” файл (“деньги”). Клиент может принять решение передать этотфайл магазину, который затем обменяет его в банке (точнее, потребует, чтобы банквзамен его выпустил новый файл, принадлежащий уже не клиенту, а магазину) и доставит товар клиенту.
Кроме того, клиент имеет возможность отменить свой файл, т.е.попросить банк вернуть деньги на свой счет, причем они уже не могут быть израсхо-54Стр. 54ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛдованы. Взаимодействие трех участников ограничено, таким образом, следующимипятью событиями.1.Клиент может совершить оплату (pay) товара, т.е. переслать денежный файл вмагазин.2.Клиент может выполнить отмену (cancel) денег. Они отправляются в банк вместе ссообщением о том, что их сумму следует добавить к банковскому счету клиента.3.Магазин может произвести доставку (ship) товара клиенту.4.Магазин может совершить выкуп (redeem) денег. Они отправляются в банк вместе стребованием передать их сумму магазину.5.Банк может выполнить перевод (transfer) денег, создав новый, надлежащим образомзашифрованный, файл и переслав его магазину.2.1.2.
ÏðîòîêîëВо избежание недоразумений участники должны вести себя осторожно. В нашем случае мы резонно полагаем, что клиенту доверять нельзя. Клиент, в частности, может попытаться скопировать денежный файл и после этого уплатить им несколько раз или уплатить и отменить его одновременно, получая, таким образом, товар бесплатно.Банк должен вести себя ответственно, иначе он не банк. В частности, он должен проверять, не посылают ли на выкуп два разных магазина один и тот же денежный файл, ине допускать, чтобы одни и те же деньги и отменялись, и выкупались. Магазин тожедолжен быть осторожен. Он, например, не должен доставлять товар, пока не убедится,что получил за него деньги, действительные к оплате.Протоколы такого типа можно представить в виде конечных автоматов.
Каждое состояние представляет ситуацию, в которой может находиться один из участников. Такимобразом, состояние “помнит”, что одни важные события произошли, а другие — еще нет.Переходы между состояниями в нашем случае совершаются, когда происходит одно изпяти описанных выше событий. События мы будем считать “внешними” по отношению кавтоматам, представляющим трех наших участников, несмотря на то, что каждый из нихможет инициировать одно или несколько из этих событий. Оказывается, важно не то,кому именно позволено вызывать эти события, а то, какие последовательности событиймогут произойти.На рис. 2.1 участники представлены автоматами. На диаграмме показаны лишь те события, которые влияют на того или иного участника.
Например, действие оплата влияетлишь на клиента и магазин. Банк не знает о том, что клиент отправил деньги в магазин;он узнает об этом, когда магазин выполняет действие выкуп.Рассмотрим вначале автомат (в), изображающий банк. Его начальное состояние —это состояние 1. Оно соответствует ситуации, когда банк выпустил денежный файл, о котором идет речь, но еще не получил требования на его выкуп или отмену.
Если клиент2.1. ÍÅÔÎÐÌÀËÜÍÎÅ ÇÍÀÊÎÌÑÒÂÎ Ñ ÊÎÍÅ×ÍÛÌÈ ÀÂÒÎÌÀÒÀÌÈСтр. 5555посылает в банк запрос на отмену, то банк восстанавливает деньги на счету клиента ипереходит в состояние 2. Оно представляет ситуацию, в которой деньги возвращеныклиенту. Поскольку банк в ответе за свои действия, то, попав в состояние 2, он уже непокидает его. Этим он не позволит клиенту вернуть на свой счет с помощью отмены илиизрасходовать те же самые деньги.1Началооплатавыкупabпереводdдоставка(a) магазинcfдоставкаeдоставкаgвыкуппереводвыкуппереводотменаоплатаНачало(b) клиентотменаНачало(c) банкРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
