Формализованное описание кибернетической системы.

С позиций современной алгебры элемент кибернетической системы представляет абстрактный автомат А,который описывается пятеркой (А;S;Z;f;g), где A – множество входных сигналов (входной алфавит), S – множество внутренних состояний; Z – множество выходных сигналов (выходной алфавит); f:S×A→S – функция переходов (в следующее состояние); g:S×A→Z – функция выходов автомата. Формально, автомат – это алгебра с тремя основными множествами А;S;Z и двумя бинарными операциями f и g. Если автомат А находится в состоянии s S и получает на входе а А, то он переходит в состояние f(s;a) и выдает сигнал g(s;a).

Автомат А называется конечным, если множества А;S;Z конечны. Это наиболее изученный класс автоматов, к которому, в частности, отнесятся современные компьютеры [14]. Обобщения конечных автоматов происходят по нескольким направлениям: если, например, хотя бы одно из множеств А;S или Z – бесконечное, то соответствующий автомат называют бесконечным; если автоматные функции f;g – есть случайные процессы, то такой автомат называют стохастическим; если А;S или Z представляют собой нечеткие множества [15], то данный автомат называют нечетким и т.д.

Покажем, что алгебраическая структура (А;S;Z;f;g), представляющая автомат А, является универсальным преобразователем информации. Для простоты ограничимся рассмотрением конечных автоматов и заметим, что в реальной ситуации на вход автомата, как правило, подается не одиночный сигнал а А, а некоторая программа, состоящая из последовательностей элементов (букв) входного алфавита А. Поэтому элементы А резонно рассматривать как систему образующих, порождающих посредством операции конкатенации свободный моноид F_A, состоящий из всевозможных последовательностей (слов), построенных из букв алфавита А, включая пустую последовательность е в виде единицы.

Пусть автомат А находится в состоянии s S и на его вход поступает команда в виде последовательности а₁а₂…а_r F_A, где а₁;а₂;…;а_r A. Выполнение этой команды предполагает рекурсию

f(s;e)=s

f(s;a₁)=f(s;a₁)

f(s;a₁a₂)=f(f(s;a₁);а₂) (1.1)

. . . . . . . . . . . . . . . . . . . . . . . . . . .

f(s;a₁a₂…a_r)=f(f(s;a₁a₂…a_r-1);а_r),

что дает на выходе: g(s;e)=e

g(s;a₁)=g(s;a₁)

g(s;a₁a₂)= g(s;a₁)g(f(s;a₁);а₂) (1.2)

. . . . . . . . . . . . . . . . . . . . . . . . . . .

g(s;a₁a₂…a_r)= g(s;a₁)g(f(s;a₁);a₂a₃…a_r)

Используя (1.1), положим: s₁=s

s₂= f(s₁;a₁)

s₃= f(s₁;a₁a₂)= f(f(s₁;a₁);а₂)= f(s₂;a₂) (1.3)

. . . . . . . . . . . . . . . . . . . . . . . . . . .

s₄= f(s₃;a₃);…; s_r+1= f(s_r;a_r)

Из соотношений (1.1), (1.2), (1.3) видно, что, если автомат А находится в состоянии s и на вход поступает команда а₁а₂…а_r F_A, то его состояния последовательно изменяются от s=s₁ к s₂;s₃;..., пока не будет достигнуто состояние s_r+1 и выходная последовательность примет вид z₁z₂z₃…z_r, где z_i=g(s_i;a_i) Z, i= , причем, множество выходных последовательностей, вообще говоря, моноидом быть не обязано.

Для произвольной последовательности a F_A введем функцию f_a:S S, так что f_a(s)=f(s;a). Тогда F_A: (f_a )(s) = f_a( (s))= f_a(f (s; ))= = f(f (s; );a)=f (s; a)= (s) f_a = , причем, полагая =e, получаем f_a = =f_a, т.е. функция в данном случае выполняет роль единицы. Учитывая, что композиция функций ассоциативна, пара ({f_a|a F_A}; ) является моноидом, который принято называть моноидом автомата А, представляя в виде тройки (А;S;f).

Данное обстоятельство представляется важным, поскольку имеет место изоморфизм (А;S;f) F_A. Тогда в свободном моноиде F_A, как это следует из теории формальных языков [14], выделяется класс рациональных (или регулярных) языков Rat F_A, и всякий такой язык, по теореме С.К. Клини (1956), является распознаваемым. Следовательно, конструкция абстрактного автомата А такова, что входная информация формализуется универсальным алгоритмическим языком, который гарантированно распознается данным автоматом и, тем самым, реализуется соответствующее преобразование поступающей информации.