Конечные автоматы
Для моделирования динамических систем, функционирующих в дискретном времени, применяется аппарат конечных автоматов [7]. Теория конечных автоматов и их модели используются при синтезе и анализе вычислительных устройств, дискретных устройств автоматики. Конечный автомат функционирует в дискретные моменты времени t, причем в каждый момент tiавтомат находится в одном из возможных состояний z(ti), принадлежащем множеству состояний автомата Z. Математические модели в виде конечного автомата получили название F-схем от английского finite automata – конечный автомат.
В каждый момент ti(i=1,2,...) на вход конечного автомата поступает входной параметр - одна из букв х(ti) входного алфавита Х, а на выходе существует выходной параметрy(t) - буква выходного алфавита Y.
Автомат формально определен набором
A=<Х,Z,Y,z0,j,y>,
где Х={х1,х2,...,хm} -множество входных параметров; Z={z1,z2,...,zn} - множество состояний; Y={y1,y2,...,yr} - множество выходных параметров. Элементы множества Х, Z, Y называют входным, внутренним и выходным алфавитом. При поступлении параметра х состояние конечного автомата изменяется в соответствии с одношаговой функцией переходов, например:
z(t)=j[z(t-1),х(t)] илиz(t)=j[z(t),х(t)],
а выходной параметр y(t) определяется функцией выходов, которая может иметь следующие виды задания:
y(t)=y[z(t),х(t)]; y(t)=y[z(t-1),z(t) х(t)]; y(t)=y[z(t-1), х(t)].
Функции переходов и выходов могут быть заданы теоретико-множественным способом, табличным способом и в виде графов. Рассмотрим пример задания конечного автомата.
Пусть Х={х1,х2,х3}, Z={z1,z2,z3,z4}, Y={y1,y2,y3,y4}.
Функция переходов для данного автомата задана в виде табл. 2.1, а функция выходов вида y(t)=y[z(t),х(t)] – в виде табл. 2.2.
Таблица 2.1
Функция переходов
| Х | Z | |||
| z1 | Z2 | z3 | z4 | |
| х1 | z1 | Z2 | z3 | z4 |
| х2 | z2 | Z3 | z4 | z1 |
| х3 | z4 | Z1 | z2 | z3 |
Таблица 2.2
Функция выходов
| Х | Z | |||
| z1 | z2 | z3 | z4 | |
| х1 | y1 | y4 | y3 | y2 |
| х2 | y2 | y1 | y4 | y3 |
| х3 | y3 | y2 | y1 | y4 |
При задании функции переходов на пересечении i–й строки и j–го столбца указывается состояние zk, в которое переходит автомат при подаче входного параметра хi в такте времени t, при условии, что в такте времени t-1 автомат находился в состоянии zj.
На рис. 2.4 приведено графическое задание функции переходов рассматриваемого автомата.
Рис. 2.4
Автомат в процессе своей работы реализует отображение множества слов (последовательность параметров) входного алфавита Х на множество слов выходного алфавита Y. Если на вход конечного автомата, установленного в начальное состояние z0, подать последовательность букв входного алфавита х(t0), х(t1), х(t2),…, то на выходе автомата будут последовательно появляться буквы выходного алфавита y(t0), y(t1), y(t2),…
В зависимости от способа заданий функций переходов и выходов, автоматы подразделяются на автоматы первого и второго рода. Для автомата первого рода, называемого автоматом Мили, функция переходов имеет вид z(t)=j[z(t),х(t)], а функция выходов - y(t)=y[z(t),х(t)].
Для автомата второго рода функция переходов имеет вид: z(t)=j[z(t),х(t)], а функция выходов - y(t)=y[z(t-1),х(t)].
Автомат второго рода, функция выходов которого определяется его состоянием - y(t)=y[z(t)], называется автоматом Мура.
По числу состояний различают конечные автоматы с памятью и без памяти. Автоматы с памятью имеют более одного состояния, а автоматы без памяти обладают лишь одним состоянием. Автоматы без памяти называют комбинационными или логическими схемами. Функция выходов такого автомата - y(t)=y[х(t)].
Если множества Х и Y состоят из двух параметров, то функции переходов и выходов называются булевыми функциями.
Рассмотрим примеры моделирования систем в виде конечных автоматов.
Пример 1. Автомат для продажи билетов в автобусах принимает монеты достоинством в 1,2 и 5 рублей и выдает билеты стоимостью 5 рублей. Рассмотрим конечный автомат Мили с множеством состояний Z=(0,1,2,3), входным алфавитом Х=(1,2,5) и выходным алфавитом Y=(0,1), где 0 соответствует ситуации «билет не выдается», а 1 – ситуации «билет выдается».
Функция переходов j(t) определяется соотношением
Z(t)=(z(t-1)+х(t))mod5,
а функция выходов y(t) – соотношением
Пример 2.Хранилище склада материально-техническогоснабжения состоит из стеллажей, предназначенных для хранения материальных ценностей.
Изделия i-й номенклатуры хранятся в i-м стеллаже (i=1,2,…,n). Содержание стеллажей изменяется в моменты времени поступления на склад новых изделий потребителям. Такое хранилище можно представить в виде конечного автомата Мура. В качестве состояний выберем n-мерный вектор Z=(Z1,Z2,…,Zn), где Zi - число изделий на i-м стеллаже.
Выходной сигнал – (n+1) – мерный вектор Х=(Х1,Х2,…, Хn,m), где Хi - число изделий i-й номенклатуры, поступивший на склад или выданный потребителю. При поступлении изделий на склад m=1, а при выдаче изделий потребителю m= -1. Выходной сигнал представляет собой n–мерный вектор Y=(Y1,Y2,…,Yn), для которого Yi(t)=Zi(t) – информация о состоянии стеллажей.
Функция переходов определена соотношением
Zi(t)=Zi(t-1)+mх(t),
а функция выходов определена соотношением
Yi(t)=Zi(t).
На рис. 2.5 приведен алгоритм программы моделирования конечного автомата, функция выходов которого имеет задание z(t)=j[z(t-1),х(t)], а функция переходов - y(t)=y[z(t),х(t)]. Функция переходов задается в подпрограмме WWOD в виде массива FР(i,j), значения которого определены индексом k состояния zk, в которое переходит автомат при подаче входного параметра хi в такте времени t, при условии, что в такте времени t-1 автомат находился в состоянии zj.
Рис. 2.5
Функция выходов задается в подпрограмме WWOD в виде массива FW(i,k), значения которого определены индексом w выходного параметра (буквы) yw, который будет на выходе автомат при подаче входного параметра хi в такте времени t, при условии, что в этом такте времени t автомат находится в состоянии zk. В подпрограмме WWOD происходит инициализация автомата, т.е. определение z0=zk. В блоке 3 алгоритма происходит изменение индекса состояния с учетом задержки на один такт.