в) Сокращение (сжатие) таблицы переходов

Если в построенной таблице «быстрого» автомата (в таблице переходов Хафмана) имеются строки с одинаковым заполнением, то это значит, что его можно заменить другим «быстрым» автоматом с меньшим числом состояний. Покажем, как это сделать, на примере табл. 5.7.

Вводится новая переменная , ее значения приводятся в соответствие значениям переменной и притом так, чтобы значениям , соответствующим строкам с одинаковым заполнением таблицы «быстрого» автомата, соответствовало бы одно и то же значение . Это удобно сделать на таблице «быстрого» автомата, добавив в ней справа столбец значений . В нашем случае этот столбец будет заполнен так, как показано на табл. 5.7, (где были одинаково заполнены шестая и девятая строки. Затем строится сжатая таблица переходов (табл. 5.8), содержащая прежнее количество столбцов и столько строк, сколько получилось различных символов . Заполнение таблицы ведется по табл. 5.7 с заменой символов соответствующими символами .

Таблица 5.8

При этом в шестой строке появляется еще один квадратик — равновесное состояние. Полученная таким образом сжатая таблица определяет (в форме П — П) «быструю машину», работающую (если следить за ее равновесными состояниями) как исходная «медленная» и имеющую минимальное число состояний. Последнее утверждение будет разъяснено гл. X.

По существу на этом заканчивается синтез последовательностной машины, которая, работая в быстрой тактности, реализует своими равновесными состояниями исходную машину, работающую в тактности смены входа. Далее остается реализовать ее релейной схемой.