Возможные приложения.

Чтобы задать конечный Р-автомат, необходимо описать все элементы множества <2, X, У, , ф, г0>,

т. е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов, причем среди множества состояний необходимо выделить состояние г0, в котором автомат находился в момент времени г=0. Существует несколько способов задания работы Р-автоматов, но наиболее часто используются табличный, графический и матричный.

Простейший табличный способ задания конечного автомата основан на использовании таблиц переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы — его состояниям. При этом обычно первый слева столбец соответствует начальному состоянию г0. На пересечении /-й строки и к-го столбца таблицы переходов помещается соответствующее значение (р {гк, х,) функции переходов, а в таблице выходов — соответствующее значение ф(гкух^ функции выходов. Для Р-автомата Мура обе таблицы можно совместить, получив так называемую отмеченную таблицу переходов, в которой над каждым состоянием гк автомата, обозначающим столбец таблицы, стоит соответствующий этому состоянию, согласно (2.17), выходной сигнал ф (г().

Описание работы Г-автомата Мили таблицами переходов ср и выходов ф иллюстрируется табл. 2.1, а описание Г-автомата Мура — таблицей переходов (табл. 2.2).

Таблица 2.1

Примеры табличного способа задания Г-автомата Мили П с тремя состояниями, двумя входными и двумя выходными сигналами приведены в табл. 2.3, а для Г-автомата Мура — в табл. 2.4.

При другом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал хк вызывает переход из состояния г, в состояние то на графе автомата дуга, соединяющая вершину 2, с вершиной обозначается хк. Для того чтобы задать функцию выходов, дуги графа необходимо отметить соответствующими выходными сигналами. Для автоматов Мили эта разметка производится так: если входной сигнал хк действует на состояние г то, согласно сказанному, получается дуга, исходящая из г{ и помеченная хк эту дугу дополнительно отмечают выходным сигналом у = фь д:*). Для автомата Мура аналогичная разметка графа такова: если входной сигнал хку действуя на некоторое состояние автомата, вызывает переход в состояние г/, то дугу, направленную в и помеченную дополнительно отмечают выходным сигналом у—ф(г^ хк).

Таблица 2.3

На рис. 2.3, а, б приведены заданные ранее таблицами Р-авто маты Мили Р1 и Мура Р2 соответственно.

При решении задач моделирования систем часто более удобной формой является матричное задание конечного автомата. При этом матрица соединений автомата есть квадратная матрица С=||су||, строки которой соответствуют исходным состояниям, а столбцы — состояниям перехода. Элемент Су=хк5, стоящий на пересечении *-й строки и /-го столбца, в случае автомата Мили соответствует входному сигналу хку вызывающему переход из состояния г, в состояние

и выходному сигналу выдаваемому при этом переходе. Для автомата Мили Р1, рассмотренного выше, матрица соединений имеет вид

Рис. 2.3. Графы автоматов Мили (а) и Мура (б)

Если переход из состояния г, в состояние происходит под действием нескольких сигналов, элемент матрицы си представляет собой множество пар "вход-выход" для этого перехода, соединенных знаком дизъюнкции.

Для Р-автомата Мура элемент с равен множеству входных сигналов на переходе (г*, а выход описывается вектором выходов

/-я компонента которого — выходной сигнал, отмечающий состояние Г,.

Пример 2.2. Для рассмотренного выше Р-автомата Мура /2 запишем матрицу соединений и вектор выходов:

Для детерминированных автоматов выполняется условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Применительно к графическому способу задания Р-автомата это означает, что в графе автомата из любой вершины не могут выходить два ребра и более, отмеченные одним и тем же входным сигналом. Аналогично этому в матрице соединений автомата С в каждой строке любой входной сигнал не должен встречаться более одного раза.

Рассмотрим вид таблицы переходов и графа асинхронного конечного автомата. Для /'-автомата состояние гк называется устойчивым, если для любого входа х^Х, для которого (г*, х)=гк, имеет место ф(гк, х,)=ук. Таким образом, /'-автомат называется асинхронным, если каждое его состояние zkeZ устойчиво.

Необходимо отметить, что вообще на практике автоматы всегда являются асинхронными, а устойчивость их состояний обеспечивается тем или иным способом, например, введением сигналов синхронизации. Однако на уровне абстрактной теории, когда конечный автомат выступает в виде математической схемы для формализации конкретных объектов без учета ряда второстепенных особенностей, часто удобно оказывается оперировать с синхронными конечными автоматами.

Таблица 2.5

Рис. 2.4. Граф асинхронного автомата Мура

Пример 2.3. Рассмотрим асинхронный Р-автомат Мура, который описан табл. 2.5 и приведен на рис. 2.4. Очевидно, что если в таблице переходов асинхронного автомата некоторое состояние стоит на пересечении строки и столбца г, (г**), то это состояние я* обязательно должно встретиться в этой же строке в столбце 2*. В графе асинхронного автомата, если в некоторое состояние имеются переходы из других состояний под действием каких-то сигналов, то в вершине г* должна быть петля, отмеченная символами тех же входных сигналов. Анализ табл. 2.3 и 2.4 или рис. 2.3, 6 и 2.4 показывает, что представленные там Р-автоматы Р1 и Р2 являются синхронными.

Таким образом, понятие Р-автомата в дискретно-детерминированном подходе к исследованию на моделях свойств объектов является математической абстракцией, удобной для описания широкого класса процессов функционирования реальных объектов в автоматизированных системах обработки информации и управления. В качестве таких объектов в первую очередь следует назвать элементы и узлы ЭВМ, устройства контроля, регулирования и управления, системы временной и пространственной коммутации в технике обмена информацией и т. д. Для всех перечисленных объектов характерно наличие дискретных состояний и дискретный характер работы во времени, т. е. их описание с помощью Р-схем является эффективным. Но широта их применения не означает универсальности этих математических схем. Например, этот подход непригоден для описания процессов принятия решений, процессов в динамических системах с наличием переходных процессов и стохастических элементов.

 
< Пред   СОДЕРЖАНИЕ     След >