7.5. Метод уменьшения числа состояний автоматов с ограничениями на входе

Как стало ясно из предыдущих параграфов, определение минимальной формы автомата с ограничениями на входе — процесс очень трудоемкий. В тех случаях, когда не обязательно требуется минимальная форма, но уменьшение числа состояний все же желательно, может быть использован упрощенный метод, который часто дает значительно сокращенную форму (а иногда и минимальную форму) по сравнению с заданным автоматом. Предлагаемый метод, по существу, является методом таблиц минимизации автоматов без ограничений на входе, описанным в § 3.6. Единственное различив

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

В качестве примера в таблицах 7.5 и 7.6 представлены соответственно таблица и таблица для автомата заданного таблицей 7.1. Таблица получена путем замены прочерков в клетках подтаблицы таким образом, чтобы

Таблица 7.5. Таблица для

Таблица 7.6. Таблица для

множества стали -эквивалентным разбиением. Заметим, что возможны также другие замены прочерков в клетках, но при выбранной замене получается наименьшее число классов -эквивалентности. Таблица получена заменой прочерков в клетках таблицы таким образом, что множества становятся -эквивалентным разбиением. Так как это — конечная таблица то является эквивалентным разбиением, из которого сокращенная форма может быть построена по алгоритму 7.2. Случайно получилось, что множества также составляют минимальную правильную группировку, так что сокращенный автомат, полученный на основе является также минимальной формой автомата (действительно, это автомат рис. 7.2). Заметим, однако, что другая замена прочерков клеток в таблице может

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

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

Рис. 7.4. Автомат А33.

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

группировка может быть образована из пересекающихся совместимых множеств. Например, рассмотрим автомат А33, представленный графом на рис. 7.4 и таблицей 7.7. в этом случае будет или . В каждом из этих случаев будет , а это означает, что ЛЗЗ не может быть минимизирован предложенным методом. С другой стороны, если применить общий метод минимизации, то окажется, что являются С-множествами для А 33 и что эти два С-множества составляют правильную группировку.

Таблица 7.7

Автомат А 33

Рис. 7.5. Автомат А33.

Поэтому А 33 имеет минимальную форму , которая состоит из двух состояний. На рис. 7.5 приведена эта минимальная форма, в которой состояния 1 и 2 представляют соответственно множества автомата А33.