Минимизация 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) |
|---|---|---|
| (а, б) | (а, б) | (в, г, д) |
| (в, г, д) | (в, г, д) | (е) |
| (е) | (е) | (е) |