|
Мінімізація ДСкАВ інформатиці, чи якщо точніше в теорії автоматів, мінімізація ДСкА — це задача перетворення даного детермінованого скінченного автомата (ДСкА) в еквівалентний ДСкА який має мінімальне число станів. Два ДСкА називаються еквівалентними, якщо вони описують одну і ту ж регулярну мову. Існує кілька різних алгоритмів розв'язання цієї задачі, які описуються в підручниках теорії автоматів. Мінімальний ДСкАДля кожної регулярної мови яка може прийматись ДСкА, існує ДСкА з мінімальною кількістю станів (і відповідно з мінімальними ресурсами необхідними для програмування та використання) і цей ДСкА єдиний (з точністю до перейменування станів).[1] Є три класи станів в оригінальному ДСкА які можуть бути видалені/об'єднані без впливу на мову яку розпізнає автомат.
Мінімізація ДСкА зазвичай виконується за три кроки, видаляючи чи об'єднуючи відповідні класи станів. Так як елімінація невідрізнюваних станів обчислювально найважча, вона зазвичай виконується останньою. Недосяжні стани
Стан p ДСкА M=(Q, Σ, δ, q0, F) недосяжний, якщо не існує рядка w з ∑* для якого p=δ(q0, 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], базується на розбитті всіх станів скінченного автомата на групи згідно з їхньою поведінкою. Ці групи являють собою класи еквівалентності. Два стани з одного класу еквівалентні, якщо вони мають однакову поведінку на всіх вхідних станах. Тобто, для будь-яких двох станів які належать одній множині в розбитті , і для кожного вхідного слова , переходи визначені приводять або до двох приймаючих станів, або до двох неприймаючих станів. Наступний псевдокод описує алгоритм: 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;
Алгоритм починає роботу з розбиття яке є занадто грубим: кожна пара станів вважається еквівалентною. Він поступово розбиває класи еквівалентності на все менші частини. Стани в різних частинах гарантовано нееквівалентні. Перше розбиття — це розділення станів які є очевидно поводяться по різному: фінальні та нефінальні стани. Після цього алгоритм по черзі вибирає множину з поточного розбиття та вхідний символ , і розбиває кожну з множин в розбитті на дві (можливо порожні) підмножини: підмножину станів які приводять по символу в стан з множини , та стани які переходять в стани з іншої множини. Так як стани з різних множин розбиття гарантовано не еквівалентні, то й наші дві підмножини теж. Алгоритм закінчує роботу коли більше не може знайти розбиттів такого типу. В найгіршому випадку час роботи алгоритму , де — число початкових станів, а — розмір алфавіту. Мінімізація НДСкАВищезгадані алгоритми не працюють для недетермінованих автоматів (НДСкА). Знаходження ефективного (поліноміального) алгоритму мінімізації НДСкА неможливе, якщо тільки не виконується рівність класів P і NP.[3] Див. такожПримітки
Література
Посилання
|
