Третий этап

Процедура получения автомата S' = (A', Z', W', d', l', a₁'), представляемого найденным для исходного автомата S замкнутым покрытием D, достаточно проста. Каждому классу совместимости C_i Î D ставится в соответствие состояние a_i' нового автомата S'. Для каждого класса C_i Î D и каждого z_i Î Z вычисляем множество следующих за C_i состояний T_if = d(C_i, Z_f).

Функции переходов и выходов определяются как

В качестве начального состояния a ₁' автомата S' выбирается любое состояние из множества A', соответствующее некоторому классу совместимости, содержащему начальное состояние a₁автомата S.

Применим эту процедуру к нашему примеру. В качестве исходного замкнутого покрытия, как уже отмечалось выше, возьмем множество максимальных классов совместимости Ф = {{1,2},{1,4},{2,3},{3,4,5}} = { b ₁, b ₂, b ₃, b ₄}. Классу совместимости {1,2} ставим в соответствие состояние b ₁ нового автомата. За классом {1,2} по входу z ₁ следует класс {2,3}, по входу z ₂ - класс {5}, по z ₃ - класс {2,3}, по z ₄ - {2}. Следовательно, чтобы автомат, получающийся в результате совмещения состояний {1,2} был детерминированным, должны быть совместимы состояния {1,2}, {2,3}, {5}, {2,3}, {2}, что в нашем случае верно. Таким образом получаем следующие значения функций переходов и выходов:

d'(b ₁, z₁) = b ₃, d'(b ₁, z₂) = b ₄, d'(b ₁, z₃) = b ₃, d'(b ₁, z₄) = b ₃.

l'(b ₁, z₁) = w₁, l'(b ₁, z₂) = w₂, l'(b ₁, z₃) = w₁, l'(b ₁, z₄) = w₁.

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

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

В частности, в нашем примере минимальным замкнутым покрытием является {{1,2},{2,3},{4,5}}. Соответствующий этому покрытию минимальный автомат имеет всего три состояния: