Зенкевич_Упр.манип_03 (962916), страница 28
Текст из файла (страница 28)
Таким образом, будем предполагать, что сетевой автомат генерирует символ в выходной канал не одновре- менно с приходом входного символа (как это было для абстрактного конечного автомата), а одновременно с достижением нового состояния. Такая интерпретация позволит нам в дальнейшем избежать «момен- тальной зависимости».
Поскольку зто достаточно важно, проиллюст- рируем работу сетевого автомата (с одним входом и одним выходом), построив его модель в виде сети Петри 15б1. На рис. 9.12 представлена модель сетевого автомата в виде секи Петри. Позиции и переходы ин- терпретируются здесь следующим образом: р, — ожидание прихода входного символа; — получен входной символ; р, — — переход в следующее состояние; — генерация выходного символа; автомат находится в новом состоянии„. ~.73 истОчник ВхОдных симВОДОВ р, — накопитель выходных символов.
Рис. 9Л2. Модель сетевого ввтомвтв с одним входом и одним выходом Если в некотором состоянии автомата присутствует переход по пустому символу а, то в его представлении в виде сети Петри отсутствует позиция р,. Аналогично обстоит дело с пустым выходным сим- волом а: в этом случае отсутствует позиция р,. Рассмотрим еще одну интерпретацию сетевого автомата с р входами и с1 выходами, которая понадобится в дальнейшем ~4$ Будем интерпретировать сетевой автомат как устройство (рис.
9.13)„состоящее из: — управлякнцего блока; — полубесконечной входной ленты (гзлента), разделенной на ячейки, каждая из которых содержит символ обобщенного входного алфавита (слово записывается слева направо); — полубесконечной выходной ленты ~о-лента), разделенной на ячейки; — р читающих головок; — 9 записывающих головок. Находясь в состоянии х, автомат обозревает входную ленту так, что каждая его читающая головка, связанная с каналом ~ н 1., находится над ячейкой ленты, содержащей символ нл. После чтения символа автомат переходит в новое состояние у и на выходную ленту записывается и и И'.
Читающие головки, связанные с каналами из 1,, перемещаются вправо до тех пор, пока под каждой из них не окажется символ из Г с соответствующим номером канала. 364 нвк Ьг маинм ВхаЬяя ясна мдха я гряяВха ВыхяВяая яеяаа надва~ ас Рис. 9ЛЗ. Модель сетевого автомата как читающее — записывающее устройство Итак, сформулировав все основные определения, перейдем к построению сети автоматов. 9.5.
Сеть автоматов В этом параграфе мы построим сеть автоматов, т.е. набор автоматов, объединенных своими входами и выходами и взаимодействующих путем передачи и приема символов своих входных — выходных алфавитов по общим каналам. Рассмотрим предварительно механизм взаимодействия введенных выше автоматов при их элементарных соединениях.
9.5.1. Последовательное соединение сетевых автоматов Пусть два автомата (см. (9.16)) )ч(А,. = (1,, О,, У,, Х,, 7,, /;., Ь,), 1= 1, 2, соединены так, как это показано на рис. 9.14, т.е. подмножество выходов О,' с: О, автомата )чА, соединено с подмножеством входов 1, "~ 1, автомата ХА,. Будем далее считать, что 1, И У, = О, П О, = О. Если эти условия не выполняются, тогда переименуем соответствующие каналы.
Отметим одно обстоятельство. Пусть клетки на ленте пронумерованы (см. рис. 9.13), и и,", — положение головки т автомата А, и е (г, ьр), А н 11ЧА„1чА, ) . Тогда нетрудно увидеть, что в соответствии с введенной выше интерпретацией выполняется соотношение (9.19) означающее, что читающая головка г автомата )чА, никогда не обгонит записывающую головку и автомата 1чА,. На рис. 9.15 представле- на модель взаимодействия автоматов в виде сети Петри. Позиция р„ служит для передачи сообщений от )чА, к ИАт. Рис. 9.14.!!оследовательное соединение сетевых автоматов Рис. 9.15. Модель взаимодействия последовательно соединенных автоматов в виде сети Пстри Соотношение (9.19) устанавливает минимальное расстояние между головками взаимодействующих автоматов.
Однако имеет смысл рассмотреть вопрос о максимальном расстоянии. Прикладная сторона этого вопроса состоит в следующем. При программной реализации автоматов используют Г1ГО-очереди в качестве механизма обмена данными, и тогда максимальное расстояние между читающей и записывающей головкой автоматов ХА, и ИА, равно длине очереди, которую необходимо зарезервировать при генерации автоматной сети. Покажем теперь, что можно построить сетевой автомат ХА = (1, О, Х, У, ~, Ь), такой, что его поведение будет совпадать с поведением последовательно соединенных 1ЧА, и ХА,. Под эквивалентностью здесь и далее будем понимать совпадение отображений обобщенный вход — обобщенный выход. Прежде всего укажем на одну специфическую особенность рассматриваемой проблемы.
Автоматы МА, и ИА2 могут являться моделями различных устройств: в частности, если МА, моделирует медленное (по сравнению с ИА2) устройство, то с момента поступления на вход )т(А, некоторого символа до момента поступления вызванной им реакции на вход )т(А2 последний может неоднократно поменять свое состояние за счет поступления на его внешние входы некоторых допустимых в данном состоянии символов. (Это обстоятельство убедительно иллюстрируется сетью Петри, представленной на рис. 9.15, если пополнить ее позициями, имитирующими входные символы, которые поступают по внешним каналам.
Тогда разметка такой сети может меняться за счет изменения разметки только модели ИА2.) Учет этого эффекта чрезвычайно важен для практических приложений. Для учета этого обстоятельства поступим следующим образом. Пусть х — состояние )т1А, такое, что у= Г(х,и) и х=т2(х, и) (входные и выходные каналы сейчас неважны, поэтому их опускаем). Тогда введем дополнительное (транзитное) состояние ху, обладающее следующим своиством ху Х(х~ и) ° е 22(х и) ~ у .Г(х)» е) ° х 72(хуз е) ° Соответствующая иллюстрация приведена на рис. 9.16. Заметим при этом, что пребывая в состоянии ху автомат ИА не реагирует на остальные входы, как это, возможно, было в состоянии х, т.е. переход х -+ ху-+у неделим для данного автомата.
Вообще говоря, именно такая интерпретация поведения автомата принята при описании его сетью Петри (рис. 9.15). Рис. 9Л б. Введение товнзитното состояния Пусть теперь автоматы 1МА, и 1'(А2 преобразованы так„как сказано выше. Построим эквивалентный )т(А в соответствии со следующей процедурой свертки.
Шаг 1. Построение объединенного автомата. Построим ИА = (1, О, (', Х, ~, Ь), где 1 ()( 2 2)' о=(о, -о,')Оо;, ~'! (-) ~' 2' Х=Х, хХ,. (920) Функции переходов и выходов строятся следующим образом. Пусть х=(р, д) и у=(», х), х, уеХ„. Тогда (х,1) — ~+~у, если (р, ~) — «~-+» либо (д, ~) 1х — + з. Аналогично строится 6: (х, г) — ' — + и, если (р, ю) — "-' — + и либо (9, ю) — "-' — + и . Шаг 2.
Свертка дуг. Построим теперь автомат г1А, отличающийся от ХА лишь ото- бражениями 1 и Ь. Пусть отображения )" н Ь автомата |чА содер- жат следующие отображения: (х, ~) — +у, (х, ~) — +а, (у,а) — ~ — эх, (у, а) — "— +а. (9.21) Тогда дополним 1' н Ь следующими элементами: (х, ю) -+ х, (х, г) -+ в. (9.22) (Здесь, к сожалению, нельзя внести композицию отображений, по- скольку функции 1,, Ь, и ~~, Ь, имеют„вообще говоря„попарно раз- ные области определения из-за наличия внешних входов.) Выполняя эту процедуру для всех элементов отображений 1 и Ь, удовлетворяющих условиям (9.21), получаем отображения 1 и Ь .
Шаг 3. Удаление внутренних дуг. Этот шаг в построении автомата 1ЧА состоит в удалении дуг, со- держащих ссылки на внутренние каналы, соединяющие ИА, и ХА,. Более точно это означает следующее. Если отображение 1 содержит элементы (х, и, () -+ у, где г и 1,', то онн удаляются. Аналогично, если Ь содержит отображение (х, и, ()-+(х, о), где либо ~а 1,', либо он О,', то оно удаляется. Шаг 4.
Минимизация. Здесь осуществляется стандартная процедура, минимизирующая число состояний сетевого автомата. Полученные в результате отобра- жения 1 и Ь являются искомыми функциями переходов и выходов ав- томата 1чА. Зб8 Итак, описанная процедура свертки является корректной в том смысле, что атрибуты полученного автомата ХА не зависят от порядка, в котором строятся дополнительные дуги на втором шаге, Заметим„что полученный автомат может быть недетерминированным, даже если оба автомата 1ЧА, и Ь1А, детерминированы.
(а1 (б] Рис. 9Л7. два послсдователвно соединенных сетевых автомата: а — топология; б, в — графы А и В;; д — - модифипированныс графы автоматов А и В П р и м е р 9.3. Рассмотрим пример применения описанной процедуры свертки двух последовательно соединенных автоматов А и В, изображенных на рис. 9.17, а. Их графы переходов — выходов, а также модифицированные графы представлены на рис. 9.17 б, в и г, д соответственно. Результирующий автомат показан на рис. 9.18. Пусть аЬ— начальное состояние автомата АВ (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
