Автомат может быть задан своими функциями (переходов и выхода), таблично, в виде графа, матрицы, а также аналитически.
Для табличного представления нужно перечислить все сочетания x(t), u(t) – все элементы области определения функций переходов и выхода (область определения одна и та же) и записать соответствующие им значения x(t+1) и y(t) – элементы областей значения функций переходов и выхода.
Для наглядности аргументы x и u имеет смысл разделить: значения одного аргумента приписать строкам, а другого – столбцам. Тогда значение функций будут записываться на пересечении строк и столбцов. Ввиду совпадения областей определения функций переходов и выхода эти функции можно задавать одной таблицей.
При изображении функций в виде графа: состояния приписывают вершинам, управления – дугам.
Пример 1. Пусть множество управлений u состоит из управлений α, β, γ, множество состояний x – состояний 1,2,3,4, т.е. uÎ{α, β, g}, xÎ{1,2,3,4}, y Î{0,1}.
Функции φ (переходов) и ¦ (выхода) заданы таблицей переходов (табл. 1.4.1), в которой единица может означать необходимость какого-либо действия, ноль – отсутствие такового, прочерк – ограниченность управлений (отсутствует управление β при состоянии 2 и управление γ при состоянии 3).
Таблица 1.4.1
x(t)
u(t)
α
β
g
2/0
3/1
4/0
2/1
-
3/0
3/0
4/0
-
2/1
1/0
2/1
При другом способе задания конечного автомата используется понятие направленного графа.
Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал вызывает переход из одного состояния в другой, то на графе автомата дуга, соединяющие их вершины обозначается соответствующим символом входного сигнала. Для задания функции выходов дуги графа необходимо отметить соответствующими сигналами.
Табл. 1.4.1.соответствует граф, показанный на рис. 1.4.1.
Рис.1.4.1 Граф конечного автомата таблицы 1.4.1.
Пример 2. Рассмотрим автомат, который выдает билет при опускании в него монет в сумме 3 руб., причем он принимает монеты 50 коп., 1рубль и 2 рубля. Автомат может давать сдачу. Составим функцию перехода и выхода.
uÎ{ α=0.5, β=1, g=2}, xÎ{1,2,3,4,5,6}.
Функция переходов может быть задана таблицей переходов (табл. 1.4.2).
Таблица 1.4.2
u
0.5
1.0
2.0
x
a
β
g
1
0.5
1.0
3
1.5
4
2.0
2.5
6
Поясним табл. 1.4.2.
Например, опустили в автомат 1 рубль. Тогда из исходного состояния 1 (ожидание начала набора суммы) автомат перешел в состояние 3 (в автомате пока накопилась сумма 1 рубль). Теперь опустили, к примеру, 50 коп., тогда автомат перейдет из теперь уже исходного состояния 3 в состояние 4 (в автомате уже полтора рубля), далее опустили еще 1 рубль – автомат перешел из состояния 4 в состояние 6 (накопилась сумма 2,5 рубля). И, наконец, опустили последние 50 коп., в автомате собралась полная сумма: выдается билет, и автомат опять переходит в 1 состояние – готовности к приему монет.
Для функции выхода y = (y1, y2) составим табл. 1.4.3, в которой:
y1 – сигнал на пропуск или выдачу билета, y1 Î{0,1}.
y2 – сигнал для сдачи, y2 Î{0, 0.5, 1.0, 1.5}.
Таблица 1.4.3
u
0,5
x
a
β
g
0;0
0;0
0;0
0;0
0;0
0;0
0;0
0;0
1;0
0;0
0;0
1;0,5
0;0
1;0
1;1
6
1;0
1;0,5
1;1,5
действие сдача
При превышении требуемой цены за билет вместе с билетом выдается сдача. Моменты времени лучше связывать только с моментами опускания монеты.
Граф переходов, как и любой граф, может быть представлен матрицей переходов – квадратной матрицей, размерность которой совпадает с числом состояний, а элементами являются дуги, соединяющие состояния.
Запишем автомат в виде матрицы:
Если множество путей, ведущих от одного состояний к другому записывать как сумму, а путь, включающий дуги как произведение дуг, то возведение матрицы в степень дает все пути определенной длины, совпадающей с показателем степени между состояниями (возведем в квадрат, получим путимежду состояниями длины 2, если в куб -длины 3).
Если хотят определить количество путей определённойдлины, то составляют так называемые скелеты матриц и возводят их в степень. Они отличаются от матрицы «А» тем, что в ней вместо управлений записывается их количество.
Транспортная сеть, рассмотренная ранее в примере минимизации, расстояния также подходит под модель конечного автомата.
Путем возведения матрицы переходов в степень можно получить пути определенной длины, ведущие от i-го состояния к j‑му для всех i и j.
Обозначим множество дуг, ведущих из i-го состояния в j-ое в графе переходов, через πij (получится одна объединенная дуга).
Путь – это последовательность дуг. Будем считать его произведением дуг.
Путь между состояниями может быть не один. Если множество путей записывать как сумму, то возведение матрицы переходов в квадрат дает все пути длины 2 между всеми состояниями. Справедливость этого подтверждается правилом перемножения матриц.
Элемент, стоящий на пересечении i-ой строки и j-го столбца произведения матриц равен произведению i-ой строки и j-ый столбец матриц-сомножителей. При возведении в квадрат это есть произведение следующих строки и столбца
То есть pij = pi1p1j + pi2p2j + …+ pispsj .
Это есть все пути длины 2, ведущие из i-го состояния в j-е.
Аналогично элемент (i,j) матрицы ||A||k является множеством всех путей длины k, ведущих из i-го состояния в j-е состояние автомата A.
Матрица ||A||k называется матрицей переходов k-го порядка.
Если необходимо определить пути, ведущие из одного состояния, например i-го, то нужно на матрицу ||A|| умножить не матрицу, а ее i-ю строку. После каждого умножения получается строка. В результате будет строка, содержащая пути определенной длины из i-го состояния.
Таким образом, понятие автомата в дискретно-детерменированном подходе к исследованию на моделях свойств объектов является математической абстракцией, удобной и эффективной для описания широкого класса процессов функционирования реальных объектов в автоматизированных системах (элементы ЭВМ, устройства контроля, регулирования и управления, системы коммутации). Для подобных систем характерно наличие дискретных состояний и дискретный характер работы во времени. Но широта их применения не означает универсальности этих математических схем. Например, данный подход непригоден для описания процессов принятия решений, процессов в динамических системах с наличием переходных процессов и стохастических элементов.
1
3
4
6
6
