Мінімізація ДСкА

В інформатиці, чи якщо точніше в теорії автоматів, мінімізація ДСкА — це задача перетворення даного детермінованого скінченного автомата (ДСкА) в еквівалентний ДСкА який має мінімальне число станів. Два ДСкА називаються еквівалентними, якщо вони описують одну і ту ж регулярну мову. Існує кілька різних алгоритмів розв'язання цієї задачі, які описуються в підручниках теорії автоматів.

Мінімальний ДСкА

Для кожної регулярної мови яка може прийматись ДСкА, існує ДСкА з мінімальною кількістю станів (і відповідно з мінімальними ресурсами необхідними для програмування та використання) і цей ДСкА єдиний (з точністю до перейменування станів).^[1]

Є три класи станів в оригінальному ДСкА які можуть бути видалені/об'єднані без впливу на мову яку розпізнає автомат.

• Недосяжні стани в які автомат ніколи не переходить з початкового для будь-яких вхідних послідовностей.
• Мертві стани — нефінальні стани, переходи по кожному символу з яких ведуть на них же.
• Невідрізнювані стани, перебуваючи в яких автомат приймає одні й ті ж вхідні рядки.

Мінімізація ДСкА зазвичай виконується за три кроки, видаляючи чи об'єднуючи відповідні класи станів. Так як елімінація невідрізнюваних станів обчислювально найважча, вона зазвичай виконується останньою.

Недосяжні стани

Стан p ДСкА M=(Q, Σ, δ, q₀, F) недосяжний, якщо не існує рядка w з ∑* для якого p=δ(q₀, w). Їх можна знайти за допомогою наступного алгоритму:

let reachable_states := {q0};
let new_states := {q0};
do {
    temp := the empty set;
    for each q in new_states do
        for all c in ∑ do
            temp := temp ∪ {p such that p=δ(q,c)};
        end;
    end;
    new_states := temp \ reachable_states;
    reachable_states := reachable_states ∪ new_states;
} while(new_states ≠ the empty set);
unreachable_states := Q \ reachable_states;

Невідрізнювані стани

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

Алгоритм для об'єднання невідрізнюваних станів^[2], базується на розбитті всіх станів скінченного автомата на групи згідно з їхньою поведінкою. Ці групи являють собою класи еквівалентності. Два стани з одного класу еквівалентні, якщо вони мають однакову поведінку на всіх вхідних станах. Тобто, для будь-яких двох станів ${\displaystyle p_{1},\,p_{2}}$ які належать одній множині в розбитті ${\displaystyle P}$, і для кожного вхідного слова ${\displaystyle w}$, переходи визначені ${\displaystyle w}$ приводять або до двох приймаючих станів, або до двох неприймаючих станів.

Наступний псевдокод описує алгоритм:

P := {{all accepting states}, {all nonaccepting states}};
Q := {{all accepting states}};
while (Q is not empty) do
     choose and remove a set A from Q
     for each c in ∑ do
          let X be the set of states for which a transition on c leads to a state in A
          for each set Y in P for which X ∩ Y is nonempty do
               replace Y in P by the two sets X ∩ Y and Y \ X
               if Y is in Q
                    replace Y in Q by the same two sets
               else
                    add the smaller of the two sets to Q
          end;
     end;
end;

Алгоритм починає роботу з розбиття яке є занадто грубим: кожна пара станів вважається еквівалентною. Він поступово розбиває класи еквівалентності на все менші частини. Стани в різних частинах гарантовано нееквівалентні.

Перше розбиття — це розділення станів які є очевидно поводяться по різному: фінальні та нефінальні стани. Після цього алгоритм по черзі вибирає множину ${\displaystyle A}$ з поточного розбиття та вхідний символ ${\displaystyle c}$, і розбиває кожну з множин в розбитті на дві (можливо порожні) підмножини: підмножину станів які приводять по символу ${\displaystyle c}$ в стан з множини ${\displaystyle A}$, та стани які переходять в стани з іншої множини. Так як стани з різних множин розбиття гарантовано не еквівалентні, то й наші дві підмножини теж. Алгоритм закінчує роботу коли більше не може знайти розбиттів такого типу.

В найгіршому випадку час роботи алгоритму ${\displaystyle O(ns\log n)}$, де ${\displaystyle n}$ — число початкових станів, а ${\displaystyle s}$ — розмір алфавіту.

Мінімізація НДСкА

Вищезгадані алгоритми не працюють для недетермінованих автоматів (НДСкА). Знаходження ефективного (поліноміального) алгоритму мінімізації НДСкА неможливе, якщо тільки не виконується рівність класів P і NP.^[3]

Див. також

• Алгоритми мінімізації скінченних автоматів