Минимизация DFA

Минимизация DFA с использованием теоремы Myphill-Nerode

Алгоритм

Input - DFA

Output - Минимизированный DFA

Step 1- Нарисуйте таблицу для всех пар состояний (Q i , Q j ), которые не обязательно связаны напрямую [изначально все не отмечены]

Step 2- Рассмотрите каждую пару состояний (Q i , Q j ) в DFA, где Q i ∈ F и Q j ∉ F, или наоборот, и отметьте их. [Здесь F - набор конечных состояний]

Step 3 - Повторяйте этот шаг, пока мы больше не сможем отмечать состояния -

Если есть немаркированная пара (Q i , Q j ), отметьте ее, если пара {δ (Q i , A), δ (Q i , A)} помечена для некоторого входного алфавита.

Step 4- Объедините все немаркированные пары (Q i , Q j ) и сделайте их единым состоянием в сокращенном DFA.

пример

Давайте воспользуемся алгоритмом 2, чтобы минимизировать DFA, показанный ниже.

Step 1 - Рисуем таблицу для всех пар состояний.

а б c d е ж
а
б
c
d
е
ж

Step 2 - Мы отмечаем пары состояний.

а б c d е ж
а
б
c
d
е
ж

Step 3- Попробуем пометить пары состояний зеленой галочкой переходно. Если мы введем 1 для состояния «a» и «f», он перейдет в состояние «c» и «f» соответственно. (c, f) уже отмечен, поэтому мы отметим пару (a, f). Теперь мы вводим 1 в состояние «b» и «f»; он перейдет в состояние «d» и «f» соответственно. (d, f) уже отмечен, поэтому мы отметим пару (b, f).

а б c d е ж
а
б
c
d
е
ж

После шага 3 у нас есть комбинации состояний {a, b} {c, d} {c, e} {d, e}, которые не отмечены.

Мы можем рекомбинировать {c, d} {c, e} {d, e} в {c, d, e}

Следовательно, мы получили два комбинированных состояния как - {a, b} и {c, d, e}

Таким образом, окончательный свернутый DFA будет содержать три состояния {f}, {a, b} и {c, d, e}.

Минимизация DFA с использованием теоремы эквивалентности

Если X и Y - два состояния в DFA, мы можем объединить эти два состояния в {X, Y}, если они не различимы. Два состояния различимы, если существует хотя бы одна строка S, такая, что одно из δ (X, S) и δ (Y, S) принимает, а другое не принимает. Следовательно, ДКА минимален тогда и только тогда, когда все состояния различимы.

Алгоритм 3

Step 1 - Все штаты Q разделены на две перегородки - final states а также non-final states и обозначаются P0. Все государства в перегородке равны 0 - й эквивалент. Возьми счетчикk и инициализируйте его с помощью 0.

Step 2- Увеличить k на 1. Для каждого раздела в P k разделить состояния в P k на два раздела, если они k-различимы. Два состояния в этом разделе X и Y являются k-различимыми, если есть входS такой, что δ(X, S) а также δ(Y, S) (k-1) -различимы.

Step 3- Если P k ≠ P k-1 , повторите шаг 2, в противном случае перейдите к шагу 4.

Step 4- Объедините k- е эквивалентные множества и сделайте их новыми состояниями сокращенного DFA.

пример

Давайте рассмотрим следующий DFA -

q δ (q, 0) δ (д, 1)
а б c
б а d
c е ж
d е ж
е е ж
ж ж ж

Давайте применим вышеуказанный алгоритм к вышеуказанному DFA -

  • P 0 = {(c, d, e), (a, b, f)}
  • P 1 = {(c, d, e), (a, b), (f)}
  • P 2 = {(c, d, e), (a, b), (f)}

Следовательно, P 1 = P 2 .

В сокращенном DFA есть три состояния. Уменьшенный DFA выглядит следующим образом -

Q δ (q, 0) δ (д, 1)
(а, б) (а, б) (в, г, д)
(в, г, д) (в, г, д) (е)
(е) (е) (е)