Минимизация преобразователя частоты

Минимизация преобразователя частоты

Теорема Майхилла-Нероде (минимизация преобразователь частоты). Пусть L — рациональный язык. Среди всех L-распознающих AFD есть один и только один, имеющий минимальное количество состояний.

Прежде чем свернуть AFD, его необходимо завершить, т. е. добавить состояние мусора, подобное состоянию R на диаграмме ниже.

Алгоритм минимизации следующий:

1. Завершите AFD с именем D
2. Постройте начальный раздел ∏, содержащий два набора состояний I и II, таких, что ∏={I=(конечные состояния принятия D), II=(другие состояния состояний D)}
3. Для каждого состояния D выполните
   1. Построить таблицу переходов
   2. Отметьте состояния отправления и прибытия в соответствии с их группой ∏
4. Если состояния одной и той же группы ∏ имеют разное поведение
   1. Разделите состояния в новую группу (например, III) — желательно делать только одно разделение за итерацию.
   2. Вернуться к 3
5. Конец: новые состояния - это группы ∏

Пример

Вернемся к приведенному выше примеру AFD. Это действительно детерминировано, как показано в таблице переходов.

Давайте посмотрим на таблицу переходов на шаге 3:

Мы замечаем, когда в группе I поведение O и R расходится, поэтому разделим их на две группы: I=(0) и III=(R)

Вот новая таблица переходов:

Мы замечаем, когда в группе II поведение 2 и 5, 8 расходится, поэтому разделим их на две группы: II=(5, 8) и IV=(2)

Вот новая таблица переходов:

Мы больше не наблюдаем каких-либо расхождений между группами, поэтому мы можем выполнить таблицу перехода с минимизированным DFA, дающим следующую таблицу перехода:

Начальным состоянием является I (по отношению к его эквиваленту в D), а конечными состояниями автомата являются II и IV (по отношению к их эквивалентам в D).

Другой пример

Рассмотрим следующий автомат:

Фаза инициализации позволяет получить неконцевую группу I и концевую группу II:

Рассмотрим переходы для каждого состояния по группам I и II:

Затем мы разделяем наборы. Два состояния находятся в одном множестве, если они уже были в одном множестве и если переходы ведут в одни и те же множества. В этом примере B и D ведут себя точно так же, поэтому они остаются вместе. С другой стороны, A и C, которые были частью одного и того же набора, ведут себя по-разному на символе «a». Следовательно, множество, обозначенное I, делится на два. Итак, мы получаем:

Текущая ситуация (линия Balance 1) отличается от исходной. Итак, мы должны начать сначала.

Строка «Разделение 2» идентична строке «Разделение 1». Поэтому в каждом из оставшихся наборов состояния неразличимы (они ведут себя точно так же и поэтому являются «избыточными»).

Таким образом, мы можем построить новый автомат связывая состояние с каждым набором. Переходы указаны в таблице. Начальное состояние — это состояние, содержащее начальное состояние стартового автомата: здесь I содержит состояние A, начальное состояние. Конечные состояния — это состояния, соответствующее множество которых содержит хотя бы одно конечное состояние: здесь II содержит B и D, которые являются конечными.

На данный момент мы «слили» неразличимые состояния. Теперь необходимо удалить все оставшиеся бесполезные состояния. В нашем примере состояние III является стерильным состоянием (неконечным и без перехода), поэтому бесполезным. Поэтому его необходимо удалить. Отсюда минимальный детерминированный автомат следующего рисунка: