МИНИМИЗАЦИЯ ЧИСЛА СОСТОЯНИЙ АВТОМАТА

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

Для всюду определенных инициальных Мили автоматов задача минимизации сводится к построению приведенного автомата, эквивалентного данному (т. е. представляющего то же самое отображение, что и исходный автомат). В этом случае используют теорему о существовании и единственности приведенного автомата. Наиболее известным алгоритмом минимизации всюду определенных автоматов является алгоритм Ауфенкампфа—Хона, состоящий в построении последовательности спец. разбиений мн-ва состояний исходного автомата. В разбиении, получающемся на -ом шаге в один класс объединяются состояния, представляющие отображения, которые совпадают на всех словах длины . Через конечное число шагов такая последовательность разбиений стабилизируется на разбиении, определяющем некоторое отношение конгруэнтности. Фактор-автомат по этому отношению является приведенным автоматом, эквивалентным исходному. Алгоритм легко поддается автоматизации.

Решение задачи минимизации для частичных Х-К-автоматов предполагает перебор покрытий мн-ва состояний автомата классами состояний со свойством подстановки, т. е. таких покрытий что для любой пары , где существует такое, что для любых .

Цифровая вычислительная машина «Минск-32».

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

Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464—469]

0. В. Капитонова.