В інформатиці, чи якщо точніше в теорії автоматів, мінімізація ДСкА — це задача перетворення даного детермінованого скінченного автомата (ДСкА) в еквівалентний ДСкА який має мінімальне число станів. Два ДСкА називаються еквівалентними, якщо вони описують одну і ту ж регулярну мову. Існує кілька різних алгоритмів розв'язання цієї задачі, які описуються в підручниках теорії автоматів.
Мінімальний ДСкА
Для кожної регулярної мови яка може прийматись ДСкА, існує ДСкА з мінімальною кількістю станів (і відповідно з мінімальними ресурсами необхідними для програмування та використання) і цей ДСкА єдиний (з точністю до перейменування станів).
Є три класи станів в оригінальному ДСкА які можуть бути видалені/об'єднані без впливу на мову яку розпізнає автомат.
- Недосяжні стани в які автомат ніколи не переходить з початкового для будь-яких вхідних послідовностей.
- Мертві стани — нефінальні стани, переходи по кожному символу з яких ведуть на них же.
- Невідрізнювані стани, перебуваючи в яких автомат приймає одні й ті ж вхідні рядки.
Мінімізація ДСкА зазвичай виконується за три кроки, видаляючи чи об'єднуючи відповідні класи станів. Так як елімінація невідрізнюваних станів обчислювально найважча, вона зазвичай виконується останньою.
Недосяжні стани
Цей розділ не містить . |
Стан 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;
Невідрізнювані стани
Алгоритм Гопкрофта
Алгоритм для об'єднання невідрізнюваних станів, базується на розбитті всіх станів скінченного автомата на групи згідно з їхньою поведінкою. Ці групи являють собою класи еквівалентності. Два стани з одного класу еквівалентні, якщо вони мають однакову поведінку на всіх вхідних станах. Тобто, для будь-якхи двох станів які належать одній множині в розбитті , і для кожного вхідного слова , переходи визначені приводять або до двох приймаючих станів, або до двох неприймаючих станів.
Наступний псевдокод описує алгоритм:
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.
Див. також
Примітки
- Hopcroft, Motwani та Ullman, (2001), Section 4.4.3, «Minimization of DFA's», p. 159.
- Hopcroft, (1971)
- 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 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.]
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V informatici chi yaksho tochnishe v teoriyi avtomativ minimizaciya DSkA ce zadacha peretvorennya danogo determinovanogo skinchennogo avtomata DSkA v ekvivalentnij DSkA yakij maye minimalne chislo staniv Dva DSkA nazivayutsya ekvivalentnimi yaksho voni opisuyut odnu i tu zh regulyarnu movu Isnuye kilka riznih algoritmiv rozv yazannya ciyeyi zadachi yaki opisuyutsya v pidruchnikah teoriyi avtomativ Minimalnij DSkADlya kozhnoyi regulyarnoyi movi yaka mozhe prijmatis DSkA isnuye DSkA z minimalnoyu kilkistyu staniv i vidpovidno z minimalnimi resursami neobhidnimi dlya programuvannya ta vikoristannya i cej DSkA yedinij z tochnistyu do perejmenuvannya staniv Ye tri klasi staniv v originalnomu DSkA yaki mozhut buti vidaleni ob yednani bez vplivu na movu yaku rozpiznaye avtomat Nedosyazhni stani v yaki avtomat nikoli ne perehodit z pochatkovogo dlya bud yakih vhidnih poslidovnostej Mertvi stani nefinalni stani perehodi po kozhnomu simvolu z yakih vedut na nih zhe Nevidriznyuvani stani perebuvayuchi v yakih avtomat prijmaye odni j ti zh vhidni ryadki Minimizaciya DSkA zazvichaj vikonuyetsya za tri kroki vidalyayuchi chi ob yednuyuchi vidpovidni klasi staniv Tak yak eliminaciya nevidriznyuvanih staniv obchislyuvalno najvazhcha vona zazvichaj vikonuyetsya ostannoyu Nedosyazhni staniCej rozdil ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cej rozdil dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno Stan p DSkA M Q S d q0 F nedosyazhnij yaksho ne isnuye ryadka w z dlya yakogo p d q0 w Yih mozhna znajti za dopomogoyu nastupnogo algoritmu 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 d 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 Nevidriznyuvani staniAlgoritm Gopkrofta Algoritm dlya ob yednannya nevidriznyuvanih staniv bazuyetsya na rozbitti vsih staniv skinchennogo avtomata na grupi zgidno z yihnoyu povedinkoyu Ci grupi yavlyayut soboyu klasi ekvivalentnosti Dva stani z odnogo klasu ekvivalentni yaksho voni mayut odnakovu povedinku na vsih vhidnih stanah Tobto dlya bud yakhi dvoh staniv p 1 p 2 displaystyle p 1 p 2 yaki nalezhat odnij mnozhini v rozbitti P displaystyle P i dlya kozhnogo vhidnogo slova w displaystyle w perehodi viznacheni w displaystyle w privodyat abo do dvoh prijmayuchih staniv abo do dvoh neprijmayuchih staniv Nastupnij psevdokod opisuye algoritm 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 Algoritm pochinaye robotu z rozbittya yake ye zanadto grubim kozhna para staniv vvazhayetsya ekvivalentnoyu Vin postupovo rozbivaye klasi ekvivalentnosti na vse menshi chastini Stani v riznih chastinah garantovano neekvivalentni Pershe rozbittya ce rozdilennya staniv yaki ye ochevidno povodyatsya po riznomu finalni ta nefinalni stani Pislya cogo algoritm po cherzi vibiraye mnozhinu A displaystyle A z potochnogo rozbittya ta vhidnij simvol c displaystyle c i rozbivaye kozhnu z mnozhin v rozbitti na dvi mozhlivo porozhni pidmnozhini pidmnozhinu staniv yaki privodyat po simvolu c displaystyle c v stan z mnozhini A displaystyle A ta stani yaki perehodyat v stani z inshoyi mnozhini Tak yak stani z riznih mnozhin rozbittya garantovano ne ekvivalentni to j nashi dvi pidmnozhini tezh Algoritm zakinchuye robotu koli bilshe ne mozhe znajti rozbittiv takogo tipu V najgirshomu vipadku chas roboti algoritmu O n s log n displaystyle O ns log n de n displaystyle n chislo pochatkovih staniv a s displaystyle s rozmir alfavitu Minimizaciya NDSkAVishezgadani algoritmi ne pracyuyut dlya nedeterminovanih avtomativ NDSkA Znahodzhennya efektivnogo polinomialnogo algoritmu minimizaciyi NDSkA nemozhlive yaksho tilki ne vikonuyetsya rivnist klasiv P i NP Div takozhAlgoritmi minimizaciyi skinchennih avtomativPrimitkiHopcroft Motwani ta Ullman 2001 Section 4 4 3 Minimization of DFA s p 159 Hopcroft 1971 Hopcroft Motwani ta Ullman 2001 Section 4 4 Figure labeled Minimizing the States of an NFA p 163 LiteraturaAho Alfred V Hopcroft John E Ullman Jeffrey D 1974 4 13 Partitioning The Design and Analysis of Computer Algorithms Addison Wesley s 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 s 529 561 MR0175719 Campeanu 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 t 2214 Springer Verlag s 60 70 doi 10 1007 3 540 45526 4 6 Hopcroft John 1971 An n log n 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 s 189 196 MR 0403320 Hopcroft John E Ullman Jeffrey D 2001 Vstup do teoriyi avtomativ mov i obchislen vid 2nd Addison Wesley s 521 angl 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 s 129 153 MR 0078059 PosilannyaMinimizaciya DSkA za dopomogoyu teoremi Majgilla Nerode 21 chervnya 2015 u Wayback Machine Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi