§ 4.2. Абстрактная структура автомата

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

где F — любая однозначная функция, заданная на множествах .

Рассмотрим теперь подробнее на примере автомата типа П — П, каким образом описание конечной динамической системы рассматриваемого класса сводится к соотношению вида (4.1).

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

Пусть координата может иметь лишь одно из значений . Аналогично каждое входное воздействие в эти же моменты может принимать лишь одно из , значений . «Движение» в системе подчинено условию, что значение каждой из координат в момент однозначно определяется значениями всех координат и всех входов в момент . Тогда движение описывается системой рекуррентных соотношений

Введя в рассмотрение -мерный вектор с координатами -мерный вектор с координатами и вектор-функцию с координатами , систему соотношений (4.2) можно представить в векторной форме

Вектор в моменты тактов может иметь одно из значений, а вектор — одно из значений. Поэтому, выбрав алфавиты , содержащие соответственно и символов, и приписывая различным векторам различные символы , а векторам — символы , вместо соотношения (4.3), получим соотношение вида (4.1) с конкретной функцией F в правой части. Эта функция F строится по вектор-функции в соответствии с выбранной кодировкой векторов .

Из изложенного ясно, что система рекуррентных соотношений (4.2) описывает конечный автомат

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

Условимся называть систему соотношений вида (4.2) абстрактной структурой конечного автомата (4.4).

Таким образом, задание абстрактной структуры однозначно определяет конечный автомат, т. е. по соотношениям (4.2) единственным образом восстанавливается соотношение (4.4). В этом смысле система рекуррентных соотношений (4.2) задает конечный автомат в такой же мере, в какой он может быть задан соотношением (4.4). Поэтому на конечный автомат, заданный системой соотношений типа (4.2), полностью распространяется понятие о замещении автоматов.

Покажем теперь, что по заданному конечному автомату А можно построить много абстрактных структур, замещающих этот автомат.

Пусть задан автомат А с алфавитами . Зная , выберем числа и .

Выбор этих чисел стеснен лишь одним условием: должны выполняться неравенства

Введем в рассмотрение координат (принимающих соответственно значений) и s ниток входа (принимающих соответственно значений).

Заполним теперь таблицу (табл. 4.9) следующим образом.

Таблица 4.9

В левые столбцы таблицы выписываются все возможные сочетания значений .

Таких сочетаний может быть , следовательно, имеет такое число строк.

Чтобы заполнить столбец , обратим внимание лишь на столбцы . В эти столбцы вписано различных сочетаний из . Выберем из них какие-нибудь сочетаний, назовем их основными, припишем им символы и впишем эти символы в соответствующие строки столбца табл. 4.9. В связи с тем, что в силу неравенств (4.5) может быть и , часть строк столбца может оказаться незаполненной. В этом случае остальным сочетаниям из , которые не вошли в k отобранных сочетаний, припишем уже использованные символы в любом порядке и впишем эти символы в незаполненные строки столбца .

После этого столбец заполнен целиком. Совершенно так же заполняется столбец , но только рассматриваются сочетания из , вписанные в столбцы .

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

то часть сочетаний может повториться.

Обращаясь теперь к заданному автомату А, например к его основной таблице, заполняем столбец табл. 4.9. Но с каждым символом мы уже связали одно из основных сочетаний из . Вписывая теперь в столбцы сочетания, соответствующие , заканчиваем заполнение таблицы.

Построенная так таблица определяет значения всех по заданным , т. е. задает функций в рекуррентных соотношениях вида (4.2).

Если бы вместо неравенств (4.5) имели место равенства

то в столбцах табл. 4.9 каждое попарное сочетание символов встречалось бы лишь один раз.

то табл. 4.9 содержит те же строки, что и в случае (4.6), и, кроме того, эта таблица содержит также дополнительные строки, соответствующие неосновным сочетаниям.

Если бы мы пытались теперь от построенной в табл. 4.9 абстрактной структуры перейти к автомату, то получили бы уже не исходный автомат, а другой автомат.

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

Таблица 4.10

При построении абстрактной структуры, т. е. при построении системы соотношений (4.2) из соотношения (4.4) с помощью табл. 4.9, мы могли распорядиться выбором чисел различным образом, лишь бы были соблюдены условия (4.5). Ясно, что не только вид функций в правых частях соотношений (4.2), но даже само число соотношений в системе (4.2) зависит от того, как мы распорядились выбором этих чисел. Используя этот произвол, можно строить множество абстрактных структур, замещающих заданный конечный автомат А.

В качестве важного примера рассмотрим случай, когда все равны двум, т. е. все — логические переменные. Абстрактная структура в этом случае имеет вид

где все — логические функции.

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

Таблица 4.11.

В этом случае

Если числа не являются целыми степенями двойки, т. е. не содержатся среди чисел 2, 4, 8, 16, 32, 64, 128, 256,..., то равенства (4.6) не могут быть удовлетворены. Чтобы удовлетворить неравенствам (4.5), надо и s выбирать из условий

Так, например, если автомат задан основной таблицей (табл. 4.10), то и можно взять, например, . Заполнение таблицы типа табл. 4.9 показано в табл. 4.11.

Можно также построить иные двоичные структуры, замещающие тот же автомат, если положить, например, или и т. д.

Таблица 4.12

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

Заполняя для этого случая табл. 4.9, строим абстрактную структуру (табл. 4.12), но она уже не является двоичной.