Кіріспе
Шекті автоматтарды детерминистік ету әдісі. Есептеу теориясы мен автоматтар теориясында, қуат жиыны құрылысы немесе кіші жиын құрылысы – бұл детерминистік емес шекті автоматты (NFA) сол формальды тілді танитын детерминистік шекті автоматқа (DFA) түрлендірудің стандартты әдісі. Бұл теориялық тұрғыдан маңызды, себебі ол NFA-ның қосымша икемділігіне қарамастан, кейбір DFA-мен танылмаса, ешқандай тілді тани алмайтынын көрсетеді. Сондай-ақ, бұл практикалық тұрғыдан да маңызды, өйткені оңай құрастырылатын NFA-ны тиімді орындалатын DFA-ға түрлендіруге мүмкіндік береді. Дегенмен, егер NFA-да n күй болса, нәтижедегі DFA-да 2n күйге дейін болуы мүмкін, яғни күйлер саны экспоненциалды түрде артады, бұл кейде үлкен NFA үшін құрылысты тиімсіз етеді. Бұл құрылыс кейде Рабин-Скотт қуат жиыны құрылысы (немесе кіші жиын құрылысы) деп аталады, оны басқа автоматтардың ұқсас құрылыстарынан ажырату үшін, және алғаш рет Майкл О. Рабин мен Дана Скотт 1959 жылы жариялаған.
In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language. It is important in theory because it establishes that NFAs, despite their additional flexibility, are unable to recognize any language that cannot be recognized by some DFA. It is also important in practice for converting easier to construct NFAs into more efficiently executable DFAs. However, if the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs. The construction, sometimes called the Rabin–Scott powerset construction (or subset construction) to distinguish it from similar constructions for other types of automata, was first published by Michael O. Rabin and Dana Scott in 1959.
Интуиция
Берілген кіріс жолы бойынша DFA-ның жұмысын модельдеу үшін, кез келген сәтте бір ғана күйді қадағалау қажет: автомат кіріс жолының префиксін қарағаннан кейін жететін күй. Ал NFA-ны модельдеу үшін күйлер жиынтығын қадағалау керек: автоматтың кіріс жолының сол префиксін қарағанда, автоматтың недетерминистік таңдауларына сәйкес жетуі мүмкін барлық күйлер. Егер кіріс жолының белгілі бір префиксінен кейін S күйлер жиынтығына жетуге болады десе, келесі кіріс символы x болғанда, жете алатын күйлер жиынтығы S пен x-тің детерминистік функциясы болады. Сондықтан, NFA-ға жете алатын күйлер жиынтығы NFA модельдеуінде DFA модельдеуіндегі жеке DFA күйлерінің атқаратын қызметін атқарады, және іс жүзінде осы модельдеуде кездесетін NFA күйлер жиынтығын DFA күйлері ретінде қарастыруға болады.
Құрылыс
Күш жиыны құрылымы ең тікелей түрде кіріс символдарын пайдаланбай күй өзгертуге рұқсат бермейтін автоматқа (яғни: "ε көшулер") қолданылады. Мұндай автомат (Q, Σ, T, q0, F) 5-тік ретінде анықталуы мүмкін, онда Q – күйлер жиыны, Σ – кіріс символдар жиыны, T – көшу функциясы (күй мен кіріс символын күйлер жиынына бейімдеу), q0 – бастапқы күй, ал F – қабылдау күйлерінің жиыны. Сәйкес келетін автоматтың күйлері Q жиынының кіші жиынтықтарына сәйкес келеді. Автоматтың бастапқы күйі – бастапқы күйлердің (бір элементті) жиыны. Автоматтың көшу функциясы S күйін (Q жиынының кіші жиынтығын көрсетеді) және x кіріс символын S жиынындағы күйден x көшуі арқылы қол жеткізілетін барлық күйлер жиынына бейімдейді. Автоматтың S күйі қабылдау күйі болып табылады, егер және тек қана S жиынының кем дегенде бір мүшесі автоматтың қабылдау күйі болса. Күш жиыны құрылымының ең қарапайым нұсқасында, автоматтың барлық күйлерінің жиыны Q жиынының күш жиыны болып табылады, яғни Q жиынының барлық мүмкін кіші жиынтықтарының жиыны. Дегенмен, алынған автоматтың көптеген күйлері пайдасыз болуы мүмкін, себебі олар бастапқы күйден қол жеткізілмейді. Құрылыстың балама нұсқасы тек қол жетімді күйлерді ғана жасайды.
A state S of the DFA is an accepting state if and only if at least one member of S is an accepting state of the NFA. In the simplest version of the powerset construction, the set of all states of the DFA is the powerset of Q, the set of all possible subsets of Q. However, many states of the resulting DFA may be useless as they may be unreachable from the initial state. An alternative version of the construction creates only the states that are actually reachable.
Е-қозғалыстармен NFA
Е-қозғалыстары бар NFA үшін (немесе е-NFA), құрылысты оларды есептеу үшін өзгерту қажет: тек е-қозғалыстарды пайдаланып, берілген күйден қол жетімді барлық күйлердің жиынтығы – е-жабылу. Ван Норд осы жабылуды есептеуді қуат жиынтығы құрылымына енгізудің үш жолын атайды:
Барлық автоматтың е-жабылуын алдын ала өңдеу қадамы ретінде есептеп, е-қозғалыстары жоқ эквивалентті NFA-ны жасау, содан кейін стандартты қуат жиынтығы құрылымын қолдану. Бұл әдіс Хопкрофт пен Ульман да талқылаған, оны іске асыру оңай, бірақ көптеген е-қозғалыстары бар автоматтар үшін тиімсіз, мұндай жағдайлар табиғи тілді өңдеуде жиі кездеседі. Қуат жиынтығын есептеу кезінде алгоритм қарастырған әрбір q күйінің е-жабылуын есептеу (және нәтижені сақтау). Қуат жиынтығын есептеу кезінде алгоритм қарастырған Q' күйлерінің әрбір жиынтығының е-жабылуын есептеу және оның элементтерін Q'-қа қосу.
Бірнеше бастапқы күйлер
Егер NFA бірнеше бастапқы күйлерге рұқсат етілсе, сәйкес DFA-ның бастапқы күйі – NFA-ның барлық бастапқы күйлерінің жиынтығы болады, немесе (егер NFA-да ε көшулер болса) – бастапқы күйлерден ε көшулер арқылы қол жетімді барлық күйлердің жиынтығы.
Мысал
Төмендегі NFA төрт күйге ие; 1-күй бастапқы, ал 3- және 4-күйлер қабылдаушы. Оның әліпбиі 0 және 1 символдарынан тұрады және ε көшкіндері бар. Осы NFA-дан құрастырылған DFA-ның бастапқы күйі – 1-күйден ε көшкіндері арқылы қол жетімді барлық NFA күйлерінің жиыны; яғни, ол {1,2,3} жиыны. {1,2,3} күйінен 0 кіріс символымен өту 1-күйден 2-күйге немесе 3-күйден 4-күйге бағытталған жебелердің бірін ұстанған тиіс. Бұған қоса, 2- және 4-күйлерден шығатын ε көшкіндері жоқ. Сондықтан, T({1,2,3},0) = {2,4}, және осыған байланысты NFA-дан құрастырылған толық DFA төменде көрсетілгендей. Осы мысалда көрініп тұрғандай, DFA-ның бастапқы күйінен қол жетімді бес күй бар; NFA күйлері жиынының қуаты жиынындағы қалған 11 жиынтыққа қол жеткізу мүмкін емес.
Күрделілігі
[[File:NFA және жарылған тең DFA 01. svg|thumb|upright=1.8|5 күйі бар NFA (сол жақта), оның DFA (оң жақта) 16 күйді қажет етеді. Бұл – кем дегенде n символ бар, соңғыдан санағанда n-ші символы 1 болатын {0,1} алфавитіндегі тізбектер тілі сияқты, көптеген күйлерді қажет ететін қарапайым мысал. Оны (n + 1) күйлі NFA арқылы көрсетуге болады, бірақ ол 2^n DFA күйін қажет етеді, әрбір n символға созылатын жұрнақ үшін біреуден; н=4 үшін суретті қараңыз. Сафраның конструкциясы, n күйі бар детерминистік емес Бюхи автоматын детерминистік Мюллер автоматына немесе 2O(n log n) күйі бар детерминистік Рабин автоматына түрлендіреді, бұл үшін қуат жиыны құрылымын өз механизмінің бір бөлігі ретінде пайдаланады.