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

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

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

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

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

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

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

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

Стан 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; 

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

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

Алгоритм для об'єднання невідрізнюваних станів, базується на розбитті всіх станів скінченного автомата на групи згідно з їхньою поведінкою. Ці групи являють собою класи еквівалентності. Два стани з одного класу еквівалентні, якщо вони мають однакову поведінку на всіх вхідних станах. Тобто, для будь-якхи двох станів ${\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.

Див. також

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

Примітки

1. Hopcroft, Motwani та Ullman, (2001), Section 4.4.3, «Minimization of DFA's», p. 159.
2. Hopcroft, (1971)
3. Hopcroft, Motwani та Ullman, (2001), Section 4.4, Figure labeled «Minimizing the States of an NFA», p. 163.

Література

• Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), 4.13 Partitioning, The Design and Analysis of Computer Algorithms, Addison-Wesley, с. 157—162.
• Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), Minimization of Automata, Automata: from Mathematics to Applications, European Mathematical Society, arXiv:1010.5318
• Brzozowski, J. A. (1963), Canonical regular expressions and minimal state graphs for definite events, Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., с. 529—561, MR0175719.
• Câmpeanu, Cezar; Culik, Karel, II; Salomaa, Kai; Yu, Sheng (2001), State Complexity of Basic Operations on Finite Languages, 4th International Workshop on Automata Implementation (WIA '99), Lecture Notes in Computer Science, т. 2214, Springer-Verlag, с. 60—70, doi:10.1007/3-540-45526-4_6.
• Hopcroft, John (1971), An ${\displaystyle n\log n}$ algorithm for minimizing states in a finite automaton, Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York: Academic Press, с. 189—196, MR 0403320
• Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.).
• Leiss, Ernst (1981), Succinct representation of regular languages by Boolean automata, Theoretical Computer Science, 13 (3): 323—330, doi:10.1016/S0304-3975(81)80005-9, MR 0603263.
• Moore, Edward F. (1956), Gedanken-experiments on sequential machines, Automata studies, Annals of mathematics studies, no. 34, Princeton, N. J.: Princeton University Press, с. 129—153, MR 0078059.

Посилання

• Мінімізація ДСкА за допомогою теореми Майгілла-Нероде [ 21 червня 2015 у Wayback Machine.]