а) Замечания о типе автомата или последовательностной машины

Напомним, что любая последовательностная машина, и в том числе любой конечный автомат, могут быть, определены системой соотношений (см. § 3.4)

где

Это следует из того, что те последовательностные машины и автоматы, которые определены системой соотношений

за счет введения функции

всегда могут быть приведенык форме (5.2). Обратное утверждение не имеет места, т. е. задание в виде системы (5.2) без изменения числа состояний только иногда может быть приведено к системе (5.3).

В частности, автомат, заданный системой

всегда может быть представлен системой

а автомат, заданный системой

не может быть приведен к системе вида (5.3).

П-машины, заданные системой (5.2), в § 3.4 были названы машинами типа П — П, а П-машины, заданные системой (-машинами типа П — Н. Далее мы будем пользоваться этой терминологией.

Универсальность системы (5.2) дает основания для того, чтобы использовать ее в качестве канонического способа задания конечных автоматов и последовательностных машин.

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

Можно считать, что строки и столбцы соответствуют настоящим состояниям автомата и входа (состояниям в момент времени ); тогда символы в клетках определяют будущее состояние автомата (состояние в момент времени и настоящее состояние выхода П-машины. Эта трактовка связана с представлением системы (5.2) в виде ,

Табл. 5.1 — 5.5 служат примерами представления исходных данных совмещенными таблицами.

Табл. 5.1 задает такой автомат, который по желанию можно трактовать как автомат типа П — П или типа П — Н. Это можно видеть по тому, что символы всех клетках таблицы взаимно однозначно соответствуют друг другу.

Таблица 5.1

Таблица 5.2

Табл. 5.2 определяет автомат, который нельзя трактовать как автомат типа П — Н. Признаком этого является взаимно однозначное соответствие символов в каждой строке (одинаковых всех клетках, принадлежащих одной и той же строке) и символов , расположенных в левом (входном) столбце таблицы.

Табл. 5.3 определяет последовательностную машину, приводимую к машине типа . Это следует из того, что в клетках таблицы, относящихся к одному (любому) столбцу, находятся взаимно однозначно соответствующие друг другу символы .

Таблица 5.4

Таблица 5.3

Табл. 5.4 и 5.5 определяют последовательностные машины, не приводимые к типу П — Н, так как в таблицах есть такие столбцы, в клетках которых символы и не взаимно однозначно соответствуют друг другу (см. столбец ). Особенность табл. 5.4 по сравнению с табл. 5.5 состоит в в ней во всех клетках внутри каждого столбца сохраняется однозначно соответствие символов и одинаковые встречаются в паре с одинаковыми (нет только взаимно однозначного соответствия).

Таблица 5.5

Табл. 5.1 — 5.4 объединяются одним общим признаком: для них будущее состояние автомата (символ и в клетке) однозначно определяется настоящим состоянием входа и выхода П-машины. Только табл. 5.5 не обладает этим свойством.

Излагаемый далее метод Хафмана пригоден для непосредственного применения в тех случаях, когда задание на синтезируемую схему не относится к типу табл. 5.5. Иначе говоря, этим методом можно реализовать любые автоматы (приводимые и неприводимые к типу П — Н), последовательностные машины, приводимые к типу П — Н, и некоторые последовательностные машины, неприводимые к типу П — Н, но обладающие особенностью табл. 5.4.