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

Сложность
Средний 50%

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

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

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

минимизация AFD

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

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

Пример

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

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

 вбпротив
0(Я)2(II)5(II)Р (я)
2(II)Р (я)Р (я)Р (я)
5(II)Р (я)Р (я)8 (II)
8 (II)Р (я)Р (я)8 (II)
Р (я)Р (я)Р (я)Р (я)

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

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

 вбпротив
0(Я)2(II)5(II)Р (III)
2(II)Р (III)Р (III)Р (III)
5(II)Р (III)Р (III)8 (II)
8 (II)Р (III)Р (III)8 (II)
Р (III)Р (III)Р (III)Р (III)

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

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

 вбпротив
0(Я)2(IV)5(II)Р (III)
2(IV)Р (III)Р (III)Р (III)
5(II)Р (III)Р (III)8 (II)
8 (II)Р (III)Р (III)8 (II)
Р (III)Р (III)Р (III)Р (III)

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

 вбпротив
яIVIIIII
IVIIIIIIIII
IIIIIIIIII
IIIIIIIIIIII

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

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

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

минимизация AFD

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

 ВБПРОТИВД
положить началояIIяII

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

АлфавитВБПРОТИВД
вIIIIяII
ОяIIяII

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

 ВБПРОТИВД
положить началояIIяII
вIIIIяII
0яIIяII
Разделение 1яIIIIIII

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

 ВБПРОТИВД
положить началояIIяII
вIIIIяII
0яIIяII
Разделение 1яIIIIIII
ВIIIIIIIII
0IIIIIIIIII
Разделение 2яIIIIIII

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

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

минимизация AFD

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

минимизация AFD
Делиться
ru_RURU