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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Мінімальний ДСкА[ред.ред. код]

Для кожної регулярної мови яка може прийматись ДСкА, існує ДСкА з мінімальною кількістю станів (і відповідно з мінімальними ресурсами необхідними для програмування та використання) і цей ДСкА єдиний (з точністю до перейменування станів). [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 indo
            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_1,\, p_2 які належать одній множині в розбитті P, і для кожного вхідного слова w, переходи визначені 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 indo
          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;

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

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

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

Мінімізація НДСкА[ред.ред. код]

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


Зноски[ред.ред. код]

  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 
  • 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 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 
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001), Introduction to Automata Theory, Languages, and Computation (2nd вид.), Addison-Wesley .
  • 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 .
  • 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 .

Посилання[ред.ред. код]