dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 13
Текст из файла (страница 13)
2.1. Конечные автоматы, представляющие клиента, магазин и банкС другой стороны, находясь в состоянии 1, банк может получить от магазина требование выкупа денег. В этом случае он переходит в состояние 3 и тут же отправляет магазину сообщение о переводе, в котором содержится новый денежный файл, принадлежащий уже магазину. Отослав это сообщение, банк переходит в состояние 4. В этом состоянии он не принимает запросов на отмену или выкуп денег, равно как не совершаетникаких других действий с этим конкретным денежным файлом.Рассмотрим теперь автомат на рис. 2.1, а, представляющий действия магазина. В товремя как банк всегда работает безукоризненно, в системе работы магазина есть изъяны.Представьте, что доставка товара и финансовые операции совершаются отдельно друг от1Нужно помнить, что тут речь идет об одном денежном файле.
На самом деле, банк будет работать по такому же протоколу с большим количеством единиц электронных денег. При этом всякий раз протокол работы с каждой такой единицей — один и тот же, поэтому мы можем рассматривать данную проблему так, как если бы существовала всего одна единица электронных денег.56Стр. 56ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛдруга.
Тогда доставка может быть выполнена до, во время или после выкупа электронных денег. Придерживаясь такой политики, магазин рискует попасть в ситуацию, когдатовар уже доставлен, а деньги, как выясняется, поддельные.Магазин начинает в состоянии a. Когда покупатель заказывает товар, выполняя оплату, магазин переходит в состояние b. В этом состоянии магазин начинает одновременно два процесса: доставку товара и выкуп денег. Если первым заканчивается процессдоставки, то магазин переходит в состояние c, в котором он еще должен осуществитьвыкуп денег и получить перевод эквивалентного денежного файла из банка. Магазинтакже может сначала отправить в банк запрос на выкуп денег и перейти в состояние d.
Всостоянии d магазин либо доставит товар и перейдет в состояние e, либо получит из банка денежный перевод и перейдет в состояние f. Следует ожидать, что в состоянии f магазин в конце концов доставит товар и перейдет в состояние g. В последнем случае сделказавершена, и ничего больше не происходит.
В состоянии e магазин ожидает перевода денег из банка. К сожалению, может получиться, что магазину не повезет: товар он доставит, а денежного перевода так никогда и не получит.Рассмотрим, наконец, автомат на 2.1, б, изображающий клиента. У этого автоматаесть только одно состояние, отражающее тот факт, что клиент может делать все, чтоугодно. Он может выполнять оплату или отмену сколько угодно раз и в любом порядке.При этом после каждого действия он остается в своем единственном состоянии.2.1.3. Âîçìîæíîñòü èãíîðèðîâàíèÿ àâòîìàòîì íåêîòîðûõ äåéñòâèéТройка автоматов на рис.
2.1 отображает поведение участников независимо друг отдруга, однако некоторые переходы в автоматах пропущены. Так, сообщение об отмене денег не затрагивает магазин, и если клиент отменяет деньги, то магазин должен оставаться втом же состоянии, в котором находился. Однако согласно формальному определению конечного автомата, которое мы рассмотрим в разделе 2.2, если на вход автомата подается X,то он должен совершить переход по дуге с меткой X из текущего состояния в некоторое новое. Следовательно, к каждому состоянию автомата для магазина нужно добавить еще однудугу с меткой отмена, ведущую в то же состояние.
Тогда при выполнении отмены автомат, изображающий магазин, может совершить “переход”, который состоит в том, что автомат остается в том же состоянии, в котором и был. Если бы этих дополнительных дуг небыло, то автомат, изображающий магазин, “умирал” бы, т.е. он не находился бы ни в какомсостоянии, и любые его последующие действия были бы невозможны.Еще одна потенциальная проблема кроется в том, что участники могут, умышленноили случайно, отправить сообщение, не предусмотренное протоколом, и мы не хотим,чтобы это повлекло “смерть” одного из автоматов. Представим, например, что клиентвыполнил действие оплата во второй раз, когда магазин находился в состоянии e.
Поскольку это состояние не имеет выходящей дуги с меткой оплата, то автомат, изображающий магазин, умрет прежде, чем получит перевод из банка. Итак, к некоторым со2.1. ÍÅÔÎÐÌÀËÜÍÎÅ ÇÍÀÊÎÌÑÒÂÎ Ñ ÊÎÍÅ×ÍÛÌÈ ÀÂÒÎÌÀÒÀÌÈСтр. 5757стояниям автоматов на рис. 2.1 нужно добавить петли с метками, обозначающими действия, которые следует проигнорировать в этих состояниях. Дополненные таким образомавтоматы изображены на рис.
2.2. Для экономии места дуги с разными метками, имеющие начало и конец в одном и том же состоянии, объединяются в одну дугу с несколькими метками. Игнорироваться должны следующие два типа действий.отменаоплата, отменаоплата, отменаоплата, отменаbdfНачалоaоплатавыкупдоставка(a) магазинcдоставкавыкупоплата, отменапереводeдоставкапереводоплата, отменаgоплата, отменаоплата, доставкадоставка, выкуп,перевод, оплата, отменаотменаоплата,доставкаНачало(b) клиентоплата, выкуп,отмена, доставкавыкупоплата, выкуп,отмена, доставкапереводНачало(c) банкРис. 2.2.
Полные множества переходов для трех автоматов1.Действия, не затрагивающие данного участника. Как мы видели, для магазина единственным таким действием является отмена, поэтому каждое его состояние имеетпетлю с меткой отмена. К банку не имеют отношения ни оплата, ни доставка, а потому к каждому из его состояний добавляется петля с метками оплата и доставка.Клиента не затрагивают доставка, выкуп и перевод, и мы добавляем дуги с такимиметками. В итоге, какая бы последовательность действий ни была подана на вход, оностается в своем единственном состоянии. Поэтому на операции, совершаемые системой в целом, автомат клиента не влияет. Безусловно, клиент остается участником, таккак именно он инициирует действия оплата и отмена.
Но, как мы уже говорили, дляповедения автоматов неважно, кто именно инициирует те или иные действия.2.Действия, которые не следует допускать во избежание смерти автомата. Какупоминалось ранее, чтобы не убить автомат магазина, нельзя позволять покупателюповторно выполнять оплату. С этой целью добавлены петли с меткой оплата ко58Стр. 58ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛвсем его состояниям, за исключением состояния a (в котором действие оплата уместно и ожидаемо). Кроме того, добавлены петли с меткой отмена к состояниям 3 и 4банка для того, чтобы не допустить смерти автомата банка, если покупатель попытается отменить деньги, которые уже были выкуплены.
Банк с полным правом игнорирует такое требование. Точно так же состояния 3 и 4 имеют петли с меткой выкуп.Магазин не должен пытаться дважды выкупить одни и те же деньги. Но если он всеже делает это, то банк совершенно справедливо игнорирует второе требование.2.1.4. Ñèñòåìà â öåëîì êàê àâòîìàòОбычный способ изучения взаимодействия подобных автоматов состоит в построениитак называемого автомата-произведения. Состояниями этого автомата являются пары состояний, первое из которых есть состояние магазина, а второе — состояние банка. Например, состояние автомата-произведения (3, d) представляет ситуацию, когда банк находитсяв состоянии 3, а магазин — в состоянии d.
Поскольку магазин имеет четыре состояния, абанк — семь, то число состояний автомата-произведения равно 4×7 = 28.Данный автомат-произведение изображен на рис. 2.3. Для ясности все 28 состоянийрасположены в виде массива, строки которого соответствуют состояниям банка, а столбцы — состояниям магазина. Кроме того, в целях экономии места дуги помечены буквами, каждая из которых соответствует определенному действию: P — оплата (pay), S —доставка (ship), C — отмена (cancel), R — выкуп (redeem), T — перевод (transfer).Чтобы правильно построить дуги в автомате-произведении, нужно проследить“параллельную” работу автоматов банка и магазина. Каждый из двух компонентов автомата-произведения совершает, в зависимости от входных действий, различные переходы.Важно отметить, что если, получив на вход некоторое действие, один из этих двух автоматов не может совершить переход ни в какое состояние, то автомат-произведение“умирает”, поскольку также не может перейти ни в какое состояние.Придадим строгость правилу переходов из одного состояния в другое.
Рассмотримавтомат-произведение в состоянии (i, x). Это состояние соответствует ситуации, когдабанк находится в состоянии i, а магазин — в состоянии x. Пусть Z означает одно извходных действий. Мы смотрим, имеет ли автомат банка переход из состояния i с меткой Z. Предположим, что такой переход есть, и ведет он в состояние j (которое можетсовпадать с i, если банк, получив на вход Z, остается в том же состоянии). Затем, глядяна автомат магазина, мы выясняем, есть ли у него дуга с меткой Z, ведущая в некоторое состояние y. Если j и y существуют, то автомат-произведение содержит дугу из состояния (i, x) в состояние (j, y) с меткой Z.
Если же либо состояния j, либо состояния yнет (по той причине, что банк или магазин для входного действия Z не имеет, соответственно, перехода из состояния i или x), то не существует и дуги с меткой Z, выходящей из состояния (i, x).2.1. ÍÅÔÎÐÌÀËÜÍÎÅ ÇÍÀÊÎÌÑÒÂÎ Ñ ÊÎÍÅ×ÍÛÌÈ ÀÂÒÎÌÀÒÀÌÈСтр. 5959Начало1234Рис. 2.3. Автомат-произведение для магазина и банкаТеперь ясно, каким образом выбраны дуги на рис. 2.3. Например, получая на входдействие оплата, магазин совершает переход из состояния a в состояние b, а из любогодругого состояния — в него же. Банк же, получая на вход действие оплата, в любомслучае сохраняет свое состояние, поскольку это действие его не затрагивает. Эти наблюдения объясняют, как были построены четыре дуги с меткой P в четырех столбцахрис.
2.3 и петли с меткой P для других состояний.Еще один пример выбора дуг мы получим, рассмотрев действие выкуп. Если банк получит запрос на выкуп, находясь в состоянии 1, то он перейдет в состояние 3, а если в состоянии 3 или 4 — останется в том же состоянии. Если же он получит это действие навход, находясь в состоянии 2, то “умрет”, т.е. не сможет никуда перейти. С другой стороны, магазин, получив на вход выкуп, может из состояния b перейти в d или из c в e. Нарис. 2.3 мы видим шесть дуг с меткой выкуп, соответствующих шести комбинациям изтрех состояний банка и двух состояний магазина, имеющих выходящие дуги с меткой R.Например, из состояния (1, b) дуга с меткой R переводит автомат в состояние (3, d), таккак выкуп переводит банк из состояния 1 в 3, а магазин — из b в d.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
