Другие виды конечных автоматов

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

Мы кратко рассмотрим два, достаточно часто встречающихся случая.

Автомат с последействием

Автомат с последействием – это объект A=(X,Y,Z,j,y,k), определяемый следующими характеристиками:

Z– множество состояний; X– входной, a Y– выходной алфавиты; j– одношаговая функция переходов; y– одношаговая функция выходов; k– нату- ральное число, называемое порядком начального множества.

Состояние автомата изменяется в соответствии с одношаговой функцией переходов так:

z(tj) = j{[z(tj-k), z(tj-k+1),…, z(tj-1)], x(tj)}(2.14)

Функция выходов yаналогична рассмотренной ранее и определяется по формуле (2.12).

Здесь набор состояний [z(ti-k), z(ti-k+1),.. . ., z(ti-1)]называется предыстори- ей автомата, а набор моментов времени ti-k, ti-k+1,. . ., ti-1– начальным множест- вом относительно момента времени ti-1.

Легко видеть, что при k = 1автомат с последействием превращается в обычный конечный автомат без последействия. При k > 1мы получаем модель более общую, чем конечный автомат.

Нестационарные автоматы

Другой тип детерминированных систем с дискретным временем, обоб- щающий понятие конечного автомата, - так называемые нестационарные авто- маты. Обычный (стационарный) автомат A=(X,Y,Z,j,y)имеет функции пере- ходов и выходов, которые не зависят явно от времени t. Внимание к стацио- нарным автоматам сложилось исторически как к моделям реальной аппарату- ры, работающей в стационарных условиях. Более естественна, конечно, модель общего вида, когда функции переходов и выходов могут явно зависеть от вре- мени:

z(tj) = j[tj-1, z(tj-1), x(tj)],(2.15)

y(tj) = y[tj-1, z(tj-1), x(tj)]. (2.16)

В последнее время все чаще на практике встречается именно эта схема. Она относится к случаю непостоянства условий функционирования аппарату- ры (изменение факторов внешней среды, строение технических средств, расхо-

дование ресурсов и т. д.). Кроме того, детерминированные системы с дискрет- ным временем, как модели объектов материального мира, проникают в эконо- мику, социологию, биологию и т. п. В связи с этим все чаще приходится иметь дело с объектами, не обладающими свойством стационарности.

Анализ нестационарных автоматов невозможен в рамках методов, разви- тых для стационарных автоматов. Одним из приемов изучения нестационарных автоматов может служить переход к стационарному автомату, соответствую- щему данному нестационарному. При этом чтобы функции jи yперестали яв- но зависеть от времени, его включают в состояние автомата как еще одну коор- динату.

Полученный автомат хотя и стационарный, но он уже не является конеч-

ным, поскольку моментов времени бесконечное множество. Однако при моде- лировании систем на конечном интервале времени мы будем иметь дело с ко- нечным числом моментов времени, и поэтому поведение соответственного ста- ционарного автомата будет аналогично поведению обычного конечного авто- мата.

С помощью конечных автоматов (F-схем) описываются узлы и элементы ЭВМ, устройства контроля, регулирования и управления, системы временной и пространственной коммутации в технике обмена информацией. Однако широта применения F-схем не означает их универсальность. Этот подход непригоден для описания процессов принятия решений и процессов в динамических сис- темах с наличием стохастических элементов.

СТОХАСТИЧЕСКИЕ МОДЕЛИ

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

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