§ 10.18. Описание конечных автоматов

Поведение конечных автоматов или, если угодно, процессы в конечных автоматах можно описать двумя уравнениями: уравнением состояния (или переходов) и уравнением выходных величин

                                             (10.79)

В этих уравнениях  — «квантованная» по уровню функция двух векторных переменных,  — «квантованная» по уровню функция одной векторной переменной, а  — вектор начальных состояний.

Рис. 10.7.

Специальный индекс у функций и  должен напоминать нам, что эти функции квантованы по уровням и, следовательно, могут принимать «значения», соответствующие буквам своего алфавита.

Рис. 10.8.

В отличие от уравнений непрерывных или импульсных систем, при описании конечных автоматов вводятся промежуточные величины — состояния , которые играют определенную роль при построении модели конечного автомата, но нам нет необходимости углубляться в обсуждение этого вопроса. Уравнениям (10.79) соответствует структурная схема конечного автомата, изображенная на рис. 10.7. Этот конечный автомат имеет  входов и  выходов. Для автоматов с одним входом и одним выходом (рис. 10.8) вместо уравнении (10.79) мы будем иметь

                                             (10.80)

Но для конечных автоматов между векторными уравнениями (10.79) и скалярными уравнениями (10.80) нет непроходимой пропасти, как в случае непрерывных или импульсных систем. Если все возможные комбинации   входных воздействий закодировать соответствующими буквами и то же самое проделать для состояний и выходной величины, то автомат с  входами и множеством воздействий, закодированных в -буквенном алфавите, эквивалентен автомату с одним входом и одним выходным воздействием, закодированными в -буквенном алфавите.

В отличие от непрерывных функций обычно задаваемых в аналитической форме, «квантованные» по уровню функции ,  а значит, и уравнения конечных автоматов, могут быть заданы различными способами, например табличным или графическим. Taк,  и  полностью определяются таблицей перехода и выходов (табл. 10.2), либо графом — диаграммой перехода (рис. 10.9). Над символами состояний в табл. 10.2 записываются выходные величины. На графах они записываются около узлов. Функция   может быть определена матрицей состояний

                              (10.81)

Рис. 10.9.

Таблица 10.2.

Каждая строка этой матрицы содержит только один элемент, равный единице, остальные элементы равны нулю. Если автомат в момент  находится в состоянии , а входное воздействие равно , то следующее состояние будет равно , если .

Далее мы будем рассматривать стохастические автоматы с одним входом и одним выходом. Как было упомянуто выше, это не является ограничением.