ការកំណត់
យោងទៅតាមទ្រឹស្តីបទរបស់ Kleene ការបញ្ចេញមតិធម្មតាណាមួយ។អ្នកអាចភ្ជាប់ម៉ាស៊ីនកំណត់ ដែលជាគំរូផ្លូវការនៃក្បួនដោះស្រាយសម្រាប់ការទទួលស្គាល់ lexemes ដែលតំណាងដោយកន្សោមធម្មតាដែលបានផ្តល់ឱ្យ។ នៅក្នុងលក្ខខណ្ឌទូទៅបំផុតម៉ាស៊ីនរដ្ឋ-អ្នកទទួលស្គាល់ត្រូវបានកំណត់ដោយសំណុំកំណត់នៃស្ថានភាពលក្ខណៈនៃចរន្តបញ្ចូល និងការផ្លាស់ប្តូររវាងពួកវា។ ការផ្លាស់ប្តូរស្ថានភាពកើតឡើងនៅពេលដែលនិមិត្តសញ្ញានៃចរន្តបញ្ចូលត្រូវបានទទួលពីអក្ខរក្រមដែលបានផ្តល់ឱ្យដោយអនុលោមតាមមុខងារផ្លាស់ប្តូរដែលកំណត់ស្ថានភាពបន្ទាប់ដែលអាចកើតមានដោយផ្អែកលើនិមិត្តសញ្ញាបញ្ចូល និងស្ថានភាពបច្ចុប្បន្ន។ ក្នុងចំណោមរដ្ឋដែលអាចធ្វើបាន ទីមួយគឺលេចធ្លោ(ដំបូង) និងចុងក្រោយ(អនុញ្ញាត) បញ្ជាក់ថាអ្នកទទួលស្គាល់ automaton កំណត់អាចជារៀងខ្លួននៅដើមដំបូង និងការបញ្ចប់នៃដំណើរការសញ្ញាសម្ងាត់នៃស្ទ្រីមបញ្ចូល។ ប្រសិនបើលំដាប់បញ្ចូលនៃនិមិត្តសញ្ញាអាចបង្កើតលំដាប់នៃការផ្លាស់ប្តូរដែលអាចផ្ទេរម៉ាស៊ីនរដ្ឋកំណត់ពីរដ្ឋដំបូងទៅរដ្ឋចុងក្រោយមួយ នោះវាត្រូវបានចាត់ទុកថាទទួលយក និងជាកម្មសិទ្ធិរបស់សំណុំធម្មតាដែលទទួលស្គាល់ដោយវា។
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
តារាងទី 1
| 0 | 1 | |
| សំណួរទី 1 | សំណួរទី 4 | សំណួរទី 2 |
| សំណួរទី 2 | សំណួរទី 3 | សំណួរទី 1 |
| សំណួរទី 3 | សំណួរទី 2 | សំណួរទី 4 |
| សំណួរទី 4 | សំណួរទី 1 | សំណួរទី 3 |
ជួរឈរនៃតារាងផ្លាស់ប្តូរបង្ហាញតួអក្សរនៃអក្ខរក្រមបញ្ចូល ហើយជួរដេកត្រូវគ្នាទៅនឹងស្ថានភាពបច្ចុប្បន្ននៃ DFA. ធាតុនៃបន្ទាត់នីមួយៗបង្ហាញពីស្ថានភាពនៃ DFAដែលវាត្រូវតែផ្លាស់ប្តូរពីស្ថានភាពបច្ចុប្បន្ន នៅពេលទទួលបានតួអក្សរដែលត្រូវគ្នានៃអក្ខរក្រមបញ្ចូល។ ជាពិសេស ពីជួរទីមួយនៃតារាងផ្លាស់ប្តូរនេះ វាធ្វើតាមថាការទទួលនិមិត្តសញ្ញា 0 និង 1 ក្នុងស្ថានភាពដំបូង Q1 បកប្រែ DFAទៅរដ្ឋ Q4 និង Q2 រៀងគ្នា។
នៅពេលទទួលស្គាល់លំដាប់បញ្ចូលដោយប្រើតារាងផ្លាស់ប្តូរ វាងាយស្រួលក្នុងការតាមដានការផ្លាស់ប្តូរនៅក្នុងស្ថានភាពនៃ DFAដើម្បីកំណត់ថាតើរដ្ឋអនុញ្ញាតមួយត្រូវបានសម្រេចឬអត់។ ជាពិសេស សម្រាប់វ៉ិចទ័រគោលពីរ 01001000 ជាមួយនឹងលេខគូនៃសូន្យ និងមួយ នោះ DFA ចាត់ទុកថាបង្កើតលំដាប់នៃការផ្លាស់ប្តូរខាងក្រោម ដែលការផ្លាស់ប្តូរនីមួយៗត្រូវបានដាក់ស្លាកដោយនិមិត្តសញ្ញានៃអក្ខរក្រមបញ្ចូលដែលបណ្តាលឱ្យវា៖
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
លំដាប់នៃការផ្លាស់ប្តូរនេះបញ្ចប់ដោយស្ថានភាពទទួលយក Q1 ដូច្នេះវ៉ិចទ័រគោលពីរ 01001000 ជាកម្មសិទ្ធិរបស់សំណុំធម្មតាដែលទទួលស្គាល់ដោយ DFA ដែលត្រូវបានពិចារណានិងបំពេញកន្សោមធម្មតាខាងលើ។
នៅក្នុងការសន្និដ្ឋានវាគួរតែត្រូវបានកត់សម្គាល់ថាវិធីសាស្រ្តក្រៅផ្លូវការដែលត្រូវបានចាត់ទុកថាជាការសាងសង់
ដោយចំនួនសរុបនៃតួអក្សរនៃអក្ខរក្រមនៃនិមិត្តសញ្ញា និងសញ្ញាប្រតិបត្តិការ និងវង់ក្រចកនៅក្នុងធាតុ r ។មូលដ្ឋាន។ Automata សម្រាប់កន្សោមប្រវែង 1៖ ហើយត្រូវបានបង្ហាញក្នុងរូបខាងក្រោម។
អង្ករ។ ៥.១.
ចំណាំថាសម្រាប់នីមួយៗនៃ automata ទាំងបីនេះ សំណុំនៃរដ្ឋចុងក្រោយមានរដ្ឋតែមួយ។
ជំហានបញ្ចូល។ ឥឡូវនេះឧបមាថាសម្រាប់កន្សោមធម្មតានីមួយៗនៃប្រវែង = 1 ពាក្យ w អាចត្រូវបានបែងចែកជា k subwords: w = w 1 w 2 ... w k ហើយនោះហើយជាវា។ សម្រាប់ i = 1,... ,k ពាក្យ w i បកប្រែ q 0 1 ទៅជា q f 1 ។ បន្ទាប់មកសម្រាប់ពាក្យ w ក្នុងដ្យាក្រាម M មានផ្លូវមួយ។
ដូច្នេះ, ។ ផ្ទុយទៅវិញ ប្រសិនបើពាក្យខ្លះបកប្រែ q 0 ទៅជា q f នោះវាមានឬវាត្រូវបានអនុវត្តដោយផ្លូវដែលឆ្លងកាត់ពី q 0 ដល់ q 0 1 ហើយបន្ទាប់មកឆ្លងកាត់ច្រើនដងតាមផ្លូវពី q 0 1 ដល់ q f 1 ហើយត្រលប់មកវិញ។ ពី q f 1 ដល់ q 0 1 ដោយ -transition ទីបំផុតពី q f 1 ដោយ -transition បញ្ចប់ដោយ q f ។ ដូច្នេះពាក្យបែបនេះ។
ពីទ្រឹស្តីបទ 4.2 និង 5.1 យើងទទួលបានដោយផ្ទាល់
កូរ៉ូឡារី ៥.១. សម្រាប់កន្សោមធម្មតានីមួយៗ មនុស្សម្នាក់អាចបង្កើតម៉ាស៊ីនកំណត់ស្ថានភាពកំណត់យ៉ាងមានប្រសិទ្ធភាព ដែលទទួលស្គាល់ភាសាដែលតំណាងដោយកន្សោមនោះ។
សេចក្តីថ្លែងការណ៍នេះគឺជាឧទាហរណ៍មួយនៃទ្រឹស្តីបទសំយោគ៖ ផ្អែកលើការពិពណ៌នានៃកិច្ចការ (ភាសាជាកន្សោមធម្មតា) កម្មវិធី (DFA) ដែលអនុវត្តវាត្រូវបានសាងសង់យ៉ាងមានប្រសិទ្ធភាព។ ការសន្ទនាក៏ជាការពិតផងដែរ - ទ្រឹស្តីបទនៃការវិភាគ។
ទ្រឹស្តីបទ ៥.២.
សម្រាប់ម៉ាស៊ីនកំណត់ស្ថានភាពកំណត់ (ឬមិនកំណត់) នីមួយៗ វាអាចបង្កើតកន្សោមធម្មតាដែលតំណាងឱ្យភាសាដែលទទួលស្គាល់ដោយម៉ាស៊ីននោះ។
ភស្តុតាងនៃទ្រឹស្តីបទនេះគឺពិតជាបច្ចេកទេស និងលើសពីវិសាលភាពនៃវគ្គសិក្សារបស់យើង។
ដូច្នេះ យើងអាចសន្និដ្ឋានបានថា ថ្នាក់នៃភាសា automata កំណត់ស្របគ្នាជាមួយនឹងថ្នាក់នៃភាសាធម្មតា។ ចាប់ពីពេលនេះតទៅ យើងនឹងហៅវាថាជាថ្នាក់នៃភាសាស្វ័យប្រវត្តិ។
automaton M r ដែលត្រូវបានសាងសង់ក្នុងភស្តុតាងនៃទ្រឹស្តីបទ 5.1
សម្រាប់ការសិក្សាបន្ថែមអំពីលក្ខណៈសម្បត្តិរបស់ finite automata និងជាពិសេសសម្រាប់ការដោះស្រាយបញ្ហាសំយោគ ទ្រឹស្តីបទខាងក្រោមមានសារៈសំខាន់។
ដើម្បីបញ្ជាក់ទ្រឹស្តីបទ វាជាការចាំបាច់ដំបូងដើម្បីពិពណ៌នាអំពីក្បួនដោះស្រាយសម្រាប់ការសាងសង់ automaton finite deterministic ពីដើមមួយ; ទីពីរ ដើម្បីបង្ហាញអំពីភាពត្រឹមត្រូវនៃក្បួនដោះស្រាយនេះ ដោយបញ្ជាក់យ៉ាងម៉ឺងម៉ាត់ថា វាពិតជាផលិតម៉ាស៊ីនរដ្ឋដែលកំណត់ និងសមមូលទៅនឹងឧបករណ៍ដើម។ នៅទីនេះយើងបង្ហាញតែក្បួនដោះស្រាយសម្រាប់បង្កើត automaton កំណត់ប៉ុណ្ណោះ។
ការផ្លាស់ប្តូរនៃ automaton កំណត់តាមអំពើចិត្តទៅជា deterministic សមមូលត្រូវបានអនុវត្តជាពីរដំណាក់កាល៖ ដំបូង ធ្នូដែលមានស្លាក \lambda ត្រូវបានដកចេញ បន្ទាប់មកការកំណត់ដោយខ្លួនឯងត្រូវបានអនុវត្ត។
1. ការដក λ-transitions (arcs labeled \lambda)។
ដើម្បីទៅពី automaton finite ដើម M=(V,Q,q_0,F,\delta) ទៅកាន់ automaton finite equivalent M"=(V,Q",q_0,F",\delta") ដោយគ្មានការផ្លាស់ប្តូរ λ-transitions វា វាគ្រប់គ្រាន់ហើយនៅក្នុងដើមធ្វើឱ្យការបំប្លែងដូចខាងក្រោមនៅក្នុងក្រាហ្វ M ។
ក. រដ្ឋទាំងអស់ លើកលែងតែរដ្ឋដំបូង ដែលមានតែ arcs ដែលមានស្លាក \lambda បញ្ចូលប៉ុណ្ណោះត្រូវបានលុប។ ដោយហេតុនេះកំណត់សំណុំ Q" នៃ automaton M"។ វាច្បាស់ណាស់ថា Q"\subseteq Q. ក្នុងពេលជាមួយគ្នានេះ យើងសន្មត់ថាស្ថានភាពដំបូងនៅដដែល។
ខ.
សំណុំនៃធ្នូនៃ automaton កំណត់ M" និងស្លាករបស់ពួកគេ (ដោយហេតុនេះមុខងារផ្លាស់ប្តូរ M") ត្រូវបានកំណត់ដូចខាងក្រោម: សម្រាប់រដ្ឋពីរណាមួយ p,r\in Q",~ p\to_(a)r កើតឡើងប្រសិនបើ និងតែប៉ុណ្ណោះ ប្រសិនបើ \in V ហើយនៅក្នុងក្រាហ្វ M វត្ថុមួយក្នុងចំណោមវត្ថុពីរមាន៖ ទាំងមានធ្នូពី p ដល់ r ដែលស្លាកមាននិមិត្តសញ្ញា a ឬមានស្ថានភាព q ដូច p\Rightarrow_(\lambda)^( +)q និង q\ to_(a)r ក្នុងករណីនេះ vertex q ជាទូទៅអាចមិនមែនជារបស់ set Q" ពោលគឺឧ។ វាអាចនឹងបាត់ទៅវិញនៅពេលឆ្លងទៅ automaton M" (រូបភាព 7.11) ប្រសិនបើ q\in Q" នោះតាមធម្មជាតិ ធ្នូ (q,r) នឹងត្រូវបានរក្សាទុកជា M" ហើយនិមិត្តសញ្ញា a នឹងក្លាយជានិមិត្តសញ្ញាមួយក្នុងចំណោមនិមិត្តសញ្ញា ជាកម្មសិទ្ធិរបស់ស្លាកនៃធ្នូនេះ (រូបភាព 7.12) ។
វ. សំណុំនៃរដ្ឋចុងក្រោយ F" នៃ finite automaton M" មានរដ្ឋទាំងអស់ q\in Q" ពោលគឺរដ្ឋនៃ finite automaton M ដែលមិនត្រូវបានលុបដោយយោងតាមកថាខណ្ឌ a ដែល q\Rightarrow_(\lambda)^(\ ast) រក្សា q_f សម្រាប់ q_f\in F មួយចំនួន (ឧទាហរណ៍ ទាំងរដ្ឋ q ខ្លួនវាគឺជាស្ថានភាពចុងក្រោយនៃ automaton កំណត់ M ឬផ្លូវនៃប្រវែងមិនសូន្យដែលដឹកនាំពីវាតាមអ័ក្សដែលមានស្លាក \lambda ទៅរដ្ឋចុងក្រោយមួយនៃ finite automaton M) (រូបភាព 7.13) ។
2. ការកំណត់ខ្លួនឯង។
អនុញ្ញាតឱ្យ M=(Q,V,q_0,F,\delta) ជា automaton កំណត់ដោយគ្មានការផ្លាស់ប្តូរ λ ។ អនុញ្ញាតឱ្យយើងបង្កើត automaton កំណត់កំណត់ M_1 ស្មើនឹង M.
automaton កំណត់នេះត្រូវបានកំណត់តាមវិធីដែលសំណុំរដ្ឋរបស់វាគឺជាសំណុំនៃសំណុំរងទាំងអស់នៃ state set of the finite automaton M. នេះមានន័យថារដ្ឋនីមួយៗនៃ automaton កំណត់ M_1 ត្រូវបានកំណត់ជាសំណុំរងជាក់លាក់នៃរដ្ឋកំណត់នៃ automaton M. ក្នុងករណីនេះ ស្ថានភាពដំបូងនៃម៉ាស៊ីនរដ្ឋកំណត់ថ្មី (ឧ. M_1) គឺជាសំណុំរង singleton ដែលមានស្ថានភាពដំបូងនៃម៉ាស៊ីនកំណត់រដ្ឋចាស់ (ឧទាហរណ៍ M) ហើយស្ថានភាពចុងក្រោយនៃម៉ាស៊ីនរដ្ឋកំណត់ថ្មីគឺជាសំណុំរងបែបនេះទាំងអស់។ Q ដែលមានយ៉ាងហោចណាស់មួយចុងក្រោយនៃ vertex នៃ automaton កំណត់ដើម M.
ចាប់ពីពេលនេះតទៅ ដោយអនុញ្ញាតឱ្យមានសេរីភាពក្នុងការបញ្ចេញមតិ ពេលខ្លះយើងនឹងហៅស្ថានភាពនៃ automaton កំណត់ M_1 states-sets ។ ទោះជាយ៉ាងណាក៏ដោយ វាមានសារៈសំខាន់ណាស់ក្នុងការយល់យ៉ាងច្បាស់ថា សំណុំរដ្ឋនីមួយៗគឺជាស្ថានភាពដាច់ដោយឡែកនៃ automaton កំណត់ថ្មី ប៉ុន្តែមិនមែនជាសំណុំនៃរដ្ឋរបស់វានោះទេ។ ក្នុងពេលជាមួយគ្នានេះសម្រាប់ automaton ដើម ("ចាស់") finite automaton M នេះគឺជាសំណុំនៃរដ្ឋរបស់វា។ និយាយជាន័យធៀប សំណុំរងនីមួយៗនៃរដ្ឋនៃ automaton កំណត់ចាស់ត្រូវបាន "ដួលរលំ" ទៅជាស្ថានភាពមួយនៃ automaton កំណត់ថ្មី*។
* ជាផ្លូវការ យើងគួរតែកំណត់សំណុំ Q_1 ជាសំណុំដែលមាននៅក្នុងការឆ្លើយឆ្លងមួយទល់នឹងមួយជាមួយសំណុំ 2^Q ប៉ុន្តែវានៅតែងាយស្រួលជាងសម្រាប់យើងក្នុងការសន្មត់ថា Q_1 ស្របពេលជាមួយ 2^Q - បន្ទាប់ពីទាំងអស់ សំណុំនៃស្ថានភាពនៃ automaton កំណត់អាចជាសំណុំកំណត់មិនទទេណាមួយ។
មុខងារផ្លាស់ប្តូរនៃ finite automaton ថ្មីត្រូវបានកំណត់តាមរបៀបដែលពីការកំណត់រដ្ឋ S ដោយនិមិត្តសញ្ញាបញ្ចូល A automaton finite M_1 ទៅ state-set ដែលជាការរួបរួមនៃសំណុំរដ្ឋទាំងអស់នៃការកំណត់ចាស់។ automaton ដែល automaton កំណត់ចាស់នេះឆ្លងកាត់ដោយនិមិត្តសញ្ញា a ពីរដ្ឋនីមួយៗកំណត់ S ។ ដូច្នេះ automaton កំណត់ M_1 គឺកំណត់ដោយការសាងសង់។
ការពិពណ៌នាពាក្យសំដីខាងលើអាចត្រូវបានបកប្រែទៅជារូបមន្តដូចខាងក្រោម: យើងបង្កើតម៉ាស៊ីនកំណត់ M_1 ដូច្នេះ
M_1=(Q_1,V,\(q_0\),F_1,\delta_1) ដែលជាកន្លែងដែល
\begin(cases)Q_1=2^Q,\quad F_1=\(T\colon\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\forall a\in V)\Bigl(\delta_1(S,a)=\bigcup\limits_(q\in S)\delta(q,a)\Bigr)។ \end(ករណី)
ចូរយើងកត់សម្គាល់ថាក្នុងចំណោមរដ្ឋនៃ automaton កំណត់ថ្មីមានស្ថានភាព \varnothing ហើយយោងទៅតាម (7.8) \delta_1(\varnothing,a)=\varnothing សម្រាប់និមិត្តសញ្ញាបញ្ចូលណាមួយ a . នេះមានន័យថា នៅពេលដែលស្ថិតក្នុងស្ថានភាពបែបនេះ ម៉ាស៊ីនរដ្ឋកំណត់ M_1 នឹងមិនទុកវាចោលទេ។ ជាទូទៅ ស្ថានភាព q នៃ automaton កំណត់ណាមួយ ដែលសម្រាប់និមិត្តសញ្ញាបញ្ចូលណាមួយ យើងមាន \delta(q,a)=q ត្រូវបានគេហៅថាស្ថានភាពស្រូបយកនៃ automaton កំណត់។ ដូច្នេះ ស្ថានភាព \varnothing នៃម៉ាស៊ីនកំណត់រដ្ឋកំណត់ M_1 កំពុងស្រូបយក។ វាក៏មានប្រយោជន៍ផងដែរក្នុងការកត់សម្គាល់ថា \delta_1(S,a)=\varnothing ប្រសិនបើសម្រាប់ q\in S នីមួយៗ (ស្ថានភាពនៃម៉ាស៊ីនរដ្ឋកំណត់ចាស់ពីសំណុំរដ្ឋ S) \delta(q,a)= \varnothing, ឧ. នៅក្នុងក្រាហ្វ M មិនមានធ្នូចេញពីរដ្ឋនីមួយៗ q ដែលសម្គាល់ដោយនិមិត្តសញ្ញា a ។
វាអាចត្រូវបានបង្ហាញថា automaton កំណត់ដែលទទួលបានដោយប្រើក្បួនដោះស្រាយនេះគឺស្មើនឹងមួយដើម។
ឧទាហរណ៍ 7.9 ។
អនុញ្ញាតឱ្យយើងកំណត់ automaton កំណត់ដែលបានបង្ហាញនៅក្នុងរូបភព។ ៧.១៤.
automaton កំណត់សមមូលដោយគ្មានការផ្លាស់ប្តូរ λ ត្រូវបានបង្ហាញក្នុងរូប។ ៧.១៥. ចំណាំថា vertex q_2 បាត់ ព្រោះមានតែ "ទទេ" arcs បញ្ចូលវា។
ដើម្បីកំណត់លទ្ធផល automaton វាមិនចាំបាច់ទាល់តែសោះក្នុងការសរសេរនូវរដ្ឋ 2^3=8 ទាំងអស់របស់វា ដែលភាគច្រើនប្រហែលជាមិនអាចទៅដល់បានពីស្ថានភាពដំបូង \(q_0\) ។ ដើម្បីទទួលបានរដ្ឋដែលអាចទៅដល់បានពី \(q_0\) ហើយមានតែពួកវាទេ យើងនឹងប្រើវិធីដែលហៅថាទាញ។
នៅក្នុង automaton កំណត់ដំបូង (ដោយគ្មានធ្នូទទេ) យើងកំណត់សំណុំនៃរដ្ឋទាំងអស់ដែលអាចទៅដល់បានពីដំបូង ពោលគឺឧ។ សម្រាប់និមិត្តសញ្ញាបញ្ចូលនីមួយៗ a យើងរកឃើញសំណុំ \delta(q_0,a) ។ សំណុំបែបនេះនីមួយៗនៅក្នុង automaton ថ្មីគឺជារដ្ឋដែលអាចចូលដំណើរការបានដោយផ្ទាល់ពីដំបូង។
សម្រាប់ការកំណត់រដ្ឋដែលបានកំណត់នីមួយៗ S និងនិមិត្តសញ្ញាបញ្ចូលនីមួយៗ a យើងរកឃើញសំណុំ \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom( ក)^(.)))។ រដ្ឋទាំងអស់ដែលទទួលបាននៅជំហាននេះនឹងក្លាយជារដ្ឋនៃស្វ័យប្រវត្តិកម្មថ្មី (កំណត់) ដែលអាចទៅដល់បានពីចំនុចកំពូលដំបូងតាមបណ្តោយផ្លូវនៃប្រវែង 2។ យើងធ្វើបែបបទដែលបានពិពណ៌នាម្តងទៀតរហូតដល់មិនមានរដ្ឋកំណត់ថ្មី (រួមទាំងទទេ!) លេចឡើង។ វាអាចត្រូវបានបង្ហាញថាវាបង្កើតស្ថានភាពទាំងអស់នៃ finite automaton M_1 ដែលអាចទៅដល់បានពីស្ថានភាពដំបូង \(q_0\) ។
សម្រាប់ម៉ាស៊ីនរដ្ឋកំណត់នៅក្នុងរូបភព។ ៧.១៥ យើងមាន៖
\begin(aligned)& \delta_1(\(q_0\),a)=\(q_1\);\qquad \delta_1(\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1(\(q_1,q_3\) ,a)= \delta(q_1,a)\cup \delta(q_3,a)= \(q_1\)\cup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)=\delta(q_1,b)\cup \delta(q_3,b)=\(q_1\)\cup\(q_1\)=\(q_1\)។ \end(តម្រឹម)
ដោយសារមិនមានសំណុំរដ្ឋថ្មីបានបង្ហាញខ្លួន នីតិវិធី "ទាញ" បញ្ចប់នៅទីនេះ ហើយយើងទទួលបានក្រាហ្វដែលបង្ហាញក្នុងរូបភព។ ៧.១៦.
ការបន្ថែមភាសាធម្មតា។លទ្ធផលទ្រឹស្តីដ៏សំខាន់មួយនៃទ្រឹស្តីបទកំណត់គឺទ្រឹស្តីបទខាងក្រោម។
ទ្រឹស្តីបទ 7.8 ។
ការបំពេញបន្ថែមនៃភាសាធម្មតាគឺជាភាសាធម្មតា។
យោងតាមទ្រឹស្តីបទ 7.7 សម្រាប់ភាសាធម្មតា L ស្វ័យប្រវត្តិកម្មកំណត់កំណត់ M អាចត្រូវបានសាងសង់ដែលទទួលស្គាល់ L ។ ដោយសារនៅក្នុង automaton កំណត់ពីចំនុចកំពូលនីមួយៗសម្រាប់និមិត្តសញ្ញាបញ្ចូលនីមួយៗ ការផ្លាស់ប្តូរទៅចំនុចកំពូលមួយត្រូវបានកំណត់ នោះខ្សែសង្វាក់ x នៅក្នុងអក្ខរក្រម V វាមានផ្លូវតែមួយគត់សម្រាប់វានៅក្នុង M ដោយចាប់ផ្តើមពីស្ថានភាពដំបូងដែល ខ្សែសង្វាក់ x ត្រូវបានអាន។ វាច្បាស់ណាស់ថាខ្សែសង្វាក់ x ត្រូវបានអនុញ្ញាតដោយ automaton M នោះគឺ x\in L(M) ប្រសិនបើ ហើយប្រសិនបើស្ថានភាពចុងក្រោយនៃផ្លូវដែលបានបញ្ជាក់គឺចុងក្រោយ។ វាធ្វើតាមខ្សែសង្វាក់ x\notin L(M) ប្រសិនបើ ហើយប្រសិនបើស្ថានភាពចុងក្រោយនៃផ្លូវដែលបានបញ្ជាក់គឺមិនចុងក្រោយ។ ប៉ុន្តែយើងគ្រាន់តែត្រូវការ automaton កំណត់ M" ដែលទទួលស្គាល់ខ្សែសង្វាក់ x ប្រសិនបើ និងលុះត្រាតែវាមិនត្រូវបានអនុញ្ញាតដោយ automaton កំណត់ដើម M. ជាលទ្ធផល ការបង្វែរស្ថានភាពចុងក្រោយនីមួយៗរបស់ M ទៅជារដ្ឋមិនចុងក្រោយ ហើយផ្ទុយទៅវិញ យើងទទួលបាន automaton កំណត់ដែលទទួលស្គាល់ការបន្ថែមនៃភាសា L ។
ទ្រឹស្តីបទដែលបង្ហាញឱ្យឃើញអនុញ្ញាតឱ្យយើងបង្កើត automaton កំណត់ដែលមិនទទួលស្គាល់សំណុំជាក់លាក់នៃខ្សែសង្វាក់ ដោយប្រើវិធីសាស្រ្តខាងក្រោម: ដំបូងយើងបង្កើត automaton ដែលទទួលស្គាល់សំណុំនៃច្រវាក់ដែលបានផ្តល់ឱ្យ បន្ទាប់មកយើងកំណត់វា ហើយចូលទៅកាន់ automaton សម្រាប់ការបន្ថែមដូចជា បានបង្ហាញនៅក្នុងភស្តុតាងនៃទ្រឹស្តីបទ 7.8 ។
ឧទាហរណ៍ 7.10 ។
ក. តោះបង្កើត automaton កំណត់ដែលទទួលយកខ្សែសង្វាក់ទាំងអស់ក្នុងអក្ខរក្រម \(0;1\) លើកលែងតែខ្សែសង្វាក់ 101។
ដំបូង យើងបង្កើត automaton កំណត់ដែលអនុញ្ញាតឱ្យមានខ្សែសង្វាក់តែមួយ 101. automaton នេះត្រូវបានបង្ហាញនៅក្នុងរូបភព។ ៧.១៧.
automaton នេះគឺជាការកំណត់មិនត្រឹមត្រូវ ប៉ុន្តែមិនបានកំណត់ដោយសារតែវាមិនត្រូវបានកំណត់យ៉ាងពេញលេញ។ អនុញ្ញាតឱ្យយើងកំណត់វា និងទទួលបាន automaton កំណត់សមមូលសមមូលដែលបង្ហាញនៅក្នុងរូបភព។ ៧.១៨.
ហើយចុងក្រោយ ការផ្លាស់ទៅការបន្ថែម (និងប្តូរឈ្មោះរដ្ឋ) យើងទទួលបាន automaton ដែលបង្ហាញក្នុងរូប។ ៧.១៩.
ចំណាំថានៅក្នុងលទ្ធផល automaton បញ្ឈរទាំងអស់ លើកលែងតែ vertex s_3 គឺជាចុងក្រោយ។
ចំណាំផងដែរថាម៉ាស៊ីនរដ្ឋកំណត់នៅក្នុងរូបភព។ 7.19 អនុញ្ញាតឱ្យខ្សែអក្សរទាំងអស់ដែលមានការកើតឡើងនៃខ្សែអក្សរ 101 ប៉ុន្តែមិនត្រូវគ្នានឹងខ្សែអក្សរនោះ។ ឧទាហរណ៍នៅទីនេះ គឺជាផ្លូវដែលផ្ទុកខ្សែសង្វាក់ 1011៖ s_0,s_1,s_2,s_3,t ។
ខ.
ចូរយើងបង្កើត automaton កំណត់ដែលទទួលយកខ្សែសង្វាក់ទាំងអស់នៅក្នុងអក្ខរក្រម \(0;1\) លើកលែងតែអក្សរដែលមានការកើតឡើងនៃខ្សែអក្សរ 101។ ពិចារណាភាសា L ដែលខ្សែសង្វាក់នីមួយៗដែលមានការកើតឡើងនៃខ្សែអក្សរ 101។ វាអាចជា កំណត់ដូចខាងក្រោមៈ
L=(0+1)^(\ast)101(0+1)^(\ast)។
យើងត្រូវបង្កើត automaton ដើម្បីបំពេញភាសា L.
ក្នុងករណីនេះ ដោយប្រើកន្សោមធម្មតាដោយផ្ទាល់ វាងាយស្រួលក្នុងការសាងសង់ automaton កំណត់ដែលទទួលយកភាសា L (រូបភាព 7.20) ។
បន្ទាប់មកយើងនឹងអនុវត្តការកំណត់ដោយប្រើវិធីសាស្ត្រ "ទាញ" ។ លទ្ធផលនៃការប្តេជ្ញាចិត្តត្រូវបានបង្ហាញនៅក្នុងរូបភព។ ៧.២១.
ដើម្បីដោះស្រាយបញ្ហាទាំងស្រុង អ្វីទាំងអស់ដែលនៅសល់គឺនៅក្នុងរូបភព។ 7.21 ផ្លាស់ប្តូរតួនាទីនៃចំនុចកំពូលចុងក្រោយ និងមិនមែនចុងក្រោយ (រូបភាព 7.22)។
វ. ចូរពិភាក្សាអំពីគំនិតនៃការបង្កើត automaton កំណត់ដែលអនុញ្ញាតឱ្យមានខ្សែសង្វាក់ទាំងនោះ និងតែនៅក្នុងអក្ខរក្រម \(0;1\) ដែលមិនចាប់ផ្តើមដោយខ្សែសង្វាក់ 01 និងមិនបញ្ចប់ដោយខ្សែសង្វាក់ 11 (ឧ. ទម្រង់ 01x និងខ្សែសង្វាក់នៃប្រភេទ y11 មិនត្រូវបានអនុញ្ញាតទេ ទោះបីជាមានខ្សែសង្វាក់ x,y\in\(0;1\) ក៏ដោយ។
ក្នុងករណីនេះ ការបំពេញបន្ថែមនៃភាសាដែលវាចាំបាច់ក្នុងការសាងសង់ automaton កំណត់គឺជាសំណុំនៃខ្សែសង្វាក់ទាំងអស់នៃសូន្យ និងមួយដែលចាប់ផ្តើមដោយខ្សែសង្វាក់ 01 ឬបញ្ចប់ដោយខ្សែសង្វាក់ 11 ។ automaton ដែលអនុញ្ញាតឱ្យសំណុំនៃ ខ្សែសង្វាក់ត្រូវបានសាងសង់ជា automaton សម្រាប់ផ្សំ 01(0+1)^(\ast)+(0+1)^(\ast)11 តាមរបៀបដូចគ្នា ដូចដែលបានពិពណ៌នានៅក្នុងភស្តុតាងនៃទ្រឹស្តីបទ Kleene (សូមមើលទ្រឹស្តីបទ 7.6)។
ពីទ្រព្យសម្បត្តិដែលថ្នាក់នៃភាសាធម្មតាត្រូវបានបិទដោយគោរពទៅនឹងការបំពេញបន្ថែម (សូមមើលទ្រឹស្តីបទ 7.8) វាភ្លាមៗបន្ទាប់ពីថ្នាក់នេះត្រូវបានបិទដោយគោរពតាមចំនុចប្រសព្វ សំណុំទ្រឹស្តី និងភាពខុសគ្នាស៊ីមេទ្រី។
កូរ៉ូឡារី ៧.៣.
សម្រាប់ភាសាធម្មតាពីរ L_1 និង L_2 សេចក្តីថ្លែងការណ៍ខាងក្រោមគឺពិត៖
1) ចំនុចប្រសព្វនៃ L_1\cap L_2 គឺទៀងទាត់។
2) ភាពខុសគ្នា L_1\setminus L_2 គឺទៀងទាត់។
3) ភាពខុសគ្នាស៊ីមេទ្រី L_1\vartriangle L_2 គឺទៀងទាត់។
ទីមួយ លទ្ធផលដែលទទួលបានអនុញ្ញាតឱ្យយើងអះអាងថា ថ្នាក់នៃភាសាធម្មតាទាក់ទងនឹងប្រតិបត្តិការនៃសហជីព ចំនុចប្រសព្វ និងការបន្ថែមគឺជាពិជគណិតប៊ូលីន ដែលក្នុងនោះឯកតាជាភាសាសកល ហើយសូន្យគឺជាភាសាទទេ។ ទីពីរ លក្ខណៈសម្បត្តិពិជគណិតទាំងនេះនៃក្រុមគ្រួសារនៃភាសាធម្មតាអនុញ្ញាតឱ្យយើងដោះស្រាយបញ្ហាសំខាន់នៃការទទួលស្គាល់សមមូលនៃ finite automata បំពានពីរ។
យោងតាមនិយមន័យ 7.10 ម៉ាស៊ីនរដ្ឋកំណត់គឺស្មើនឹងប្រសិនបើភាសាដែលពួកគេទទួលយកគឺដូចគ្នា។ ដូច្នេះ ដើម្បីផ្ទៀងផ្ទាត់សមមូលនៃ automata M_1 និង M_2 វាគ្រប់គ្រាន់ដើម្បីបង្ហាញថាភាពខុសគ្នាស៊ីមេទ្រីនៃភាសា L(M_1) និង L(M_2) គឺទទេ។ ដើម្បីធ្វើដូចនេះវាគ្រប់គ្រាន់ហើយក្នុងការសាងសង់ automaton ដែលទទួលស្គាល់ភាពខុសគ្នានេះហើយត្រូវប្រាកដថាភាសាដែលវាទទួលស្គាល់គឺទទេ។ ជាទូទៅបញ្ហានៃការទទួលស្គាល់ថាភាសារបស់ម៉ាស៊ីនរដ្ឋគឺទទេត្រូវបានគេហៅថាបញ្ហាទទេរបស់ម៉ាស៊ីនរដ្ឋ។ ដើម្បីដោះស្រាយបញ្ហានេះ វាគ្រប់គ្រាន់ហើយក្នុងការស្វែងរកសំណុំនៃរដ្ឋចុងក្រោយនៃ automaton ដែលអាចទៅដល់បានពីស្ថានភាពដំបូង។ ដោយសារម៉ាស៊ីនរដ្ឋកំណត់គឺជាក្រាហ្វដឹកនាំ បញ្ហានេះអាចត្រូវបានដោះស្រាយ ជាឧទាហរណ៍ ដោយប្រើការស្វែងរកដំបូង។ ភាសាដែលអនុញ្ញាតដោយម៉ាស៊ីនរដ្ឋកំណត់គឺទទេ ប្រសិនបើសំណុំនៃរដ្ឋចុងក្រោយដែលអាចទៅដល់បានពីស្ថានភាពដំបូងគឺទទេ។ នៅក្នុងការអនុវត្ត វាជាការប្រសើរក្នុងការទទួលស្គាល់សមមូលនៃ automata កំណត់ដោយប្រើក្បួនដោះស្រាយបង្រួមអប្បបរមា ប៉ុន្តែឥឡូវនេះវាមានសារៈសំខាន់សម្រាប់យើងក្នុងការបញ្ជាក់ថាលទ្ធភាពជាមូលដ្ឋាននៃការដោះស្រាយបញ្ហាសមមូលបានមកពីទ្រឹស្តីបទ 7.7 និងផលវិបាកពិជគណិតរបស់វា។
DKA គឺជាករណីពិសេសរបស់ NKA ។ នៅក្នុងវា៖
មិនមានរដ្ឋជាមួយ ε-transitions;
សម្រាប់រដ្ឋនីមួយៗ S និងនិមិត្តសញ្ញាបញ្ចូល a ភាគច្រើនមានធ្នូមួយចេញមកពី S ហើយដាក់ស្លាក a ។
DFA មានការផ្លាស់ប្តូរអតិបរមាមួយសម្រាប់និមិត្តសញ្ញាបញ្ចូលណាមួយពីរដ្ឋនីមួយៗ។ ប្រសិនបើតារាងមួយត្រូវបានប្រើដើម្បីតំណាងឱ្យមុខងារផ្លាស់ប្តូរ DFA នោះកំណត់ត្រានីមួយៗនឹងមានរដ្ឋតែមួយប៉ុណ្ណោះ។ ដូច្នេះ វាជាការងាយស្រួលក្នុងការពិនិត្យមើលថាតើ DFA ដែលបានផ្ដល់ឱ្យទទួលស្គាល់បន្ទាត់ជាក់លាក់មួយ ដោយសារមានផ្លូវតែមួយគត់ពីស្ថានភាពចាប់ផ្តើម ដែលត្រូវបានសម្គាល់ដោយបន្ទាត់នេះ។
រូបភាពទី 3 បង្ហាញក្រាហ្វការផ្លាស់ប្តូរនៃ DFA ដែលទទួលយកភាសាដូចគ្នា (a|b) * a(a|b)(a|b) ជា NFA នៅក្នុងរូបភាពទី 1 ។
រូបភាពទី 3. DFA អនុញ្ញាតឱ្យខ្សែអក្សរ (a|b) * a(a|b)(a|b) ។
ស្វ័យប្រវត្តិកម្មកំណត់កំណត់ M ដែលទទួលយកភាសាដែលបានផ្តល់ឱ្យ៖
M = ((1, 2, 3, 4, 5, 6, 7, 8), (a, b), D, 1, (3, 5, 6, 8))
មុខងារផ្លាស់ប្តូរ D ត្រូវបានកំណត់ដូចខាងក្រោម:
1. សម្រាប់ε NKA មានទម្រង់ដូចខាងក្រោម (0 – រដ្ឋដំបូង 1 – ស្ថានភាពចុងក្រោយ):
2. សម្រាប់ការរួមបញ្ចូលនៅក្នុងភាសា NKA ដែលបានផ្តល់ឱ្យ៖
3. អនុញ្ញាតឱ្យ N(s) និង N(t) ជា NFAs សម្រាប់កន្សោមធម្មតា s និង t ។
សម្រាប់កន្សោមធម្មតា s|t សមាសធាតុ NFA មានទម្រង់ដូចខាងក្រោម៖
ខ. សម្រាប់កន្សោមធម្មតា st NKA:
ជាមួយ។ សម្រាប់កន្សោម s* NFA មានទម្រង់៖
ឃ. សម្រាប់កន្សោមក្នុងតង្កៀប (s) NFA N(s) ត្រូវបានប្រើដូចនៅក្នុងចំណុច a.
រដ្ឋថ្មីនីមួយៗទទួលបានឈ្មោះបុគ្គល។ ការសាងសង់ NFA N(r) មានលក្ខណៈសម្បត្តិដូចខាងក្រោមៈ
N(r) មានរដ្ឋមួយចំនួនដែលមិនលើសពីចំនួននិមិត្តសញ្ញាច្រើនជាង 2 ដង។
N(r) មានស្ថានភាពដំបូង និងចុងក្រោយមួយ។ រដ្ឋចុងក្រោយមិនមានការផ្លាស់ប្តូរបន្ត។
រដ្ឋនីមួយៗ N(r) មានការផ្លាស់ប្តូរ 1 សម្រាប់និមិត្តសញ្ញាពីអក្ខរក្រម () ឬមិនលើសពី 2 ε-transitions ចេញ។
បំប្លែង nka ទៅ ឌីកា។NFA នៅក្នុងរូបភាពទី 1 មានការផ្លាស់ប្តូរ 2 ពីរដ្ឋ 0 សម្រាប់និមិត្តសញ្ញា a: រដ្ឋ 0 និង 1 ។ ការផ្លាស់ប្តូរបែបនេះគឺមិនច្បាស់លាស់ ដូចជាការផ្លាស់ប្តូរនៅក្នុងε។ ការធ្វើគំរូផ្កាយរណបបែបនេះដោយប្រើកម្មវិធីកុំព្យូទ័រគឺពិបាកជាង។ និយមន័យនៃលទ្ធភាព ចែងថាត្រូវតែមានផ្លូវមួយចំនួនពីរដ្ឋដំបូងទៅរដ្ឋចុងក្រោយ ប៉ុន្តែនៅពេលដែលមានផ្លូវច្រើនសម្រាប់ខ្សែអក្សរបញ្ចូលដូចគ្នា ពួកគេទាំងអស់ត្រូវពិចារណាដើម្បីស្វែងរកផ្លូវទៅកាន់រដ្ឋចុងក្រោយ ឬស្វែងរកថានៅទីនោះ។ មិនមានផ្លូវបែបនេះទេ។
នៅក្នុងតារាងការផ្លាស់ប្តូរ NKA ធាតុនីមួយៗត្រូវគ្នាទៅនឹងរដ្ឋជាច្រើន ប៉ុន្តែនៅក្នុងតារាងផ្លាស់ប្តូរ DKA មានតែមួយប៉ុណ្ណោះ។ ខ្លឹមសារនៃការផ្លាស់ប្តូរគឺថារដ្ឋ DFA នីមួយៗត្រូវគ្នាទៅនឹងសំណុំនៃរដ្ឋ NFA ។ DFA ប្រើរដ្ឋរបស់ខ្លួនដើម្បីតាមដានស្ថានភាពដែលអាចធ្វើបានទាំងអស់ដែល NFA អាចស្ថិតនៅក្នុងបន្ទាប់ពីអាននិមិត្តសញ្ញាបញ្ចូលបន្ទាប់។ នោះគឺបន្ទាប់ពីអានស្ទ្រីមបញ្ចូល DFA ស្ថិតនៅក្នុងស្ថានភាពដែលតំណាងឱ្យសំណុំជាក់លាក់នៃរដ្ឋ NFA ដែលអាចទៅដល់បានពីដំបូងនៅតាមបណ្តោយផ្លូវដែលត្រូវគ្នាទៅនឹងខ្សែអក្សរបញ្ចូល។ ចំនួននៃរដ្ឋ DFA បែបនេះអាចលើសពីចំនួនរដ្ឋ NFA យ៉ាងខ្លាំង (ការពឹងផ្អែកនិទស្សន្ត) ប៉ុន្តែនៅក្នុងការអនុវត្តនេះគឺកម្រខ្លាំងណាស់ ហើយជួនកាលមានរដ្ឋតិចជាងនៅក្នុង DFA ជាងនៅក្នុង NFA ។
ចូរយើងពិចារណាការផ្លាស់ប្តូរបែបនេះដោយប្រើឧទាហរណ៍ជាក់លាក់មួយ។ រូបភាពទី 4 បង្ហាញ NFA មួយផ្សេងទៀតដែលអនុញ្ញាតឱ្យភាសា (a|b) * a(a|b)(a|b) (ដូចក្នុងរូបភាពទី 1 និងទី 3)។
រូបភាពទី 4. NFA អនុញ្ញាតភាសា (a|b) * a(a|b)(a|b)
ការផ្លាស់ប្តូរពីរដ្ឋទី 13 ទៅរដ្ឋទី 14 ដែលបង្ហាញក្នុងរូបភាពអាចត្រូវបានតំណាងស្រដៀងគ្នាទៅនឹងការផ្លាស់ប្តូរពីរដ្ឋទី 8 ទៅរដ្ឋទី 13 ។
ចូរយើងបង្កើត DFA សម្រាប់ភាសានេះ។ ស្ថានភាពចាប់ផ្តើមនៃ DFA ដែលសមមូលគឺរដ្ឋ A = (0, 1, 2, 4, 7) នោះគឺរដ្ឋទាំងនោះដែលអាចទៅដល់ពី 0 ដោយε។
អក្ខរក្រមនិមិត្តសញ្ញាបញ្ចូលគឺ (a, b) ។ ពីស្ថានភាពដំបូង A មនុស្សម្នាក់អាចគណនារដ្ឋដែលអាចទៅដល់បានដោយ a ។ ចូរហៅរដ្ឋនេះថា B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14)។
ក្នុងចំណោមរដ្ឋនៅក្នុង A មានតែរដ្ឋ 4 ប៉ុណ្ណោះដែលមានការផ្លាស់ប្តូរតាមបណ្តោយ b ទៅ រដ្ឋ 5 ដូច្នេះ DFA មានការផ្លាស់ប្តូរតាមបណ្តោយ b ពី A ទៅរដ្ឋ C = (1, 2, 4, 5, 6, 7) ។
ប្រសិនបើយើងបន្តដំណើរការនេះជាមួយនឹងរដ្ឋ B និង C នោះសំណុំនៃរដ្ឋទាំងអស់នៃ NFA នឹងត្រូវបានសម្គាល់។ ដូច្នេះយើងនឹងមានសំណុំរដ្ឋ៖
A = (0, 1, 2, 4, 7)
B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14)
C = (1, 2, 4, 5, 6, 7)
ឃ = (១០, ១២, ១៣, ១៤)
រដ្ឋ A គឺជារដ្ឋដំបូង ហើយរដ្ឋ B, D, E គឺជារដ្ឋចុងក្រោយ។
តារាងផ្លាស់ប្តូរពេញលេញត្រូវបានបង្ហាញខាងក្រោម។
ខាងក្រោមនៅក្នុងរូបភាពទី 5 គឺជា DFA ខ្លួនវាផ្ទាល់សម្រាប់ភាសានេះ។
រូបភាពទី 5. ភាសាទទួលយក DFA (a|b) * a(a|b)(a|b)
បញ្ជីអក្សរសិល្ប៍ដែលបានប្រើ៖
Pentus A.E., Pentus M. R. - ទ្រឹស្តីនៃភាសាផ្លូវការ
A. Aho, R. Sethi, D. Ullman - អ្នកចងក្រង៖ គោលការណ៍ បច្ចេកវិទ្យា ឧបករណ៍។
កន្សោមធម្មតា (RE) គឺជាទម្រង់នៃការសរសេរដ៏ងាយស្រួលបំផុត ដែលហៅថាភាសាធម្មតា ឬភាសាស្វ័យប្រវត្តិ។ ដូច្នេះ RTs ត្រូវបានប្រើជាភាសាបញ្ចូលក្នុងប្រព័ន្ធជាច្រើនដែលដំណើរការខ្សែសង្វាក់។ តោះមើលឧទាហរណ៍នៃប្រព័ន្ធបែបនេះ៖
- ប្រព័ន្ធប្រតិបត្តិការ Unix grep ឬពាក្យបញ្ជាស្រដៀងគ្នាស្វែងរកខ្សែអក្សរដែលអាចត្រូវបានរកឃើញនៅក្នុងកម្មវិធីរុករកតាមអ៊ីនធឺណិត ឬប្រព័ន្ធធ្វើទ្រង់ទ្រាយអត្ថបទ។ នៅក្នុងប្រព័ន្ធបែបនេះ RFs ត្រូវបានប្រើដើម្បីពិពណ៌នាអំពីគំរូដែលអ្នកប្រើប្រាស់កំពុងស្វែងរកនៅក្នុងឯកសារមួយ។ ម៉ាស៊ីនស្វែងរកផ្សេងៗបំប្លែងម៉ាស៊ីនស្វែងរកទៅជាម៉ាស៊ីនកំណត់រដ្ឋកំណត់ (DFA) ឬម៉ាស៊ីនកំណត់រដ្ឋមិនកំណត់ (NFA) ហើយអនុវត្តម៉ាស៊ីននេះទៅនឹងឯកសារដែលកំពុងស្វែងរក។
- អ្នកបង្កើតឧបករណ៍វិភាគ lexical ។ ឧបករណ៍វិភាគ Lexical គឺជាធាតុផ្សំនៃកម្មវិធីចងក្រង ពួកវាបំបែកកម្មវិធីប្រភពទៅជាឯកតាតក្កវិជ្ជា (និមិត្តសញ្ញា) ដែលអាចមានតួអក្សរមួយ ឬច្រើន និងមានអត្ថន័យជាក់លាក់។ ម៉ាស៊ីនបង្កើតឧបករណ៍វិភាគ lexical ទទួលបានការពិពណ៌នាជាផ្លូវការនៃ lexemes ដែលជា RVs សំខាន់ៗ និងបង្កើត DFA ដែលទទួលស្គាល់ថា lexemes មួយណាលេចឡើងនៅក្នុងការបញ្ចូលរបស់វា។
- RV ជាភាសាសរសេរកម្មវិធី។
នៅក្នុងអត្ថបទនេះ ជាដំបូងយើងនឹងស្គាល់ម៉ាស៊ីនរដ្ឋកំណត់ និងប្រភេទរបស់វា (DFA និង NFA) ហើយបន្ទាប់មកពិចារណាឧទាហរណ៍នៃការសាងសង់ DFA តិចតួចដោយប្រើកន្សោមធម្មតា។
ម៉ាស៊ីនរដ្ឋមានកំណត់ A finite state machines (FA) គឺជាកម្មវិធីបំប្លែងដែលអនុញ្ញាតឱ្យអ្នកភ្ជាប់ធាតុបញ្ចូលជាមួយទិន្នផលដែលត្រូវគ្នា ហើយលទ្ធផលនេះអាចពឹងផ្អែកមិនត្រឹមតែលើការបញ្ចូលបច្ចុប្បន្នប៉ុណ្ណោះទេ ប៉ុន្តែក៏អាស្រ័យលើអ្វីដែលបានកើតឡើងពីមុន លើប្រវត្តិប្រតិបត្តិការផងដែរ។ នៃម៉ាស៊ីនរដ្ឋកំណត់។ សូម្បីតែឥរិយាបទរបស់មនុស្ស និងមិនត្រឹមតែប្រព័ន្ធសិប្បនិម្មិតប៉ុណ្ណោះទេ អាចត្រូវបានពិពណ៌នាដោយប្រើយានអវកាស។ ជាឧទាហរណ៍ ប្រតិកម្មរបស់អ្នកចំពោះការពិតដែលថាអ្នកជិតខាងរបស់អ្នកស្តាប់តន្ត្រីខ្លាំងនៅពេលយប់នឹងកើតឡើងបន្ទាប់ពីឧបទ្ទវហេតុបែបនេះជាលើកដំបូង ហើយខុសគ្នាទាំងស្រុងបន្ទាប់ពីឧប្បត្តិហេតុបែបនេះជាច្រើន។ អាចមានចំនួនមិនកំណត់នៃបុរេប្រវត្តិបែបនេះ សំណួរកើតឡើង៖ តើយានអវកាសគួរមានការចងចាំប្រភេទណា ដើម្បីមានឥរិយាបទខុសគ្នាសម្រាប់បុរេប្រវត្តិនីមួយៗ? វាច្បាស់ណាស់ថាវាមិនអាចទៅរួចទេក្នុងការរក្សាទុកនូវចំនួន backstory ដែលគ្មានកំណត់។ ដូច្នេះ ប្រភេទ automaton បំបែកបុរេប្រវត្តិដែលអាចកើតមានទាំងអស់ទៅជាថ្នាក់សមមូល។ ប្រវត្តិពីរគឺសមមូលប្រសិនបើពួកគេមានឥទ្ធិពលដូចគ្នាលើឥរិយាបថរបស់ម៉ាស៊ីននាពេលអនាគត។ ថ្នាក់សមមូលដែល automaton បានកំណត់ប្រវត្តិបច្ចុប្បន្នរបស់វាត្រូវបានគេហៅថា ស្ថានភាពខាងក្នុងនៃ automaton ផងដែរ។ចូរយើងពិចារណាឧទាហរណ៍នៃប្រតិបត្តិការនៃយានអវកាសបុព្វកាល៖
យានអវកាសនេះរួមមានៈ
- កាសែតដែលតំណាងដោយខ្សែសង្វាក់បញ្ចូល។
- ឧបករណ៍អាន។
- ប្លុកវត្ថុបញ្ជាដែលមានបញ្ជីនៃច្បាប់ផ្លាស់ប្តូរ។
អ្នកអានអាចផ្លាស់ទីក្នុងទិសដៅមួយ ជាធម្មតាពីឆ្វេងទៅស្តាំ ដោយហេតុនេះការអានតួអក្សរនៃខ្សែអក្សរបញ្ចូល។ សម្រាប់ចលនាបែបនេះនីមួយៗ វាអាចរាប់និមិត្តសញ្ញាមួយ។ បន្ទាប់មកតួអក្សរដែលបានអានត្រូវបានបញ្ជូនទៅអង្គភាពបញ្ជា។ អង្គភាពបញ្ជាផ្លាស់ប្តូរស្ថានភាពរបស់ម៉ាស៊ីនដោយផ្អែកលើច្បាប់ផ្លាស់ប្តូរ។ ប្រសិនបើបញ្ជីនៃច្បាប់ផ្លាស់ប្តូរមិនមានច្បាប់សម្រាប់អាននិមិត្តសញ្ញាទេនោះម៉ាស៊ីន "ស្លាប់" ។
ឥឡូវនេះសូមក្រឡេកមើលវិធីដែល CA អាចត្រូវបានបញ្ជាក់។ ពួកវាអាចត្រូវបានបញ្ជាក់ជាទម្រង់ក្រាហ្វ ឬក្នុងទម្រង់តារាងត្រួតពិនិត្យ។ ក្នុងទម្រង់ជាក្រាហ្វ CA ត្រូវបានបញ្ជាក់តាមវិធីខាងក្រោម៖
- ចំនុចកំពូលនៃក្រាហ្វត្រូវគ្នាទៅនឹងស្ថានភាពនៃយានអវកាស។
- គែមដែលដឹកនាំត្រូវគ្នាទៅនឹងមុខងារផ្លាស់ប្តូរ (នៅជាប់គែមនីមួយៗ និមិត្តសញ្ញាដែលការផ្លាស់ប្តូរត្រូវបានអនុវត្តត្រូវបានចង្អុលបង្ហាញ) ។
- ចំនុចកំពូលដែលមានគែមបញ្ចូលវាដែលមិនទុករដ្ឋច្រើនជាងមួយត្រូវគ្នាទៅនឹងស្ថានភាពដំបូង។
- ស្ថានភាពចុងក្រោយនៃយានអវកាសត្រូវបានសម្គាល់ដោយគ្រោងក្រាស់។
នៅក្នុងទម្រង់នៃតារាងត្រួតពិនិត្យដូចនេះ៖
- រដ្ឋនៃយានអវកាសមានទីតាំងនៅជួរតារាង។
- តួអក្សរនៃភាសាដែលទទួលស្គាល់គឺនៅក្នុងជួរឈរ។
- នៅចំនុចប្រសព្វ រដ្ឋមួយត្រូវបានចង្អុលបង្ហាញដែលអាចទៅដល់ពីរដ្ឋដែលបានផ្តល់ឱ្យដោយប្រើនិមិត្តសញ្ញាដែលបានផ្តល់ឱ្យ។
ឧទាហរណ៍នៃ CA ក្នុងទម្រង់ជាក្រាហ្វ និងជាទម្រង់តារាងត្រួតពិនិត្យនឹងត្រូវបានបង្ហាញខាងក្រោម។
DKA និង NKAភាពខុសគ្នាសំខាន់រវាង DKA និង NKA គឺថា DKA អាចស្ថិតនៅក្នុងរដ្ឋតែមួយក្នុងអំឡុងពេលប្រតិបត្តិការ ខណៈដែល NKA អាចស្ថិតនៅក្នុងរដ្ឋជាច្រើនក្នុងពេលតែមួយ។ ជាឧទាហរណ៍នៃការងាររបស់ NCA មនុស្សម្នាក់អាចដកស្រង់គំនិតរបស់អ្នករូបវិទ្យាជនជាតិអាមេរិកលោក Hugh Everett ថាព្រឹត្តិការណ៍ណាមួយបានបំបែកពិភពលោកទៅជាពិភពលោកជាច្រើន ដែលព្រឹត្តិការណ៍នីមួយៗនេះបានបញ្ចប់តាមរបៀបរបស់ខ្លួន។ ជាឧទាហរណ៍ នៅក្នុងពិភពលោកមួយ ហ៊ីត្លែរបានឈ្នះសង្គ្រាមលោកលើកទីពីរ មួយទៀត ញូវតុន បានចូលទៅក្នុងអាជីវកម្មជំនួសឱ្យរូបវិទ្យា ហើយការរកឃើញច្បាប់នៃមេកានិចបុរាណត្រូវពន្យារពេល 50 ឆ្នាំ ដើម្បីទាញការសន្និដ្ឋានណាមួយពីប្រតិបត្តិការរបស់ អូតូម៉ាតុន "ពិភពលោក" ទាំងអស់គួរតែត្រូវបានសិក្សា។ បន្ទាប់ពីខ្សែសង្វាក់បញ្ចូលទាំងមូលត្រូវបានអានរួច យើងសន្មត់ថា NFA ទទួលយកខ្សែសង្វាក់នេះ ប្រសិនបើវាបានបញ្ចប់ប្រតិបត្តិការនៅក្នុងស្ថានភាពទទួលយកយ៉ាងហោចណាស់មួយនៃ "ពិភពលោក" ជាច្រើន។ ដូច្នោះហើយ automaton ច្រានចោលខ្សែសង្វាក់ ប្រសិនបើវាបញ្ចប់នៅក្នុងស្ថានភាពមិនទទួលយកនៅក្នុង "ពិភពលោក" នីមួយៗ។ DKA ទទួលយកខ្សែសង្វាក់នេះ ជាក់ស្តែងប្រសិនបើបន្ទាប់ពីអានខ្សែសង្វាក់បញ្ចូលទាំងមូល វាឃើញថាខ្លួនវាស្ថិតក្នុងស្ថានភាពទទួលយក។
ក្នុងករណីភាគច្រើនវាងាយស្រួលជាងក្នុងការសាងសង់ NKV ជាង DKA ។ ប៉ុន្តែទោះបីជាយ៉ាងនេះក៏ដោយ ការប្រើប្រាស់ NKA សម្រាប់ធ្វើជាគំរូមិនមែនជាគំនិតល្អនោះទេ។ ជាសំណាងល្អ សម្រាប់ NFA នីមួយៗ វាអាចបង្កើត DFA ដែលទទួលយកភាសាបញ្ចូលដូចគ្នា។ នៅក្នុងអត្ថបទនេះ យើងនឹងមិនបង្ហាញក្បួនដោះស្រាយសម្រាប់ការសាងសង់ DFA ដោយប្រើ NFA ទេ ប៉ុន្តែនឹងពិចារណាអំពីក្បួនដោះស្រាយនេះដោយផ្អែកលើឧទាហរណ៍ខាងក្រោម។
បង្កើត DFA តិចតួចដោយប្រើកន្សោមធម្មតា។ដើម្បីចាប់ផ្តើម នេះជាបញ្ជីនៃប្រតិបត្តិការ RT ដែលប្រើក្នុងអត្ថបទនេះ តាមលំដាប់អាទិភាព៖
- ការធ្វើឡើងវិញ (ការបិទ Kleene) ដោយប្រើនិមិត្តសញ្ញា "*"
- ការភ្ជាប់គ្នាត្រូវបានបញ្ជាក់ដោយប្រើចន្លោះ ឬខ្សែអក្សរទទេ (ឧទាហរណ៍៖ ab)
- ចូលរួមដោយប្រើនិមិត្តសញ្ញា "|"
សូមក្រឡេកមើលឧទាហរណ៍មួយដែលកន្សោមធម្មតាត្រូវបានផ្តល់ឱ្យ៖
Xy* (x | y*) |
ab (x | y *) |
(x | a*) (x | y*)
វាចាំបាច់ក្នុងការសាងសង់ DFA តិចតួចដោយប្រើកន្សោមធម្មតា និងបង្ហាញពីការទទួលស្គាល់ខ្សែសង្វាក់ត្រឹមត្រូវ និងមិនត្រឹមត្រូវ។
ដើម្បីចាប់ផ្តើម សូមសម្រួល RV នេះ ដោយប្រើច្បាប់ចែកចាយដៃស្តាំនៃការភ្ជាប់ជាមួយសហជីព យើងទទួលបាន RV ខាងក្រោម៖
(xy* | ab | (x | a*)) (x | y*)
ឥឡូវនេះយើងបង្កើត automaton ដោយផ្អែកលើ RV នេះ:
យោងទៅតាមច្បាប់សម្រាប់ការបំប្លែង concatenation (យើងនឹងមិនផ្តល់ច្បាប់សម្រាប់ការបំប្លែង PB ទៅជា KA ទេព្រោះវាច្បាស់ណាស់) យើងទទួលបាន automaton ដូចខាងក្រោម៖
ហើយនៅចុងបញ្ចប់ យើងអនុវត្តច្បាប់បំលែងការបិទ និងទទួលបាន εNKA ។ នៅទីនេះ ចាំបាច់ត្រូវធ្វើការកក់ទុកថា εNKA គឺជា NKA ដែលមាន ε-transitions ។ នៅក្នុងវេន ε-transition គឺជាការផ្លាស់ប្តូរដែលម៉ាស៊ីនមិនគិតពីខ្សែសង្វាក់បញ្ចូល ឬនិយាយម្យ៉ាងទៀត ការផ្លាស់ប្តូរតាមបណ្តោយនិមិត្តសញ្ញាទទេ។
យើងកម្ចាត់ ε-transitions ("សញ្ញាផ្កាយ" តំណាងឱ្យរដ្ឋចុងក្រោយ):
នៅក្នុង NFA នេះ រដ្ឋ s3 និង s5 គឺសមមូល ចាប់តាំងពី δ(s3, x) = δ(s5, x) = s1 និង δ(s3, y) = δ(s5, y) = s5, s7 ។ ប្តូរឈ្មោះរដ្ឋ s6 -> s5 និង s7 -> s6:
យើងបង្កើត DKA យោងទៅតាម NKA:
នៅក្នុង DFA នេះ រដ្ឋ p1 និង p5 គឺសមមូល ចាប់តាំងពី
δ(p1, x) = δ(p5, x) = p4 និង δ(p1, y) = δ(p5, y) = p5 ។ ប្តូរឈ្មោះរដ្ឋ p6 -> p5 និង p7 -> p6:
ម៉ាស៊ីននេះគឺជា DKA តិចតួចបំផុត។
អនុញ្ញាតឱ្យ δ ជាអនុគមន៍ផ្លាស់ប្តូរ បន្ទាប់មកយើងសម្គាល់មុខងារផ្លាស់ប្តូរដែលបានពង្រីកដែលបង្កើតពី δ ដោយ δ' ហើយ ω គឺជាខ្សែសង្វាក់បញ្ចូល។
ឧបមាថាការបញ្ចូលគឺជាខ្សែសង្វាក់ ω = aaax យើងរំពឹងថាម៉ាស៊ីននឹងស្ថិតនៅក្នុងរដ្ឋមួយដែលទទួលយក។
δ'(p0, ε) = p0
δ'(p0, a) = δ(δ'(p0, ε), a) = δ(p0, a) = p3
δ'(p0, aa) = δ(δ'(p0, a), a) = δ(p3, a) = p5
δ'(p0, aaa) = δ(δ'(p0, aa), a) = δ(p5, a) = p5
δ'(p0, aaax) = δ(δ'(p0, aaa), x) = δ(p5, x) = p4
P4 គឺជាស្ថានភាពចុងក្រោយដែលមានសុពលភាព ដូច្នេះខ្សែសង្វាក់ aaax គឺត្រឹមត្រូវសម្រាប់ម៉ាស៊ីននេះ។
ឥឡូវសូមសន្មតថា ω = xyyb៖
δ'(p0, ε) = p0
δ'(p0, x) = δ(δ'(p0, ε), x) = δ(p0, x) = p1
δ'(p0, xy) = δ(δ'(p0, x), y) = δ(p1, y) = p1
δ'(p0, xyy) = δ(δ'(p0, xy), y) = δ(p1, y) = p1
δ'(p0, xyyb) = δ(δ'(p0, xyy), b) = δ(p1, b) = ∅
នៅទីនេះយើងឃើញថាប្រសិនបើយើងផ្តល់និមិត្តសញ្ញា b ទៅការបញ្ចូលរបស់ automaton នៅពេលដែលវាស្ថិតនៅក្នុងស្ថានភាព p1 នោះ automaton នេះនឹងស្លាប់ ដូច្នេះសង្វាក់ xyyb មិនត្រឹមត្រូវទេ។
P. S. អត្ថបទនេះបានពិភាក្សាអំពីក្បួនដោះស្រាយសម្រាប់បង្កើត DFA ដោយប្រើ RT ប៉ុន្តែមានក្បួនដោះស្រាយងាយស្រួលជាង ជាពិសេសសម្រាប់ការសរសេរកម្មវិធី ប៉ុន្តែនេះគឺជាប្រធានបទសម្រាប់អត្ថបទមួយទៀត...