) Понятие множество, если не будет специально оговорено, всегда будет предполагать неупорядоченное множество. Множество

элементов ej, .....е будет записываться так: {е„ е2, ..., е]-

Число элементов г называется мощностью множества.

2 А. Гилл

Рис. 1.2 изображает представленную на рис. 1.1 систему с обозначениями, измененными в соответствиис предположением о дискретности времени. Символами лГу. / -1, 2..... «,

и zJ\ J=\, 2.....w, обозначены соответственно входные и выходные переменные в моменты времени t.

1.4. Конечность алфавита

Следующее предположение, которое должно быть сделано для основной модели с конечным числом состояний, заключается в том, что каждая переменная может принимать только конечное число различных значений (которые по своей природе могут быть числовыми или не числовыми).

Множество) значений, которые переменная v может принимать, называется алфавитом переменной v и обозначается через V; элемент v алфавита V называется символом. Пусть

К\ /С®.....ЛГ*"* - конечные множества с соответствующими элементами Л;, tSP...../г*""* и пусть множество

ЛГ**©ЛГ*© ®К" обозначает множество всех упорядоченных ти-значных наборов (М". kf...../г"). Если входные переменные данной системы суть д:**, д:*.....д;*"*, то

входной алфавит этой системы, обозначаемый через X, определяется выражением

А = А:<"©А<© . . . ©А-*". (1.1)

где А*", i= 1, 2, -алфавит д;**.

Аналогично, если выходные переменные системы суть 2**.....z-K то выходной алфавит Z системы определяется выражением

Z-=Z<"©Z<*© . . . ©Z<"". (1.2)

где Z-\ у=1, 2.....ге», -алфавит г*-*.

(1.3)

q=Jl4j- (1-4)

Мощности р н q конечны.

Из определения входного алфавита X видно, что одного символа входного алфавита - входного символа - достаточно для описания всех и входных переменных в любой заданный момент времени t. Аналогично из определения выходного алфавита Z видно, что одного символа выходного алфавита - выходного символа - достаточно для описания всех W выходных переменных в любой заданный момент времени t. Следовательно, входные переменные д;**, д;*.....д;"*

могут быть заменены одной входной переменной х, алфавит которой X определяется выражением (1.1). Выходные переменные z\ z.....2*™* могут быть заменены одной выходной переменной z, ал-

фавит которой Z определя-ется выражением (1.2). Соответственно и входных , клемм можно заменить од-Рис. 1.3. Представление конечного ной входной клеммой и w автомата в виде «черного ящика», выходных клемм - одной

выходной клеммой. В результате получим схематичное изображение, имеющее вид двухклеммного ящика (рис. 1.3), которое является стандартным представлением основной модели конечного автомата.

Для иллюстрации рассмотрим вычислительное устройство, которое имеет две входные линии д;** и д;**: по линии д;** подаются символы О и 1, по линии д;* - символы 1, 2 и 3. В произвольные моменты времени устройство выдает вели-

чины Z = Xj Х -\-Х-\Хх-\ и 2v = I-"V V -xv-ljiv-l

Таким образом, имеем:

А<" = {0. 1}, А<*={1, 2, 3}, 2<"={0, 1. 2, 3. 4, 5. 6). Z<*={0, 1, 2. 3}

Если Л"** имеет мощность р, а мощность qj, то

мощности р для X и q для Z выразятся соответственно формулами:

1.51 состояния 19

и, следовательно,

-={(0, 1), (О, 2). (О, 3), (1, 1), (1, 2), (1, 3)}, Z = {(О, 0), (О, 1), (О, 2), (О, 3), (1, 0), (1, 1), (1. 2), (1, 3), (2, 0), (2,1), (2, 2), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3), (4, 0), (4, 1). (4. 2) (4, 3). (5. 0). (5, 1), (5, 2), (5, 3).

(6, 0), (6, 1). (6, 2), (6, 3)}.

1.5. Состояния

В то время как в качестве входов и выходов выбираются такие переменные, которые исследователь может наблюдать и измерять, природа промежуточных переменных часто может оставаться неизвестной, а измерение их - невозможным. Значение промежуточных переменных, однако, заключается не в характере изменения каждой из них, а скорее в их комбинированном действии на зависимости между входными и выходными переменными. Это комбинированное действие, так же как и переменные, вызывающие его, подчинено предположениям о дискретности времени и конечности алфавита, введенным в §§ 1.3 и 1.4. Указанное действие называется состоянием системы. Состояние системы в момент будем обозначать через s. Набор всех возможных состояний системы, которые ей присущи, называется множеством состояний и обозначается через 5.

Понятие состояния может быть строго определено, исходя из той роли, которую оно играет в определении основной модели конечного автомата. Эта роль может быть выражена следующими двумя положениями: (1) выходной символ в данный момент времени однозначно определяется входным символом и состоянием в данный момент; (2) состояние в следующий момент времени однозначно определяется входным символом и состоянием в настоящий момент времени.

Таким образом, грубо говоря, состояние конечного автомата в любой заданный тактовый момент является той переменной, которая вместе с входным символом дает возможность