меньше переводят автомат из состояния 3 снова в состояние 3? (в) Имеет ли автомат полные контуры? Если имеет, то составьте входную последовательность, которая соответствует полному контуру, начинающемуся в состоянии 3.

Таблица 3 2.3

ГЛАВА 3

ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ

3.1. Введение

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

) Материал этой главы частично базируется на работах: Хаф-фмена (D. А. Huffman, -The Synthesis of Sequenlial Switching Networlcs, J. Franclin Inst., vol. 257, pp. 161-190, 275-303, 1954), Mypa (E. F. Moor e, Qedanken - Experiments on Sequential Machines, «Automata Studies*, pp. 129-153, Princeton University Press, Princeton, N. Y., 1956. Русский перевод: Э. Ф. Мур, Умозрительные эксперименты с последователъностными машинами. В сборнике «Автоматы» под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., 1956), Мили (О. Н. Mealy, Method for Synthesizing Sequential Circuits, Bell System Tech. J.. vol. 34, pp. 1054-1079, 1955) и Ауфен-кампа и Хона (D. D. А и f е п к а m р and F. Е. Н о h п, Analysis of Sequential Machines, IRE Trans., vol. EC-6, pp. 276-285, 1957).

) Вместо выражения «различимость автоматов AJ, (Т( и AJj будет употребляться выражение «различимость состояний ст/ и сту» во всех случаях, когда по контексту AJ, и AJj подразумеваются. Аналогично вместо выражения «реакция автомата AJ а» будет употребляться выражение «реакция состояния ст», когда по контексту автомат AJ подразумевается.

3.2. Эквивалентность состояний

В дальнейшем будем применять обозначение М\а для краткой записи высказывания: «автомат М в состоянии о».

Определение 3.1. Говорят, что состояние О; автомата Ml и состояние Оу автомата М2 эквивалентны, если yMia,- и VHjIOy под воздействием любой входной последовательности выдают одинаковые выходные последовательности. Если -Oi и Oj не эквивалентны, то говорят, что они различимы. Обозначения Mi и М2 могут относиться к одному и тому же автомату.

Таким образом, и Oj эквивалентны тогда и только тогда, когда, наблюдая внешние выходы, нельзя отличить автомат Mi, находящийся в начальном состоянии О;, от автомата М2, находящегося в начальной состоянии Oj). Состояния О; и Oj различимы тогда и только тогда, когда имеется хотя бы одна входная последовательность, подача которой как на VHJO;, так и на VHjIOy дает на выходах различные последовательности.

Эквивалентность О; и Оу обозначается равенством 0=0, а различимость о,- и Оу - неравенством а1Фа. Пользуясь определением 3.1, можно легко показать, что эквивалентные состояния обладают свойством рефлексивности (О; = о,), свойством симметричности (если ai = aj, то ау = а;) и свойством транзитивности (если 0 = 0 и ау = а, то ai = a). Следовательно, эквивалентность состояний может рассматриваться как обычное соотношение эквивалентности, которое применимо к множествам состояний любой мощности. Различимость состояний не обладает свойствами рефлексивности и транзитивности и, следовательно, может относиться только к парам состояний.

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