Возможные приложения. 
Моделирование систем

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

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

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

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

Таблица 2.1.

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

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

Таблица 2.3.

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

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

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

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

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

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

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

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

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

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

Таблица 2.5.

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

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

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