Cтраница 2
Описанный в предыдущем параграфе основной алгоритм минимизации автоматов основан на отождествлении всех совместимых между собой состояний. Часто оказывается удобным, однако, проводить отождествление лишь некоторой части совместимых состояний. В предыдущем параграфе все совместимые между собой состояния объединялись в один класс, называемый оо-классом. Система всех оо-классов осуществляла покрытие множества всех состояний заданных автоматов; иначе говоря, всякое состояние содержалось хотя бы в одном оо-классе. [16]
Совместимые состояния легко отыскиваются непосредственно по таблице переходов. Действительно, если в табл. 3.18 взять две строки j 1 и j - 3, которым, как было показано выше, соответствуют совместимые состояния / ii и / з, то легко заметить, что в каждом столбце стоят одинаковые цифры, характеризующие внутреннее состояние автомата. [17]
Множество внутренних состояний MC ffjbAfj Zi является совместимым, если все внутренние состояния из MC попарно совместимы. Такое множество можно заменить одним внутренним состоянием, присвоив ему, например, наименьший из номеров внутренних состояний, входящих в множество Мс - Удобным средством отыскания всех вариантов совместимости внутренних состояний является диаграмма совместимых состояний. Такая диаграмма состоит из узлов, обозначающих внутренние состояния автомата, каждая пара которых соединена ненаправленными линиями, если узлам, входящим в пары, соответствуют совместимые внутренние состояния. [18]