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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Действия, не затрагиваюигие данного участника, Как мы видели, для магазина единственным таким действием является отмена, поэтому каждое его состояние имеет петлю с меткой отмена. К банку не имеют отношения ни оплата, ни доставка, а потому к каждому из его состояний добавляется петля с метками оняата и доставка. Клиента не затрагивают доставка, выкуп и перевод, и мы добавляем дуги с такими метками. В итоге, какая бы последовательность действий ни была подана на вход, ои остается в своем единственном состоянии.

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

2,1 нужно добавить петли с метками, обозначающими действия, которые следует проигнорировать в этих состояниях. Дополненные таким образом автоматы изображены на рис. 2.2, Для экономии места дуги с разными метками, имеющие начало и конец в одном и том же состоянии, объединяются в одну дугу с несколькими метками. Игнорироваться должны следующие два типа действий. всем его состояниям, за исключением состояния а (в котором действие оплата уместно и ожидаемо). Кроме того, добавлены петли с меткой онсмена к состояниям 3 и 4 банка для того, чтобы не допустить смерти автомата банка, если покупатель попытается отменить деньги, которые уже были выкуплены.

Банк с полным правом игнорирует такое требование. Точно так же состояния 3 и 4 имеют петли с меткой выкуп. Магазин не должен пытаться дважды выкупить одни и те же деньги. Но если он все же делает это, то банк совершенно справедливо игнорирует второе требование.

2.1.4. Система в целом как автомат Обычный способ изучения взаимодействия подобных автоматов состоит в построении так называемого автомата-произведеник. Состояниями этого автомата являются пары состояний, первое из которых есть состояние магазина, а второе — состояние банка. Например, состояние автомата-произведения (3, д) представляет ситуацию, когда банк находится в состоянии 3, а магазин — в состоянии а'. Поскольку магазин имеет четыре состояния, а банк — семь, то число состояний автомата-произведения равно 4х7 = 28, Данный автомат-произведение изображен на рис.

2.3. Для ясности все 28 состояний расположены в виде массива, строки которого соответствуют состояниям банка, а столбцы — состояниям магазина. Кроме того, в целях экономии места дуги помечены буквами, каждая из которых соответствует определенному действию: Р— оплата (рау), 5— доставка (заир), С вЂ” от мена (саисеГ), Š— выкуп (гейеет), Т вЂ” перевод (гкап~ее) . Чтобы правильно построить дуги в автомате-произведении, нужно проследить "параллельную" работу автоматов банка и магазина. Каждый из двух компонентов автомата-произведения совершает, в зависимости от входных действий, различные переходы. Важно отметить, что если, получив на вход некоторое действие, один из этих двух автоматов не может совершить переход ни в какое состояние, то автомат-произведение 'Умирает", поскольку также не может перейти ии в какое состояние.

Придадим строгость правилу переходов из одного состояния в другое. Рассмотрим автомат-произведение в состоянии (б х). Это состояние соответствует ситуации, когда банк находится в состоянии 1, а магазин — в состоянии х. Пусть У означает одно из входных действий. Мы смотрим, имеет ли автомат банка переход из состояния ~' с меткой 2. Предположим, что такой переход есть, и ведет он в состояние7' (которое может совпадать с б если банк, получив на вход 2, остается в том же состоянии). Затем, глядя на автомат магазина, мы выясняем, есть ли у него дуга с меткой 2, ведущая в некоторое состояние у. Если/ и у существуют, то автомат-произведение содержит дугу из состояния (б х) в состояние 0', у) с меткой 2.

Если же либо состояния7', либо состояния у нет(по той причине, что банк или магазин для входного действия 2 не имеет, соответственно, перехода из состояния ~' или х), то не существует и дуги с меткой 2, выходящей из состояния (б х). 2.Ь НЕФОРМАЛЬНОЕ ЗНАКОМСТВО С КОНЕЧНЫМИ АВТОМАТАМИ Начала С Р,С Р, С Р, С Р, С Р, С Р, С Рис. 23. Аетомат-произведение для магазина и банка Теперь ясно, каким образом выбраны дуги на рис. 2.3. Например, получая на вход действие оплата, магазин совершает переход из состояния а в состояние Ь, а из любого другого состояния — в него же. Банк же, получая на вход действие оплата, в любом случае сохраняет свое состояние, поскольку это действие его не затрагивает.

Эти наблюдения объясняют, как были построены четыре дуги с меткой Р в четырех столбцах рис. 2.3 и петли сметкой Р для других состояний. Еше один пример выбора дуг мы получим, рассмотрев действие выкуп. Если банк получит запрос на выкуп, находясь в состоянии 1, то он перейдет в состояние 3, а если в состоянии 3 или 4 — останется в том же состоянии. Если же он получит зто действие на вход, находясь в состоянии 2, то "умрет", т.е.

не сможет никуда перейти. С другой стороны, магазин, получив на вход выкуп, может из состояния Ь перейти в е1 или из с в е. На рис. 2.3 мы видим шесть дуг с меткой выкуп, соответствующих шести комбинациям из трех состояний банка и двух состояний магазина, имеющих выходящие дуги с меткой )1. Например, из состояния 11, Ь) дуга с меткой Я переводит автомат в состояние (3, е)), так как выкуп переводит банк из состояния 1 в 3, а магазин — из Ь в Ы. Еще один пример: существует дуга с меткой )1, ведущая из состояния (4, с) в (4, е), поскольку выкуп переводит банк из состояния 4 снова в состояние 4, а магазин — из с в е. ГЛАВА 2. КОНЕЧНЬЖ АВТОМАТЫ 60 2.1.5.

Проверка протокола с помощью автомата-произведения Из рис. 2.3 можно узнать кое-что интересное. Так, из начального состояния (1, а)— комбинации начальных состояний банка и магазина — можно попасть только в десять из всех 28 состояний. Заметим, что такие состояния, как (2, е) и (4, а), не являются досгиижииыми, т.е. пути, ведущего к ним нз начального состояния, не существует.

Нет надоб- ности включать в автомат недостижимые состояния, н в нашем случае это сделано ис- ключительно для последовательности изложения. Однако реальной целью анализа протоколов, подобных данному, с помощью автоматов является ответ на вопрос: "возможна ли ошибка данного типа?". Простейший при- мер: нас может интересовать, возможно ли, что магазин доставит товар, а оплаты за него так и не получит, т.е. может ли автомат-произведение попасть в состояние, в котором магазин уже завершил доставку (и находится в одном из состояний в столбцах с, е или 8), и при этом перехода, соответствующего входу Т, никогда ранее не было и не будет. К примеру, в состоянии (3, е) товар уже доставлен, но переход в состояние (4, д), соответствующий входу Т, в конце концов произойдет.

В терминах действий банка это означает, что если банк попал в состояние 3, то он уже получил запрос на выкуп и обработал его. Значит, он находился в состоянии 1 перед получением этого запроса, не получал требования об отмене и будет игнорировать его в будущем. Таким образом, в конце концов банк переведет деньги магазину. Однако в случае состояния (2, в) мы сталкиваемся с проблемой. Состояние достижимо, но единственная выходящая дуга ведет в него же. Это состояние соответствует ситуации, когда банк получил сообщение об отмене раньше, чем запрос на выкуп.

Но магазин получил сообщение об оплатив, т.е. наш пройдоха-клиент одни и те же деньги и потратил, и отменил. Магазин же, по глупости, доставил товар прежде, чем попытался выкупить деньги. Теперь, если магазин выполнит запрос на выкуп, то банк даже не подтвердит получение соответствующего сообщения, так как после отмены, находясь в состоянии 2, банк не будет обрабатывать запрос на выкуп. 2.2.

Детерминированные конечные автоматы Теперь пора ввести формальное понятие конечного автомата и уточнить рассуждения и описания из разделов 1.1.! и 2.1. Начнем с рассмотрения формализма детерминированного конечного автомата, который, прочи~ав любую последовательность входных данных, может находиться только в одном состоянии. Термин "детерминированный'* говорит о том, что для всякой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти нз текущего.

В противоположность детерминированному, "недетерминированный" конечный автомат, который рассматривается в разделе 2,3, может находиться сразу в нескольких состояниях. Под термином "конечный автомат" далее подразумевается автомат детерминированного типа. Но 2.2. ДЕТЕРМИНИРОВАННЫЕ КОНЕЧНЫЕ АВТОМАТЫ обычно для того, чтобы напомнить читателю, автомат какого типа рассматривается, употребляется слово "летерминированный" или сокращение ДКА (РЕА — Г)езегш1п1яг(с Е|пие Ацгоша1оп). 2.2.1.

Определение детерминированного конечного автомата Детермшшрованный конечный автомат состоит из следующих компонентов. 1, Конечное множество состояний, обозначаемое обычно как Д. 2. Конечное множество входных символов, обозначаемое обычно как Х. 3. Функция переходов, аргументами которой являются текущее состояние и входной символ, а значением — новое состояние. Функция переходов обычно обозначается как Б Представляя нестрого автомат в виде графа, мы изображали д отмеченными дугами, соединяющими состояния. Если д — состояние и а — входной символ, то 4д, а) — это состояние р, для которого существует дуга, отмеченная символом а и ведущая из с) в р. 4.

Характеристики

Список файлов книги