§ 10.4. Минимизация воспроизводящей последовательностной машины, построенной в предыдущем параграфе

Для рассмотренного в § 10.3 случая попытаемся решить задачу минимизации, т. е. построить такую машину , воспроизводящую относительно заданную машину G, которая имела бы наименьшее возможное число состояний. Предположим заранее, что искомая машина удовлетворяет двум условиям.

Условие 1. Любое состояние машины является равновесным хотя бы для одного входного воздействия.

Условие 2. При любом изменении входного воздействия машина приходит в новое равновесное состояние за один быстрый такт (т. е. число для этой машины равно единице).

Рис. 10.8.

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

Допустим, что первое условие не выполнено. Это означает, что машина имеет хотя бы одно состояние , которое не является равновесным, и на диаграмме состояний машина обозначается кружком h, не охваченным петлей (рис. 10.8). Тогда это состояние можно удалить, заменив подходящую и отходящую от кружка стрелки с первым индексом одной стрелкой с тем же первым индексом, соединяющей кружки . Отходящая от кружка стрелка с первым индексом , для которого не имеется соответствующей подходящей стрелки с тем же индексом, удаляется (рис. 10.9).

Таким способом можно удалить все неравновесные состояния.

Описанное преобразование, как нетрудно видеть, изменяет работу машины лишь в промежутке между ее двумя равновесными состояниями, когда мы работу этой машины все равно не наблюдаем. Порядок же смены равновесных состояний не нарушается и, следоватёльно, измененная машина по-прежнему будет воспроизводить заданную машину G. Однако это преобразование позволяет уменьшить число состояний машины , и, следовательно, машина, не удовлетворяющая условию 1, не может быть минимальной. Таким образом, условие 1 является необходимым для минимальной машины .

Рис. 10.9.

Вообще для заданной машины G может существовать несколько различных минимальных машин , воспроизводящих машину G относительно множества . Число состояний у всех этих машин должно быть одно и то же — .

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

Обратимся теперь к условию 2. Докажем следующее утверждение. Если существует машина состояниями, воспроизводящая относительно машину G и не удовлетворяющая условию, то существует другая машина с тем же числом состояний , также воспроизводящая машину G относительно и удовлетворяющая условию 2. Тем самым будет доказано, что и условие 2 не является ограничением.

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

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

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

Рис. 10.10.

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

Рис. 10.11.

Будем теперь искать минимальную машину среди всех машин , воспроизводящих заданную машину G относительно множества и удовлетворяющих условиям 1 и 2.

Как уже отмечалось в предыдущем параграфе, входной последовательности вида

машины G соответствует при воспроизведении входная последовательность (10.6)

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

Пусть за множество при воспроизведении выбрано множество следующее утверждение:

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

При справедливость нашего утверждения очевидна, так как в этом случае (см. § 10.3, соотношение ).

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

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

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

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

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

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

Итак, мы показали, что все состояния машины , соответствующие одному и тому же состоянию машины G, при эквивалентны относительно выбранного множества . Тогда в силу доказанного выше утверждения они эквивалентны и относительно , т. е. просто эквивалентны.

Предположим теперь, что нам удалось найти такую быструю машину S из множества , которая не только воспроизводит машину G относительно , но и изображает машину . Это означало бы, что каждому состоянию машины S при любом можно поставить в соответствие состояние машины G так, чтобы имело место изображение.

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

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

Найденная таким образом машина и будет минимальной П-машиной, воспроизводящей относительно машину .

Как отмечалось в § 10.2, машина S, построенная при помощи преобразования матрицы соединений машины G, одновременно и воспроизводит относительно и изображает относительно Е машину G. В то же время эта машина удовлетворяет условиям 1 и 2.

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

Приведем пример построения минимальной П-машины , воспроизводящей относительно заданную машину .

Пример. Пусть матрица соединений заданной «медленной» машины с алфавитами имеет вид

Диаграмма состояний машины G приведена на рис. 10.12.

Рис. 10.12.

Производя описанную в § 10.3 перестройку матрицы , получим матрицу «быстрой» машины S, воспроизводящей машину :

Диаграмма состояний машины показана на рис. 10.13. Минимизируем теперь машину . В матрице соединений машины строки и и строки образуют -матрицы. Перепишем матрицу так, чтобы эти строки стояли рядом и осуществим симметричное разбиение:

Рис. 10.13.

Окончательно получаем матрицу соединений минимальной машины имеющей четыре состояния:

Диаграмма состояний машины приведена на рис. 10.14.

Рис. 10.14.

В силу отмеченного выше свойства матрицы соединений быстрой машины S, заключающегося в том, что в каждом столбце матрицы могут содержаться лишь одинаковые пары, матрица обладает следующим свойством: в одном Столбце матрицы не могут содержаться две пары с одинаковым первым и различными вторыми индексами. Это означает, что диаграмму состояний машины можно, по желанию, трактовать как диаграмму состояний последовательностной машины типа П — П либо последовательностной машины типа П — Н (см. об этом замечание в § 3.4).

Будем считать, например, что эта диаграмма является диаграммой состояний машины типа П — Н, и покажем, как далее строится релейная схема, реализующая эту машину. По диаграмме состояний можно восстановить основную таблицу автомата и таблицу преобразователя машины . В нашем примере эти таблицы соответственно имеют вид табл. 10.9 и табл. 10.10.

Таблица 10.9

Таблица 10.10

Таблицу 10.9 можно трактовать как таблицу переходов Хафмана; достаточно лишь обвести квадратиками равновесные состояния , т. е. те, индексы которых совпадают с номером строки. После этого табл. 10.9 примет вид табл. 10.11.

Имея табл. 10.10 и 10.11, можно реализовать машину с помощью релейной схемы способом, описанным в § 5.4.

Для этого зашифруем сцмволы двоичными числами так, как это показано в табл. . Тогда табл. 10.9 и 10.10 можно представить в форме табл. 10.15 и 10.16.

По табл. 10.15 и 10.16 строится объединенная табл. 10.17.

Табл. 10.17 задает три логические функции и Z от четырех независимых переменных . Рассмотрим теперь как состояния входных контактов, а как состояние контактов вторичных реле, и как состояния (наличие или отсутствие токов) обмоток этих вторичных реле. Будем Z полагать состояниями обмотки выходного реле. Любая контактная сеть, составленная из контактов и включен

Таблица 10.11

Таблица 10.12

Таблица 10.13

Таблица 10.14

в нее обмотки и Z, которые реализуют таблицу логических функций типа табл. 10.17, реализует и синтезируемую машину . Такая сеть может быть по табл. 10.17 построена любым приемом (см. гл. II).

Таблица 10.15

Таблица 10.16

Таблица 10.17

Теперь целесообразно сравнить изложенный выше метод построения машины , которая воспроизводит на состояниях равновесия заданную машину G, с методом Хафмана, предназначенным для решения этой задачи и описанным в § 5.4.

Главное отличие метода Хафмана от метода, изложенного в этой главе, состоит в том, что область применимости последнего ничем не ограничена, тогда как метод Хафмана, как уже отмечалось в гл. V, можно применять для построения лишь таких последовательностных машин, у которых будущее состояние входящего в эти машины автомата однозначно определяется состояниями входа и выхода машины в настоящий момент.

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

В заключение этого параграфа заметим, что алгоритм размножения состояний, описанный в § 10.3, применйм и в том случае, когда заданная медленная машина О имеет ограничения типа Ауфенкампа. Построенная с помощью этого алгоритма быстрая машина S, которая воспроизводит относительно машину G, также будет иметь ограничения типа Ауфенкампа. Поэтому для ее минимизации следует пользоваться приемом, описанным в конце § 9.8 (или каким-либо иным способом полной минимизации машин с ограничениями типа Ауфенкампа).

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