7.4. Определение минимальных форм

Множество входящее в правильную группировку будем называть совместимым множеством.

Лемма 7.1. Каждая пара состояний в совместимом множестве должна быть совместимой.

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

В дальнейшем С-множеством автомата М будем называть множество состояний автомата М, которое удовлетворяет двум следующим условиям: (1) каждая пара состояний из С-множества совместима; (2) это множество не является подмножеством другого С-множества, содержащего большее число состояний. Лемма 7.1 тогда позволяет сформулировать следующую теорему.

Теорема 7.2. Каждое множество в правильной группировке автомата М должно быть или С-множеством, или подмножеством С-множества автомата М.

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

Перечень всех возможных С-множеств может быть легко составлен, когда задан перечень всех совместимых пар. Перечень всех совместимых пар в свою очередь может быть получен из таблицы пар, как описано в § 7.2. Процедура получения всех С-множеств из совместимых пар состоит в следующем.

Алгоритм 7.1. Даны все совместимые пары автомата М; требуется определить все С-множества автомата М. (1) Пусть первый перечень множеств состояний состоит из всех совместимых пар автомата и из отдельных состояний, не принадлежащих ни к одной из совместимых пар. Полагаем . Для каждого множества состояний содержащихся в перечне, выполняем следующие операции. Определяем I состояний автомата М, скажем что не включено в данное множество, и таких, что каждое образует совместимую пару с каждым состоянием из этого множества. Заменяем множество множествами , то заменим множество самим собой. (3) Исключаем из нового перечня множеств все одинаковые множества, оставляя по одному представителю от каждой группы одинаковых множеств, и все множества, являющиеся подмножествами других множеств. Пусть полученный таким образом перечень будет перечнем. (4) (а) Если перечень отличается от перечня, то увеличиваем k на единицу и возвращаемся к (2). (б) Если перечень совпадает

с , то он является перечнем всех С-множеств автомата М.

Выполнение алгоритма 7.1 облегчается построением матрицы совместимости, обозначаемой элемент которой равен 1, если или — совместимые пары состояний, и 0 в противном случае. По построению, если в каждой строке содержится 1 в каком-либо данном столбце то образует совместимые пары с каждым состоянием из множества . Следовательно, если множество в (k-1)-м перечне и если строки матрицы совмещений содержат единицу в столбце множество должно быть заменено множеством .

В качестве примера рассмотрим автомат изображенный на рис. 7.1. В таблице 7.2 получены все совместимые пары автомата из которых может быть составлен первый перечень:

Матрица совмещений для которая может быть построена непосредственно по первому перечню, представлена выражением (7.1):

    (7.1)

Из этой матрицы и первого перечня можно найти второй перечень:

Например, обе строки 1 и 2 в (7.1) содержат единицы в столбцах 3 и 5; поэтому множество первого перечня заменяется множествами . Так как в матрице нет столбцов, в которых обе строки 2 и 4 содержат единицу, то множество из первого перечня заменяется множеством . Из (7.1) и второго перечня можно найти третий перечень: . Так как этот перечень такой же, как и четвертый, то он содержит все С-множества автомата .

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

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

Алгоритм 7.2. Дана минимальная правильная группировка автомата М, а именно надо построить минимальную форму с множеством состояний . Полагаем k = 1. (2) (а) Если все клетки в подтаблицах автомата М, расположенные на пересечении строк и столбца содержат прочерк, то в Клетках подтаблиц

и автомата М, расположенных на пересечении строки и столбца тоже проставим прочерк, (б) Если, по крайней мере, одна из клеток в подтаблице автомата М, расположенных на пересечении строк и столбца не содержит прочерка, то проставим содержимое таких клеток в клетке, расположенной на пересечении строки и столбца в подтаблице автомата (в) Если в подтаблице автомата М есть клетки без прочерка, расположенные на пересечении строк и столбца то находим совместимое множество в которое включены все элементы, соответствующие этим клеткам. Пусть будет содержимым клетки, общей для строки и столбца в подтаблице автомата М. (3) (а) Если то увеличиваем на 1 и возвращаемся к (2). (б) Если , то таблица переходов для М построена.

Таблица 7.3 представляет собой таблицу переходов автомата , который является минимальной формой автомата .

Таблица 7.3. Автомат

Таблица 7.4. Автомат

Эта таблица построена на основе минимальной правильной группировки Множества группировки представлены в состояниями 1, 2, 3 соответственно. Таблица 7.4 представляет собой таблицу переходов автомата являющегося минимальной формой . Таблица построена на основе минимальной правильной группировки

множества которой представлены в состояниями 1, 2, 3 соответственно.

На рис. 7.2 и 7.3 приведены графы переходов автоматов соответственно. Для иллюстрации квазиэквивалентности автоматов по отношению к автомату рассмотрим входную последовательность которая допустима для состояния 1 автомата

Рис. 7.2. Автомат

Рис. 7.3. Автомат

Когда эта последовательность прикладывается к в состоянии 1 или к в состоянии 1, или к в состоянии 1 (два последних состояния квазиэквивалентны первому), видно, что реакция автоматов на эту последовательность одинакова у всех автоматов и выражается так: 10101100000111.