ГЛАВА IX. ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН

§ 9.1. Постановка задачи о распознавании эквивалентных состояний

В гл. III, вводя понятие о входных последовательностях, мы говорили уже о том, что класс возможных входных последовательностей может быть ограничен. Затем со случаем такого рода мы встречались в гл. V. В этой главе наряду со случаем, когда класс возможных входных последовательностей не ограничен, мы будем рассматривать и случаи, когда на класс возможных входных последовательностей наложены некоторые ограничения (см. § 9.7). Приведем вновь некоторые примеры ограничений:

а) входная последовательность не может иметь два одинаковых символа подряд;

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

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

г) если где-либо во входной последовательности появился символ или , то появляться не может.

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

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

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

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

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

Рис. 9.1.

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

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

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

Ограничения такого типа впервые рассматривались Ауфенкампом. Поэтому мы будем в дальнейшем такой тип ограничений входных последовательностей называть ограничениями типа Ауфенкампа.

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

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

Рассматривая пока лишь ограничения последовательностей «в себе», введем понятие об эквивалентности состояний П-машины (конечного автомата).

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

Если машины и G совпадают, то мы получаем определение эквивалентности относительно L двух состояний одной П-машины (автомата).

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

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

Задана последовательностная машина и множество допустимых входных последовательностей L. Требуется выработать прием, позволяющий для любых двух состояний П-машины ответить на вопрос: эквивалентны ли эти два состояния относительно множества ?

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

Группой эквивалентных относительно L состояний мы здесь называем такое множество состояний П-машины, в котором: 1) любые два состояния эквивалентны (Относительно L; 2) любое из состояний внутри группы не эквивалентно относительно L никакому состоянию вне группы.

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

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

Однако, как будет показано в следующем параграфе, эта задача алгоритмически неразрешима. Поэтому мы в §§ 9.3 и 9.4 рассмотрим несколько типичных частных случаев, для которых алгоритм распознавания эквивалентности может быть построен.