Interested Article - Минимизация ДКА

Минимизация ДКА — построение по детерминированному конечному автомату (ДКА) эквивалентного ДКА, имеющего наименьшее возможное число состояний.

Минимальный ДКА

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

Алгоритмы

Алгоритм Хопкрофта

1. Разделить все состояния ДКА на две группы: группу конечных состояний и группу неконечных состояний.

2. Для каждого символа алфавита, проверить, в какую из групп перейдет автомат из каждого состояния, используя данный символ. Если из состояний A и B можно перейти в состояния C и D соответственно, то состояния A и B будут считаться эквивалентными по данному символу, если состояния C и D принадлежат одной и той же группе.

3. На основе этой информации разделить каждую группу на подгруппы, где состояния, эквивалентные по всем символам алфавита, находятся в одной подгруппе.

4. Повторять шаги 2 и 3 до тех пор, пока группы перестанут разделяться.

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

6. Удалить недостижимые состояния.

Алгоритм Бжозовского

Пусть ${\mathcal {A}}$ ${\mathcal {A}}$ — ДКА. Обозначим через $r({\mathcal {A}})$ $r({\mathcal {A}})$ инвертированный автомат ${\mathcal {A}}$ ${\mathcal {A}}$ . Через $d({\mathcal {A}})$ $d({\mathcal {A}})$ обозначим детерминизированный автомат, полученный из ${\mathcal {A}}$ ${\mathcal {A}}$ процедурой построения подмножеств. Имеет место следующий результат :

Пусть автомат ${\mathcal {A}}$ ${\mathcal {A}}$ распознаёт язык $L$ $L$ . Тогда минимальный ДКА для языка $L$ $L$ может быть найден как ${\mathcal {A}}_{L}=drdr({\mathcal {A}}).$ ${\mathcal {A}}_{L}=drdr({\mathcal {A}}).$