Алгоритм минимизации числа состояний ДКА

Неформальное описание алгоритма минимизации числа состояний ДКА

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

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

Изначально разбиение состояний состоит из двух групп: заключительные и незаключительные.

Основной шаг: взять некоторую группу состояний, например и входной символ и посмотреть, какие переходы имеют состояния из группы по этому входному символу.

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

Этот процесс разбиения продолжается до тех пор, пока не останется групп, подлежащих разбиению.

Вход. ДКА .

Выход. ДКА , допускающий тот же язык, что и ДКА , и имеющий наименее возможное число состояний.

Метод.

1. Построить начальное разбиение множества состояний с двумя группами: заключительные и незаключительные .

2. Применить процедуру разбиения к текущему разбиению и получить новое разбиение .

3. Если , то перейти к шагу 2, иначе – шаг 4.

4.

- Выбрать одно из состояний в каждой группе разбиения в качестве представителя этой группы – это будут состояния ДКА .

- Переход исходного ДКА заменить переходом от представителя группы, содержащей , к представителю группы, содержащей .

- Начальное состояние ДКА - представитель группы, содержащей начальное состояние ДКА

- Заключительными состояниями ДКА объявить представителей групп, содержащих заключительные состояния исходного ДКА .