Советов Б.Я., Яковлев С.А. Моделирование систем (3-е изд., 2001) (1186218), страница 15
Текст из файла (страница 15)
Для автомата Мура аналогичная разметкаграфа такова: если входной сигнал хк, действуя на некоторое состояние автомата, вызывает переход в состояние zjt то дугу, направленную В 2 | Е помеченную хк, дополнительно отмечают выходнымсигналом у=ф (Zj, xk).Таблица 2.3г*Переходыг0ВыходыУгУ\У*.У1У1У1Таблица 2.4*|УУ1г*12ХоУхУзJ»2Уз*1zЧ**z0г0*4*3iг**1*2На рис. 2.3, а, б приведены заданные ранее таблицами F-автоматы Мили F1 и Мура F2 соответственно.При решении задач моделирования систем часто более удобнойформой является матричное задание конечного автомата. При этомматрица соединений автомата есть квадратная матрица С=||су||,строки которой соответствуют исходным состояниям, а столбцы —состояниям перехода. Элемент c,j=xk/ys, стоящий на пересечении i-йстроки и j-ro столбца, в случае автомата Мили соответствует входному сигналу хк, вызывающему переход из состояния z, в состояниеZj, и выходному сигналу ys, выдаваемому при этом переходе.Для автомата Мили F1, рассмотренного выше, матрицасоединений имеет видx—Графы автоматови Мура (б)58с1=—xjy2х2/У1tfiхг\У7—Если переход из состояния z,- в состояние zt происходит поддействием нескольких сигналов, элемент матрицы ctJ представляетсобой множество пар «вход-выход» для этого перехода, соединенных знаком дизъюнкции.Для F-автомата Мура элемент су равен множеству входныхсигналов на переходе (z„ zj), а выход описывается вектором выходовУ =Ф(.*к)1-я компонента которого — выходной сигнал, отмечающий состояние z,.Пример 12.
Для рассмотренного выше F-автомата Мура F2 запишем матрицусоединений и вектор выходов:— х.—— х, —У1У2х,УУ»У*.х,— х.— —УъДля детерминированных автоматов выполняется условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейтиболее чем в одно состояние. Применительно к графическому способу задания F-автомата это означает, что в графе автомата излюбой вершины не могут выходить два ребра и более, отмеченныеодним и тем же входным сигналом. Аналогично этому в матрицесоединений автомата С в каждой строке любой входной сигнал недолжен встречаться более одного раза.Рассмотрим вид таблицы переходов и графа асинхронного конечного автомата.
Для F-автомата состояние zk называется устойчивым, если для любого входа х(еХ, для которого (p(zk, x)=zk,имеет место ф(гк, х)=ук. Таким образом, ^-автомат называетсяасинхронным, если каждое его состояние zkeZ устойчиво.Необходимо отметить, что вообще на практике автоматы всегдаявляются асинхронными, а устойчивость их состояний обеспечивается тем или иным способом, например введением сигналов синхронизации. Однако на уровне абстрактной теории, когда конечный59автомат выступает в виде математической схемы для формализации конкретных объектов без учета ряда второстепенных особенностей, часто удобно оказывается оперировать с синхронными конечными автоматами.Таблица 2.5У*|Рис.
2.4. Граф асинхронного автомата МураЛУгЛ*0*i*1*1*i*i*1*а*зz*г0«1«2*о*2Пример 2.3. Рассмотрим асинхронный F-автомат Мура, который описан табл.2.S и приведен на рис. 2.4. Очевидно, что если в таблице переходов асинхронногоавтомата некоторое состояние z* стоит на пересечении строки Jtj и столбца г, {?Фк),то это состояние гк обязательно должно встретиться в этой же строке в столбце zk.В графе асинхронного автомата, если в некоторое состояние имеются переходы издругих состояний под действием каких-то сигналов, то в вершине z* должна бытьпетля, отмеченная символами тех же входных сигналов.
Анализ табл. 2.3 и 2.4 илирис. 2.3, 6 и 2.4 показывает, что представленные там F-автоматы Fl aF2 являютсясинхронными.Таким образом, понятие F-автомата в дискретно-детерминированном подходе к исследованию на моделях свойств объектов является математической абстракцией, удобной для описания широкогокласса процессов функционирования реальных объектов в автоматизированных системах обработки информации и управления. В качестве таких объектов в первую очередь следует назвать элементыи узлы ЭВМ, устройства контроля, регулирования и управления,системы временной и пространственной коммутации в технике обмена информацией и т.
д. Для всех перечисленных объектов характерно наличие дискретных состояний и дискретный характер работы во времени, т. е. их описание с помощью F-схем являетсяэффективным. Но широта их применения не означает универсальности этих математических схем. Например, этот подход непригоден для описания процессов принятия решений, процессов в динамических системах с наличием переходных процессов и стохастических элементов.2.4. ДИСКРЕТНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ(Р-СХЕМЫ)Рассмотрим особенности построения математических схем придискретно-стохастическом подходе к формализации процесса функционирования исследуемой системы S.
Так как сущность дискрети60зации времени при этом подходе остается аналогичной рассмотренным в § 2.3 конечным автоматам, то влияниефактора стохастичности проследим также на разновидности такихавтоматов, а именно на вероятностных (стохастическиих) автоматах.Основные соотношения. В общем виде вероятностный автомат(англ. probabilistic automat) можно определить как дискретный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памятив нем и может быть описано статистически.Применение схем вероятностных автоматов (Р-схем) имеет важное значение для разработки методов проектирования дискретныхсистем, проявляющих статистически закономерное случайное поведение, для выяснения алгоритмических возможностей таких системи обоснования границ целесообразности их использования, а такжедля решения задач синтеза по выбранному критерию дискретныхстохастических систем, удовлетворящих заданным ограничениям.Введем математическое понятие Р-автомата, используя понятия, введенные для F-автомата.
Рассмотрим множество G, элементами которого являются всевозможные пары (xh zt), где х( и z, —элементы входного подмножества X и подмножества состоянийZ соответственно. Если существуют две такие функции q> и ф, тос их помощью осуществляются отображения G-*Z и G->Y, тоговорят, что F= <Z, X, Y, <р, фУ определяет автомат детерминированного типа.Введем в рассмотрение более общую математическую схему.Пусть Ф — множество всевозможных пар вида (zk, у}, где ys —элемент выходного подмножества Y. Потребуем, чтобы любойэлемент множества G индуцировал на множестве Ф некоторыйзакон распределения следующего вида:Элементы из Ф •••К(zla yj... (г^ у2)...•••(zjojyy-i)(z^ yj)JПри этом Y, Z **/= 1» г д е by — вероятности перехода автомата в состояние zk и появления на выходе сигнала yit если он былв состоянии zs и на его вход в этот момент времени поступил сигналх,.
Число таких распределений, представленных в виде таблиц,равно числу элементов множества G. Обозначим множество этихтаблиц через В. Тогда четверка элементов P=<Z, X, У, ВУ называется вероятностным автоматом (Р-автоматом).Пусть элементы множества G индуцируют некоторые законыраспределения на подмножествах Y и Z, что можно представитьсоответственно в виде:61Элементы из К(*(.*,)Элементы из 2(*(.*»)•••—••••••у1?!гхz,у2q2z2г2••••••••••••У]-\? y _izc_,г с _!ytq,zrzrПри этом YJ zk=l и £ ?*=!> ГДе г* и Як — вероятности перехоJk-lk-\да Р-автомата в состояние zk и появления выходного сигнала ук приусловии, что Р-автомат находился в состоянии z, и на его входпоступил входной сигнал х,.Если для всех к и у имеет место соотношение qkZi=bkJ, то такойР-автомат называется вероятностным автоматом Мили.
Это требование означает выполнение условия независимости распределений для нового состояния Р-автомата и его выходного сигнала.Пусть теперь определение выходного сигнала Р-автомата зависит лишь от того состояния, в котором находится автома*т в данномтакте работы. Другими словами, пусть каждый элемент выходногоподмножества Y индуцирует распределение вероятностей выходов,имеющее следующий вид:Элементы из УZt•••уху2•••yK-iyg•••5S2•••J;_jSjtIЗдесь £ st=l, где s( — вероятность появления выходного сигнала у, при условии, что Р-автомат находился в состоянии zk.Возможные приложения.
Если для всех к и i имеет место соотношение zkSj=bkh то такой Р-автомат называется вероятностнымавтоматом Мура. Понятие Р-автоматов Мили и Мура введено поаналогии с детерминированным F-автоматом, задаваемым P=<Z,X, Y, Ф, фу. Частным случаем Р-автомата, задаваемого как P=(JZ,X, Y, B\ являются автоматы, у которых либо переход в новоесостояние, либо выходной сигнал определяются детерминированно.Если выходной сигнал Р-автомата определяется детерминированно,то такой автомат называется Y-детерминированным вероятностным автоматом.
Аналогично, Z-demepминированным вероятностным автоматом называется Р-автомат, у которого выбор новогосостояния является детерминированным.Пример 2.4 Рассмотрим У-детерминированный Р-автомат, который задан таблицей переходов (табл.
2.6) и таблицей выходов:Z . . . . Zji2 . . . . zk_tzkУ . . . . ^,iу,г • • • у,к-\у,кВ этих таблицах рц — вероятность перехода Р-автомата из состояния г, в состояние Zj. При этом, как и ранее, £ p,j= 1.62Первую из этих таблиц можно представить в виде квадратной матрицыразмерности КхК, которую будем называть матрицей переходных вероятностейили просто матрицей переходов Р-автомата. В общем случае такая матрицапереходов имеет видРиРиPIE.PnPnPinРиРиРиР,=Таблица 2.6**4fc«1Л*1РиРиРиРиРчРч1*1-1нPi (Х-1)Pi (Г- 1)Pit.PlKPi (*-»РчкДля описания У-детерминированното Р-автомата необходимо задать начальное распределение вероятностей видаz2 . . . .
1'ii*t-iD .rf,d2dK-iЗдесь dt — вероятность того, что в начале работы Р-автомат находится в состояниик. При этом £dk=\.Будем считать, что до начала работы (до нулевого такта времени) Р-автоматвсегда находится в состоянии z0 и в нулевой такт времени меняет состояние в соответствии с распределением D. Дальнейшая смена состояний Р-автомата определяется матрицей переходов РР. Информацию о начальном состоянии Р-автомата удобно•нести в матрицу Рр, увеличив ее размерность до (АГ+1)х(ЛГ+1).
При этом перваястрока такой матрицы, сопоставляемая состоянию г„, будет иметь вид (0, dlt d2, ...„., dK), а первый столбец будет нулевым.Описанный У-детермивированный Р-автомат можно задать в виде ориентированного графа, вершины которого сопоставляются состояниям автомата, а дуги —возможным переходам из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода p,j, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями.Пример US.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
