От любой правильной группировки автомата М можно перейти к автомату М, реализующему М, путем совмещения состояний, входящих в один и тот же элемент группировки. Если {qi, qj, … , qk} – элемент правильной группировки S автомата М, то в автомате М ему соответствует состояние, реализующее любое из состояний qi, qj, … , qk. Если S – минимальная правильная группировка, то построенный по ней автомат М будет обладать минимальным числом состояний среди всех автоматов, реализующих автомат М.

Чтобы получить множество состояний Q автомата М, надо каждому элементу Si  S поставить в соответствие состояние qi  Q. Функции  и  получаются следующим образом.

Пусть q(i) – некоторое (любое) состояние автомата М, принадлежащее элементу Si  S. Если (а, q(i)) = b, то (а, qi) = b. Если для всех q(i) из Si значение (а, q(i)) не определено, то значение (а, qi) считается неопределенным.

Если значение (а, q(i)) не определено для всех q(i)  Si, то (a, qi) считается неопределенным. Обозначим символом (а, Si) множество, непосредственно производное от множества Si  S по входному символу а (если значение (а, q(i)) не определено для всех q(i)  Si, то (а, Si) = ). Тогда (a, qi)  qj, где qj соответствует любому Sj  S, для которого (а, Si)  Sj.

Рассмотрим заимствованный из работы [16] пример построения автомата по правильной группировке, на котором продемонстрируем, что минимизация частичного автомата не сводится к минимизации полного автомата. Пусть табл. 20.1 представляет таблицу переходов и выходов заданного частичного автомата. Все два варианта доопределения представлены в табл. 20.2 и табл. 20.3.