បំប្លែងកន្សោមធម្មតាទៅជាម៉ាស៊ីនរដ្ឋមិនកំណត់។ ការវិភាគ Lexical

ត្រូវការដោយម៉ាស៊ីនរដ្ឋមិនកំណត់ ម = (សំណួរ, ធ, ឃ, q 0 , ច) បង្កើតម៉ាស៊ីនកំណត់ស្ថានភាពកំណត់ ម = (សំណួរ", ធ, ឃ", q" 0 , F") ស្ថានភាពដំបូងសម្រាប់ automaton ដែលកំពុងសាងសង់គឺជាការបិទε-បិទនៃស្ថានភាពដំបូងនៃ automaton ដំបូង។ ε-បិទ - សំណុំនៃរដ្ឋដែលអាចទៅដល់ពីមួយដែលបានផ្តល់ឱ្យដោយការផ្លាស់ប្តូរតាមបណ្តោយε។ លើសពីនេះទៀត ខណៈពេលដែលមានរដ្ឋដែលការផ្លាស់ប្តូរមិនត្រូវបានសាងសង់ (ការផ្លាស់ប្តូរត្រូវបានធ្វើឡើងដោយនិមិត្តសញ្ញា ការផ្លាស់ប្តូរតាមរយៈនោះនៅក្នុង automaton ដើម) សម្រាប់និមិត្តសញ្ញានីមួយៗ ε-បិទនៃសំណុំនៃរដ្ឋដែលអាចទៅដល់បានពីរដ្ឋដែលបានពិចារណា។ ដោយការផ្លាស់ប្តូរតាមរយៈនិមិត្តសញ្ញាដែលបានពិចារណាត្រូវបានគណនា។ ប្រសិនបើស្ថានភាពដែលត្រូវគ្នានឹងសំណុំដែលបានរកឃើញមានរួចហើយ នោះការផ្លាស់ប្តូរត្រូវបានបន្ថែមនៅទីនោះ។ ប្រសិនបើមិនមានទេ រដ្ឋដែលទទួលបានថ្មីត្រូវបានបន្ថែម។

ឧទាហរណ៍

ការចាប់ផ្តើម

រដ្ឋដែលត្រូវគ្នាទៅនឹងε-បិទនៃរដ្ឋដំបូងត្រូវបានសម្គាល់។ រដ្ឋទាំងនេះនឹងត្រូវគ្នាទៅនឹងរដ្ឋ ក DKA នាពេលអនាគត។


ការធ្វើម្តងទៀតជាលើកដំបូង

មានការផ្លាស់ប្តូរពីការបិទ ε ទៅរដ្ឋ NCA 3 និង 10 (យោងទៅតាម កនិង គរៀងៗខ្លួន)។ សម្រាប់រដ្ឋ 3 ការបិទ ε គឺជាសំណុំនៃរដ្ឋ (3, 4, 6) សម្រាប់រដ្ឋ 10 - (10) ។ អនុញ្ញាតឱ្យយើងកំណត់រដ្ឋ DFA ថ្មីដែលត្រូវនឹងសំណុំទាំងនេះជា ខនិង គ.

រដ្ឋ DKAសំណុំនៃរដ្ឋ NFA
ក ខ គ
ក{1, 2, 9} ខ - គ
ខ{3, 4, 6} - - -
គ{10} - - -


ការធ្វើម្តងទៀតទីពីរ

ពីសំណុំនៃរដ្ឋនៃ NFA (3, 4, 6) ដែលត្រូវគ្នាទៅនឹងស្ថានភាពនៃ DFA ខមានការផ្លាស់ប្តូរពីរ - ទៅរដ្ឋ 5 (ដោយ ខ) និង 7 (ដោយ គ) ការបិទ ε របស់ពួកគេប្រសព្វគ្នា ប៉ុន្តែសំណុំខ្លួនពួកគេខុសគ្នា ដូច្នេះពួកគេត្រូវបានចាត់តាំងរដ្ឋ DFA ថ្មីពីរ - ឃនិង អ៊ី. ពីរដ្ឋនៃ NFA ដែលត្រូវគ្នាទៅនឹងស្ថានភាពនៃ DFA គ, មិនមានការផ្លាស់ប្តូរទេ។

រដ្ឋ DKAសំណុំនៃរដ្ឋ NFAតួអក្សរដែលអាចលោតបាន។
ក ខ គ
ក{1, 2, 9} ខ - គ
ខ{3, 4, 6} - ឃអ៊ី
គ{10} - - -
ឃ{2, 5, 8, 9} - - -
អ៊ី{2, 7, 8, 9} - - -


ការធ្វើម្តងទៀតទីបី

ពីសំណុំនៃរដ្ឋនៃ NFA ដែលត្រូវគ្នាទៅនឹងរដ្ឋនៃ DFA ឃនិង អ៊ីការផ្លាស់ប្តូរត្រូវបានធ្វើឡើងចំពោះសំណុំនៃរដ្ឋដែលត្រូវគ្នានឹងរដ្ឋដែលមានស្រាប់ (ពីសំណុំ (2, 5, 8, 9) ដែលត្រូវគ្នានឹងរដ្ឋ ឃលើ កការផ្លាស់ប្តូរទៅរដ្ឋ 3 ដែលជាកម្មសិទ្ធិរបស់សំណុំ (3, 4, 6) ដែលត្រូវគ្នាទៅនឹងស្ថានភាពនៃ DFA ខលើ គ- ការផ្លាស់ប្តូរទៅជារដ្ឋ 10 ដែលត្រូវគ្នានឹងរដ្ឋ គ; ដូចគ្នានេះដែរសម្រាប់សំណុំដែលត្រូវគ្នាទៅនឹងស្ថានភាពនៃ DFA អ៊ី) ដំណើរការនៃការសាងសង់តារាងរដ្ឋ និងការផ្លាស់ប្តូរនៃ DFA ត្រូវបានបញ្ចប់។

រដ្ឋ DKAសំណុំនៃរដ្ឋ NFAតួអក្សរដែលអាចលោតបាន។
ក ខ គ
ក{1, 2, 9} ខ - គ
ខ{3, 4, 6} - ឃអ៊ី
គ{10} - - -
ឃ{2, 5, 8, 9} ខ - គ
អ៊ី{2, 7, 8, 9} ខ - គ


លទ្ធផល៖

ការកសាងវេយ្យាករណ៍លីនេអ៊ែរស្តាំពី automaton កំណត់

រដ្ឋនីមួយៗត្រូវបានភ្ជាប់ជាមួយ non-terminal ។ ប្រសិនបើមានការផ្លាស់ប្តូររដ្ឋ Xចូលទៅក្នុងរដ្ឋមួយ។ យនៅលើ កបន្ថែមច្បាប់ X → អាយ. សម្រាប់រដ្ឋចុងក្រោយ បន្ថែមច្បាប់ X→ អ៊ី. សម្រាប់ ε-transitions - X → យ.

ឧទាហរណ៍ទី 1 (ម៉ាស៊ីនកំណត់ស្ថានភាព)

  • ក → កខ | គគ
  • ខ → ខឃ | គអ៊ី
  • គ → អ៊ី
  • ឃ → កខ | គគ
  • អ៊ី → កខ | គគ

ឧទាហរណ៍ទី 2 (ម៉ាស៊ីនរដ្ឋមិនកំណត់)

  • 1 → 2 | 9
  • 2 → ក 3
  • 3 → 4 | 6
  • 4 → ខ 5
  • 5 → 8
  • 6 → គ 7
  • 7 → 8
  • 8 → 2 | 9
  • 9 → គ 10
  • ១០ → ε

ការសាងសង់ DFA ដោយ RV

ចូរ​បញ្ចេញ​មតិ​ជា​ប្រចាំ r. ដោយផ្អែកលើកន្សោមធម្មតានេះ វាចាំបាច់ក្នុងការបង្កើត automaton finite deterministic ឃបែបនោះ។ អិល(ឃ) = អិល(r).

ការកែប្រែការបញ្ចេញមតិជាទៀងទាត់

ចូរបន្ថែមនិមិត្តសញ្ញាទៅវាមានន័យថាចុងបញ្ចប់នៃ RV - "#" ។ ជាលទ្ធផល យើងទទួលបានកន្សោមធម្មតា ( r)#.

សាងសង់ដើមឈើ

ចូរយើងស្រមៃមើលកន្សោមធម្មតាជាមែកធាង ស្លឹកដែលជាតួអក្សរស្ថានីយ ហើយថ្នាំងខាងក្នុងគឺជាប្រតិបត្តិការនៃ concatenation ".", union "∪" និង iteration "*" ។ យើងកំណត់លេខតែមួយគត់ទៅស្លឹកនីមួយៗនៃដើមឈើ (លើកលែងតែស្លឹកε) ហើយសំដៅលើវានៅលើដៃម្ខាងជាទីតាំងនៅក្នុងដើមឈើ និងម្យ៉ាងវិញទៀតជាទីតាំងនៃនិមិត្តសញ្ញាដែលត្រូវគ្នានឹង ស្លឹក។

ការគណនានៃអនុគមន៍ដែលមិនអាចរាប់បាន, firstpos, lastpos

ឥឡូវនេះដោយឆ្លងកាត់មែកធាង T ពីបាតទៅកំពូលពីឆ្វេងទៅស្តាំយើងគណនាមុខងារបី: ទុកជាមោឃៈ, អត្ថបទដំបូង, និង ចុងក្រោយ. មុខងារ ទុកជាមោឃៈ, អត្ថបទដំបូងនិង ចុងក្រោយកំណត់នៅថ្នាំងនៃដើមឈើ។ តម្លៃនៃមុខងារទាំងអស់លើកលែងតែ ទុកជាមោឃៈគឺជាសំណុំនៃមុខតំណែង។ មុខងារ អត្ថបទដំបូង(ន) សម្រាប់ថ្នាំងនីមួយៗនៃមែកធាងវាក្យសម្ព័ន្ធ regex ផ្តល់សំណុំនៃមុខតំណែងដែលត្រូវគ្នានឹងតួអក្សរដំបូងនៅក្នុងខ្សែអក្សររងដែលបង្កើតដោយកន្សោមរងដែលបញ្ចប់នៅ ន. ដូចគ្នានេះដែរ ចុងក្រោយ(ន) ផ្តល់ឱ្យសំណុំនៃមុខតំណែងដែលត្រូវគ្នាទៅនឹងតួអក្សរចុងក្រោយនៅក្នុងខ្សែអក្សររងដែលបង្កើតដោយកន្សោមរងជាមួយកំពូល ន. សម្រាប់ថ្នាំង នមែកធាងរង (នោះគឺដើមឈើដែលមានថ្នាំង ន is a root) អាចបង្កើតពាក្យទទេ យើងកំណត់ ទុកជាមោឃៈ(ន) = ពិតនិងសម្រាប់ថ្នាំងផ្សេងទៀត។ មិនពិត. តារាងគណនា ទុកជាមោឃៈ, អត្ថបទដំបូង, ចុងក្រោយ:

knot ន ទុកជាមោឃៈ(ន) អត្ថបទដំបូង(ន) ចុងក្រោយ(ន)
ε ពិត ∅ ∅
ខ្ញុំ ≠ ε មិនពិត {ខ្ញុំ} {ខ្ញុំ}
u ∪ vទុកជាមោឃៈ(យូ) ឬ ទុកជាមោឃៈ(v) អត្ថបទដំបូង(យូ) ∪ អត្ថបទដំបូង(v) ចុងក្រោយ(យូ) ∪ ចុងក្រោយ(v)
យូ. vទុកជាមោឃៈ(យូ) និង ទុកជាមោឃៈ(v) ប្រសិនបើ ទុកជាមោឃៈ(យូ) បន្ទាប់មក អត្ថបទដំបូង(យូ) ∪ អត្ថបទដំបូង(v) ផ្សេងទៀត។ អត្ថបទដំបូង(យូ) ប្រសិនបើ ទុកជាមោឃៈ(v) បន្ទាប់មក ចុងក្រោយ(យូ) ∪ ចុងក្រោយ(v) ផ្សេងទៀត។ ចុងក្រោយ(v)
v*ពិត អត្ថបទដំបូង(v) ចុងក្រោយ(v)

ការ​កសាង​តាម​ក្រោយ​

មុខងារ តាមដានគណនាតាមរយៈ ទុកជាមោឃៈ, អត្ថបទដំបូងនិង ចុងក្រោយ. មុខងារ តាមដានកំណត់លើមុខតំណែងជាច្រើន។ អត្ថន័យ តាមដានគឺជាសំណុំនៃមុខតំណែង។ ប្រសិនបើ ក ខ្ញុំ- ទីតាំងបន្ទាប់មក តាមដាន(ខ្ញុំ) មានមុខតំណែងជាច្រើន។ jដូចជាមានខ្សែរខ្លះ... ស៊ីឌី... រួមបញ្ចូលនៅក្នុងភាសាដែលបានពិពណ៌នាដោយ RW បែបនោះ។ ខ្ញុំផ្គូផ្គងធាតុនេះ។ គ, ក j- ចូល ឃ. មុខងារ តាមដានក៏អាចត្រូវបានគណនានៅក្នុងផ្លូវឆ្លងកាត់មួយនៃដើមឈើនេះបើយោងតាមច្បាប់ពីរខាងក្រោម

  1. អនុញ្ញាតឱ្យមាន ន- ថ្នាំងខាងក្នុងជាមួយ "." (ការភ្ជាប់គ្នា); ក, ខ- កូនចៅរបស់គាត់។ បន្ទាប់មកសម្រាប់មុខតំណែងនីមួយៗ ខ្ញុំរួមបញ្ចូលនៅក្នុង ចុងក្រោយ(ក តាមដាន(ខ្ញុំ) មួយ​បាច់ អត្ថបទដំបូង(ខ).
  2. អនុញ្ញាតឱ្យមាន ន- ថ្នាំងខាងក្នុងដែលមានប្រតិបត្តិការ "*" (ការធ្វើឡើងវិញ), ក- កូនចៅរបស់គាត់។ បន្ទាប់មកសម្រាប់មុខតំណែងនីមួយៗ ខ្ញុំរួមបញ្ចូលនៅក្នុង ចុងក្រោយ(ក) បន្ថែមទៅសំណុំនៃតម្លៃ តាមដាន(ខ្ញុំ) មួយ​បាច់ អត្ថបទដំបូង(ក).

ឧទាហរណ៍

គណនាតម្លៃមុខងារ តាមដានសម្រាប់ការបញ្ចេញមតិធម្មតា ( ក(ខ|គ))*គ.

ទីតាំងអត្ថន័យ តាមដាន
1: (ក (ខ|គ))*គ {2, 3}
2: (ក(ខ |គ))*គ {1, 4}
3: (ក(ខ|គ ))*គ {1, 4}
4: (ក(ខ|គ))*គ {5}

ការកសាង DFA

DFA គឺជាសំណុំនៃរដ្ឋ និងសំណុំនៃការផ្លាស់ប្តូររវាងពួកគេ។ រដ្ឋ DFA គឺជាសំណុំនៃមុខតំណែង។ ការសាងសង់ DFA មាននៅក្នុងការបន្ថែមបន្តិចម្តង ៗ នៃរដ្ឋចាំបាច់ទៅវា និងការសាងសង់ការផ្លាស់ប្តូរសម្រាប់ពួកគេ។ ដំបូងមានរដ្ឋមួយ។ អត្ថបទដំបូង(ឫស) (ឫស- ឫសនៃដើមឈើ) ដែលមិនមានការផ្លាស់ប្តូរ។ ការផ្លាស់ប្តូរត្រូវបានអនុវត្តដោយតួអក្សរពីកន្សោមធម្មតា។ តួអក្សរនីមួយៗត្រូវគ្នាទៅនឹងសំណុំនៃមុខតំណែង ( ទំ ខ្ញុំ) រួបរួមទាំងអស់គ្នា តាមដាន(x) គឺជារដ្ឋដែលចាំបាច់ត្រូវទៅ ដែល x គឺជាទីតាំងដែលមានទាំងមុខតំណែងរបស់រដ្ឋ និងក្នុងចំណោមមុខតំណែងនៃនិមិត្តសញ្ញាពី RE ដែលការផ្លាស់ប្តូរត្រូវបានធ្វើឡើង។ ប្រសិនបើមិនមានរដ្ឋបែបនេះទេនោះវាត្រូវតែបន្ថែម។ ដំណើរការត្រូវតែធ្វើម្តងទៀតរហូតដល់ការផ្លាស់ប្តូរទាំងអស់សម្រាប់រដ្ឋទាំងអស់ត្រូវបានបង្កើតឡើង។ រដ្ឋទាំងអស់ដែលមានទីតាំងនៃនិមិត្តសញ្ញា # ត្រូវបានបន្ថែមទៅចុងបញ្ចប់នៃ RE ត្រូវបានប្រកាសថាចុងក្រោយ។

DFA ទទួលបានពី RV ( ក(ខ|គ))*គ

ឧទាហរណ៍

បង្កើត DFA ដោយកន្សោមធម្មតា ( ក(ខ|គ))*គ.

រដ្ឋ DKAនិមិត្តសញ្ញា
a(1)b(2)គ(៣, ៤)
ក(១, ៤)ខ(២,៣) - C(5)
ខ(២,៣) - ក(១, ៤)ក(១, ៤)
C(5) - - -

ការកសាង DFA ជាមួយនឹងចំនួនរដ្ឋអប្បបរមា

DFA ដែលមានចំនួនរដ្ឋអប្បបរមាត្រូវបានសាងសង់សម្រាប់ DFA ដែលបានកំណត់គ្រប់ទីកន្លែង ពោលគឺ បែបនោះ។ សម្រាប់ DFA ណាមួយ មាន DFA ដែលកំណត់គ្រប់ទីកន្លែងដែលស្មើនឹងវា។

ការសាងសង់ DFA ដែលបានកំណត់គ្រប់ទីកន្លែង

ណែនាំរដ្ឋថ្មី និងកំណត់សំណុំរដ្ឋថ្មី។ .

ចូរកំណត់មុខងារផ្លាស់ប្តូរថ្មីដូចនេះ៖

ការបង្កើតភាគថាស (ជាផ្លូវការ)

ចូរយើងបង្កើតភាគថាសដំបូង ទំកំណត់រដ្ឋជាពីរក្រុម៖ រដ្ឋចុងក្រោយ ចហើយ​ផ្សេងទៀត S/F, i.e. ទំ = {ច, Q\F}.

អនុវត្តចំពោះក្រុមនីមួយៗ ជី ∈ ទំតាមនីតិវិធី។ កម្ទេច ជីចូលទៅក្នុងក្រុមរងដើម្បីឱ្យរដ្ឋ សនិង tពី ជីបានបញ្ចប់នៅក្នុងក្រុមតែមួយប្រសិនបើ និងប្រសិនបើសម្រាប់និមិត្តសញ្ញាបញ្ចូលនីមួយៗ ករដ្ឋ សនិង tមានការផ្លាស់ប្តូរ កទៅរដ្ឋពីក្រុមដូចគ្នានៅក្នុង ទំ.

ក្រុមរងលទ្ធផលត្រូវបានបន្ថែមទៅភាគថាសថ្មី។ ទំថ្មី។

ទទួលយក ទំ = ទំថ្មី ហើយ​ធ្វើ​ការ​សាងសង់​ភាគថាស​ឡើងវិញ​រហូត​ដល់​ស្ថិរភាព ពោលគឺ​រហូតដល់​ភាគថាស​ឈប់​ផ្លាស់ប្តូរ។

ការបង្កើតភាគថាស (ក្បួនដោះស្រាយ)

ដើម្បីបង្កើតភាគថាសមានក្បួនដោះស្រាយដូចខាងក្រោម។ យើងបង្កើតតារាងផ្លាស់ប្តូរសម្រាប់ automaton ដើម បង្កើតភាគថាសដំបូង។

យើងកំណត់អត្តសញ្ញាណទៅក្រុមនីមួយៗពីភាគថាស (សម្រាប់ភាគថាសដំបូង ឧទាហរណ៍ 0 និង 1)។

រដ្ឋនីមួយៗ (ជួរនីមួយៗនៃតារាង) ត្រូវបានកំណត់ជាខ្សែអក្សរនៃទម្រង់ “a.bcd…xyz” ដែលជាកន្លែងកំណត់អត្តសញ្ញាណក្រុមដែលរដ្ឋជាកម្មសិទ្ធិពី [ជួរទីមួយ (កន្លែងដែលយើងទៅ) ទីពីរ ជួរឈរ (កន្លែងដែលយើងទៅដោយតួអក្សរទីមួយ), …, ជួរចុងក្រោយ (កន្លែងដែលយើងទៅដោយតួអក្សរចុងក្រោយ)] ។

យើង​បង្កើត​ក្រុម​ថ្មី​ដោយ​យោង​ទៅ​តាម​ភាព​ចៃដន្យ​នៃ​ខ្សែ​អក្សរ ពោល​គឺ​ដូច្នេះ​ថា​ក្រុម​ដែល​បាន​កំណត់​ដូចគ្នា​ធ្លាក់​ចូល​ទៅ​ក្នុង​ក្រុម​មួយ។

បន្ទាប់​មក ការ​ធ្វើ​ឡើង​វិញ។ យើងកំណត់អត្តសញ្ញាណថ្មីទៅក្រុមលទ្ធផល ឧទាហរណ៍ (0, 1, ..., n)។ ហើយយើងធ្វើម្តងទៀតនូវការសាងសង់ភាគថាសរហូតដល់ស្ថេរភាព។

ចំណាំថានៅពេលដែលមានរដ្ឋតែមួយនៅសល់ក្នុងក្រុម នៅដំណាក់កាលបន្តបន្ទាប់នៃការសាងសង់ភាគថាស អ្នកមិនអាចសរសេរខ្សែអក្សរនៃការកំណត់អត្តសញ្ញាណសម្រាប់រដ្ឋនេះទៀតទេ ដោយសារខ្សែអក្សរនេះនឹងមានតែមួយគត់ក្នុងករណីណាក៏ដោយ ដោយសារតែតួអក្សរទីមួយនៃ ខ្សែអក្សរ។ នៅក្នុងពាក្យផ្សេងទៀតនៅពេលដែលការបំបែកគ្មានអ្វីនឹងកើតឡើងចំពោះក្រុមមួយពីរដ្ឋមួយ - វាត្រូវបានផ្ទេរទៅការបំបែកថ្មីដូចដែលមាន។

ការសាងសង់ automaton កាត់បន្ថយ

ក្រុមលទ្ធផលនីមួយៗក្លាយជាស្ថានភាពនៃ DFA ថ្មី។ ប្រសិនបើក្រុមមានស្ថានភាពដំបូង (ចុងក្រោយ) នៃ automaton ដើម ក្រុមនេះនឹងក្លាយជារដ្ឋដំបូង (រៀងគ្នាចុងក្រោយ) នៃ DFA ថ្មី។ ការផ្លាស់ប្តូរត្រូវបានសាងសង់តាមរបៀបជាក់ស្តែង៖ ការផ្លាស់ប្តូរទៅរដ្ឋពីក្រុមមួយត្រូវបានចាត់ទុកថាជាការផ្លាស់ប្តូរទៅជាក្រុម។

យើងនាំយកម៉ាស៊ីន។ ដំបូងយើងដកធាតុមិនបង្កើត (មាប់មគ "ស្លាប់") បន្ទាប់មករដ្ឋដែលមិនអាចទៅដល់បាន (និយមន័យត្រូវបានផ្តល់ឱ្យសម្រាប់និមិត្តសញ្ញា ប៉ុន្តែនៅក្នុងវិធីជាក់ស្តែង ពួកគេត្រូវបានផ្ទេរទៅរដ្ឋនៃ automaton) ។

និយាយជាទូទៅ ការដករដ្ឋដែលស្លាប់ ប្រែ DFA ទៅជា NFA ចាប់តាំងពីនៅក្នុង DFA រាល់ការផ្លាស់ប្តូរទាំងអស់ត្រូវតែត្រូវបានកំណត់។ ទោះជាយ៉ាងណាក៏ដោយ នៅក្នុងសៀវភៅនាគ ការឃ្លាតឆ្ងាយពីនិយមន័យផ្លូវការនៅតែចាត់ទុកថាអាចទទួលយកបាន។

ឧទាហរណ៍

ដើម្បីបង្កើត DFA ជាមួយនឹងចំនួនរដ្ឋអប្បបរមាសម្រាប់ DFA នៃទម្រង់ខាងក្រោម៖

  • ការបំបែកដំបូង៖ (C) ( ស្ថានភាពចុងក្រោយ), (A, B, D, E) ( រដ្ឋផ្សេងទៀតទាំងអស់។).
  • (C)( ដោយគ្មានការផ្លាស់ប្តូរ), (A, D, E), (B), ( ចាប់តាំងពីយើងឆ្លងកាត់ពី A, D, E តាមបណ្ដោយ a, c ទៅ B និង C រៀងគ្នា។).
  • យើងមិនអាចធ្វើការបំបែកទៀតទេ។

អនុញ្ញាតឱ្យក្រុម (C) ទាក់ទងទៅនឹងរដ្ឋ C ក្រុម (A, D, E) ទៅរដ្ឋ A និងក្រុម (B) ទៅរដ្ឋ B ។ បន្ទាប់មកយើងទទួលបាន DFA ជាមួយនឹងចំនួនរដ្ឋអប្បបរមា៖

ឧទាហរណ៍ (ក្បួនដោះស្រាយសម្រាប់បង្កើតភាគថាស)

តារាងផ្លាស់ប្តូរសម្រាប់គ្រប់ទីកន្លែងដែលបានកំណត់ (រដ្ឋ Z បានបន្ថែម) DFA ដែលត្រូវគ្នានឹង RV (ab|ε)a*|abb|b*a ។ ពីសំណួរប្រឡងឆ្នាំ 2012 ។

កខខ្ញុំ ០ខ្ញុំ ១
→ A*ខគ0.01 0.12
ខ*ឃអ៊ី0.00 1.01
គចគ1.01
ឃ*ឃZ0.01 0.04
អ៊ី*ឃZ0.00 1.03
F*ZZ0.11
ZZZ1.11

ការធ្វើម្តងទៀត៖

  • I 0: ACDEF(0), CZ(1)។
  • I 1: AD(0), BE(1), C(2), F(3), Z(4)។
  • ខ្ញុំ 2: A, B, C, D, E, F, Z ។

លទ្ធផល៖ ម៉ាស៊ីនមានចំនួនរដ្ឋអប្បបរមារួចហើយ :-)

DFA ដែលអនុញ្ញាតឱ្យបញ្ចប់ភាសា

ក្បួនដោះស្រាយសម្រាប់ការសាងសង់ DFA ដែលទទួលយកការបំពេញបន្ថែមនៃភាសា L (L̅) មានពីរជំហាន៖

  • បង្កើត DFA ពេញលេញ
  • ការសាងសង់ automaton ដែលចង់បានពីវា។

តាមការពិត មិនមានអ្វីដូច DFA ពេញលេញនោះទេ។ នៅក្រោម DKA ពេញលេញ ខ្លះគ្រូបង្រៀនយល់ពី automaton នៅក្នុងតារាងផ្លាស់ប្តូរដែលមិនមានក្រឡាទទេ។ ទោះយ៉ាងណាក៏ដោយ យោងតាមនិយមន័យ DFA - δ: Q × Σ → Q - មិនអាចមានក្រឡាទទេក្នុងករណីណាក៏ដោយ។ ទោះជាយ៉ាងណាក៏ដោយ automaton "ជាមួយកោសិកាទទេ" បំពេញនិយមន័យនៃ NFA ។ នៅក្នុងដំណើរការនៃការដោះស្រាយ វាមិនមែនជារឿងចម្លែកទេក្នុងការទទួលបាន NFA បែបនេះ ដែលខ្វះតែការផ្លាស់ប្តូរមុន DFA ប៉ុណ្ណោះ។

ដើម្បីបំពេញបន្ថែមវាគ្រប់គ្រាន់ដើម្បីបន្ថែមរដ្ឋថ្មី។ Xនិង "ជំនួសឱ្យ" ការផ្លាស់ប្តូរដែលមិនមានស្រាប់ បន្ថែមការផ្លាស់ប្តូរទៅរដ្ឋថ្មីនេះ។ កុំភ្លេចបន្ថែមការផ្លាស់ប្តូរពី Xក្នុង X. វាងាយមើលឃើញថាកន្លែងដែល automaton ដើមមិនទទួលយកខ្សែសង្វាក់មួយចំនួនដោយសារតែអវត្តមាននៃការផ្លាស់ប្តូរ automaton ថ្មីនឹងចូលទៅក្នុងស្ថានភាព។ Xហើយព្យួរលើវា។ ដោយសាររដ្ឋថ្មីមិនមែនជារដ្ឋទទួលយក (ចុងក្រោយ) នោះ automaton ថ្មីក៏នឹងមិនទទួលយកខ្សែសង្វាក់នេះដែរ។

ឥឡូវនេះដើម្បីកសាង automaton ដែលចង់បានវាគ្រាន់តែជាការចាំបាច់ក្នុងការផ្លាស់ប្តូរតួនាទីនៃរដ្ឋទទួលយកនិងមិនទទួលយក។ និយាយម្យ៉ាងទៀត F" = Q \\ F ។

ការបង្កើតឧបករណ៍វិភាគ LL(k)

ការផ្លាស់ប្តូរវេយ្យាករណ៍

មិនមែនគ្រប់វេយ្យាករណ៍គឺ LL(k)-parsable។ វេយ្យាករណ៍​គ្មាន​បរិបទ​ជា​កម្មសិទ្ធិ​របស់​ថ្នាក់ LL(1) ប្រសិន​បើ​វា​មិន​មាន​ការ​ប៉ះទង្គិច FIRST-FIRST (ការ​ហៅ​ឡើង​វិញ​ខាង​ឆ្វេង​គឺ​ជា​ករណី​ពិសេស​នៃ​ជម្លោះ​បែប​នេះ) និង FIRST-FOLLOW ។

ពេលខ្លះវាអាចបំប្លែងវេយ្យាករណ៍ដែលមិនមែនជា LL(1) ដើម្បីឱ្យវាក្លាយជា LL(1)។ ការផ្លាស់ប្តូរមួយចំនួន (ច្បាស់ជាងនេះទៅទៀត ដែលត្រូវបានពិចារណាក្នុងវគ្គសិក្សា) ត្រូវបានផ្តល់ឱ្យខាងក្រោម។

ការ​ដក​ការ​លើក​ឡើង​ខាង​ឆ្វេង

ឧបមាថាយើងមានច្បាប់នៃទម្រង់ (តទៅនេះក្នុងផ្នែកនេះ អក្សរធំ - និមិត្តសញ្ញាមិនមែនស្ថានីយ, អក្សរ​តូច - ខ្សែសង្វាក់នៃតួអក្សរណាមួយ។):

  • ក → ក ក| ក ខ| … | ក k | ម | ន | … | z

វាមិនអាចទទួលយកបានចំពោះការវិភាគដែលមិនច្បាស់លាស់ទេ ដូច្នេះវាគួរតែត្រូវបានបំប្លែង។

វាងាយស្រួលក្នុងការបង្ហាញថាច្បាប់នេះគឺស្មើនឹងច្បាប់ទាំងពីរខាងក្រោម៖

  • ក → មខ | នខ | … | zខ
  • ខ → កខ | ខខ | … | kខ | ε

កត្តាកត្តាខាងឆ្វេង

ខ្លឹមសារនៃនីតិវិធីនេះគឺការលុបបំបាត់ភាពមិនច្បាស់លាស់នៅក្នុងជម្រើសនៃច្បាប់សម្រាប់តួអក្សរខាងឆ្វេង។ ដើម្បីធ្វើដូច្នេះ បុព្វបទខាងឆ្វេងទូទៅត្រូវបានរកឃើញ ហើយអ្វីដែលអាចធ្វើតាមវាត្រូវបានដកចេញនៅក្នុងច្បាប់ថ្មី (អក្សរតូច - ខ្សែសង្វាក់នៃតួអក្សរណាមួយ។)

ឧទាហរណ៍
  • ក → កគ | ក df | ក dg | ខ

បានបំប្លែងទៅជា

  • ក → កខ | ខ
  • ខ → គ | ឃ f | ឃ g

ដែលនៅក្នុងវេនក្លាយជា

  • ក → កខ | ខ
  • ខ → គ | ឃជាមួយ
  • គ → f | g

ឧទាហរណ៍នៃការបំប្លែងវេយ្យាករណ៍

ជី=((S,A,B),(a,b,c),P,S)

  • S →SAbB | ក
  • A→ab | អេ | ε
  • ខ → គ | ε

ការ​ដក​ពាក្យ​ដដែលៗ​ចេញ​សម្រាប់ S:

  • S → aS ១
  • S 1 → AbBS 1 | ε

កត្តា​ខាង​ឆ្វេង​សម្រាប់ A:

  • A → aA ១ | ε
  • ក 1 → ខ | ក

វេយ្យាករណ៍ចុងក្រោយ៖

  • S → aS ១
  • S 1 → AbBS 1 | ε
  • A → aA ១ | ε
  • ក 1 → ខ | ក
  • ខ → គ | ε

សាងសង់ FIRST និង FOLLOW

FIRST(α) ដែល α ∈ (N ∪ T)* គឺជាសំណុំនៃស្ថានីយដែល α អាចចាប់ផ្តើម។ ប្រសិនបើ α ⇒ ε នោះ ε ∈ FIRST (α) ។ ដូច្នោះហើយតម្លៃនៃ FOLLOW ( ក) សម្រាប់មិនមែនស្ថានីយ ក- ស្ថានីយជាច្រើនដែលអាចលេចឡើងភ្លាមៗបន្ទាប់ពី កនៅក្នុងទម្រង់មនោសញ្ចេតនាមួយចំនួន។ ប្រសិនបើ ក កអាចជាតួអក្សរដែលត្រឹមត្រូវបំផុតក្នុងទម្រង់មនោសញ្ចេតនាមួយចំនួន បន្ទាប់មកនិមិត្តសញ្ញា $ ចុងក្រោយក៏ជាកម្មសិទ្ធិរបស់ FOLLOW( ក)

ការគណនាដំបូង

សម្រាប់ស្ថានីយ
  • សម្រាប់ស្ថានីយណាមួយ។ x, x ∈ ធ, FIRST( x) = {x}
សម្រាប់មិនមែនស្ថានីយ
  • ប្រសិនបើ ក Xមិនមែនជាស្ថានីយ បន្ទាប់មកយើងដាក់ FIRST( X) = {∅}
  • ប្រសិនបើវេយ្យាករណ៍មានច្បាប់ X→ ε បន្ទាប់មកបន្ថែម ε ទៅ FIRST ( X)
  • សម្រាប់ស្ថានីយនីមួយៗ Xនិង​សម្រាប់​ក្បួន​សន្និដ្ឋាន​នីមួយៗ X → យ 1 …យ k បន្ថែម​ទៅ FIRST( X) សំណុំដំបូងនៃនិមិត្តសញ្ញាទាំងអស់នៅផ្នែកខាងស្តាំនៃច្បាប់រហូតដល់សញ្ញាទីមួយដែល ε មិនត្រូវបានយកមក រួមទាំង
សម្រាប់ខ្សែសង្វាក់
  • សម្រាប់ខ្សែអក្សរ X 1 …X k FIRST គឺ​ជា​ការ​រួបរួម​នៃ​តួអក្សរ FIRST ដែល​រួម​បញ្ចូល​ក្នុង​ខ្សែ​អក្សរ​រហូត​ដល់​អក្សរ​ទីមួយ​ដែល​មាន ε ∉ FIRST រួម​ទាំង​វា​ផង​ដែរ។
ឧទាហរណ៍
  • S → aS ១
  • S 1 → AbBS 1 | ε
  • A → aA ១ | ε
  • ក 1 → ខ | ក
  • ខ → គ | ε

ទីមួយមិនមែនស្ថានីយនៅក្នុងលំដាប់ដំណោះស្រាយភាពអាស្រ័យ៖

  • FIRST(S) = (a)
  • FIRST(A) = (a, ε)
  • FIRST(A 1) = (b, a)
  • FIRST(B) = (c, ε)
  • FIRST(S 1) = (a, b, ε)

FIRST សម្រាប់ច្បាប់សន្និដ្ឋាន៖

  • FIRST(aS 1) = (a)
  • FIRST(AbBS 1) = (a, b)
  • FIRST(ε) = (ε)
  • FIRST(aA 1) = (a)
  • FIRST(a) = (a)
  • FIRST(b) = (b)
  • FIRST(c) = (c)

អនុវត្តតាមការគណនា

ការគណនាអនុគមន៍ FOLLOW សម្រាប់តួអក្សរ X៖

  • អនុញ្ញាតឱ្យ FOLLOW(X) = (∅)
  • ប្រសិនបើ X គឺជា axiom វេយ្យាករណ៍ បន្ទាប់មកបន្ថែមសញ្ញាសម្គាល់ $ ទៅ FOLLOW
  • សម្រាប់ច្បាប់ទាំងអស់នៃទម្រង់ A → αXβ បន្ថែម FIRST(β)\(ε) ទៅ FOLLOW(X) (X អាចត្រូវបានអនុវត្តតាមតួអក្សរទាំងនោះដែលចាប់ផ្តើមដោយ β)
  • សម្រាប់ច្បាប់ទាំងអស់នៃទម្រង់ A → αX និង A → αXβ, ε ∈ FIRST(β) បន្ថែម FOLLOW(A) ទៅ FOLLOW(X) (នោះគឺ X អាចត្រូវបានអនុវត្តដោយតួអក្សរទាំងអស់ដែលអាចធ្វើតាម A ប្រសិនបើនៅក្នុង ក្បួនការសន្និដ្ឋាន X អាចនៅខាងស្តាំបំផុត)
  • ធ្វើម្តងទៀតនូវកថាខណ្ឌពីរមុន ដរាបណាអាចបន្ថែមតួអក្សរទៅសំណុំ
ឧទាហរណ៍
  • S → aS ១
  • S 1 → AbBS 1 | ε
  • A → aA ១ | ε
  • ក 1 → ខ | ក
  • ខ → គ | ε

លទ្ធផល៖

  • ធ្វើតាម(S) = ($)
  • FOLLOW(S 1) = ($) (S 1 គឺជាតួអក្សរខាងស្តាំបំផុតនៅក្នុងច្បាប់ S → aS 1)
  • FOLLOW(A) = (b) (A ក្នុងក្បួន S 1 → AbBS 1 ត្រូវបានធ្វើតាមដោយ ខ)
  • FOLLOW(A 1) = (b) (A 1 គឺជាតួអក្សរខាងស្តាំបំផុតក្នុងក្បួន A → aA 1 ដូច្នេះការបន្ថែម FOLLOW(A) ទៅ FOLLOW(A 1))
  • FOLLOW(B) = (a, b, $) (បន្ថែម FIRST(S 1)\(ε) (អនុវត្តតាមច្បាប់ S 1 → AbBS 1), FOLLOW(S 1) (ព្រោះមាន S 1 → ε))

ការចងក្រងតារាង

តុ មសម្រាប់គូដែលមិនមែនជាស្ថានីយ (ក្នុងក្រឡា ម[ក, ក]) បញ្ជាក់ច្បាប់ដែលពាក្យបញ្ចូលត្រូវតែកាត់បន្ថយ។ តារាងត្រូវបានបំពេញដូចខាងក្រោម៖ សម្រាប់ក្បួនការសន្និដ្ឋាននីមួយៗនៃវេយ្យាករណ៍ A → α (ដែល α ត្រូវបានយល់ថាជាខ្សែសង្វាក់នៅផ្នែកខាងស្តាំនៃច្បាប់) សកម្មភាពខាងក្រោមត្រូវបានអនុវត្ត៖

  1. សម្រាប់ស្ថានីយនីមួយៗ ក∈ FIRST(α) បន្ថែមច្បាប់ ក → α ទៅ ម[ក, ក]
  2. ប្រសិនបើ ε ∈ FIRST (α) បន្ទាប់មកសម្រាប់នីមួយៗ ខ∈ តាមដាន ( ក) បន្ថែម ក → α ទៅ ម[ក, ខ]
  3. ε ∈ FIRST(α) និង $∈ FOLLOW( ក), បន្ថែម ក → α ទៅ ម[ក, $]
  4. ក្រឡាទទេទាំងអស់គឺជាកំហុសនៅក្នុងពាក្យបញ្ចូល

ឧទាហរណ៍

បង្កើតតារាងសម្រាប់វេយ្យាករណ៍

  • S → aS ១
  • S 1 → AbBS 1 | ε
  • A → aA ១ | ε
  • ក 1 → ខ | ក
  • ខ → គ | ε

លទ្ធផល៖

កខគ $
ស S → aS ១ (ច្បាប់ទីមួយ ការសន្និដ្ឋាន S → aS 1 , a ∈ FIRST(aS 1)) កំហុស (ច្បាប់ទីបួន) កំហុស (ច្បាប់ទីបួន) កំហុស (ច្បាប់ទីបួន)
ស១ S 1 → AbBS ១ (ច្បាប់ទីមួយ លទ្ធផល S 1 → AbBS 1 , a ∈ FIRST (AbBS 1)) S 1 → AbBS ១ (ច្បាប់ទីមួយ លទ្ធផល S 1 → AbBS 1 , b ∈ FIRST (AbBS 1)) កំហុស (ច្បាប់ទីបួន) ស 1 → ε (ច្បាប់ទីបី ការសន្និដ្ឋាន S 1 → ε, ε ∈ FIRST(ε), $ ∈ FOLLOW(S 1))
ក A → aA ១ (ច្បាប់ទីមួយ លទ្ធផល A → aA 1 , a ∈ FIRST(aA 1)) អេ→ε (ក្បួនទីពីរ លទ្ធផល A 1 → ε, b ∈ ធ្វើតាម (A 1)) កំហុស (ច្បាប់ទីបួន) កំហុស (ច្បាប់ទីបួន)
ក ១ ក ១ → ក (ច្បាប់ទីមួយ លទ្ធផល A 1 → a, a ∈ FIRST(a)) ក 1 → ខ (ច្បាប់ទីមួយ លទ្ធផល A 1 → b, b ∈ FIRST(b)) កំហុស (ច្បាប់ទីបួន) កំហុស (ច្បាប់ទីបួន)
ខ ខ → អ៊ី ខ → អ៊ី (ក្បួនទីពីរ ការសន្និដ្ឋាន B → ε, a ∈ FOLLOW(B)) ខ → គ (ច្បាប់ទីមួយ លទ្ធផល B → c, c ∈ FIRST(c)) ខ → អ៊ី (ច្បាប់ទីបី ការសន្និដ្ឋាន B → ε, $ ∈ FOLLOW(B))

ការញែកខ្សែអក្សរ

ដំណើរការនៃការញែកខ្សែអក្សរគឺសាមញ្ញណាស់។ ខ្លឹមសាររបស់វាមានដូចខាងក្រោម៖ នៅជំហាននីមួយៗ និមិត្តសញ្ញាកំពូលត្រូវបានអាន v គខ្សែសង្វាក់បញ្ចូល។

  • ប្រសិនបើ ក v- និមិត្តសញ្ញាស្ថានីយ
    • ប្រសិនបើ ក vស្របពេលជាមួយ ជាមួយបន្ទាប់មកពួកគេទាំងពីរត្រូវបានបំផ្លាញ មានការផ្លាស់ប្តូរ
    • ប្រសិនបើ ក vមិនត្រូវគ្នាជាមួយ ជាមួយបន្ទាប់មក កំហុសញែកត្រូវបានផ្តល់សញ្ញា
  • ប្រសិនបើ ក v- និមិត្តសញ្ញាមិនមែនស្ថានីយ, គត្រឡប់​ទៅ​ដើម​បន្ទាត់​ជំនួស​វិញ។ vផ្នែកខាងស្តាំនៃច្បាប់ដែលត្រូវបានយកចេញពីក្រឡាតារាងត្រូវបានត្រលប់ទៅជង់វិញ។ ម[v, គ]

ដំណើរការបញ្ចប់នៅពេលដែលទាំងខ្សែអក្សរ និងជង់បានទៅដល់សញ្ញាសម្គាល់ចុង (#)។

ឧទាហរណ៍

តោះញែកខ្សែអក្សរ "aabbaabcb"៖

ជង់បន្ទាត់សកម្មភាព
ស# ក abbaabcb$S → aS ១
ក S1#ក abbaabcb$ផ្លាស់ប្តូរ
ស១# ក bbabcb$S 1 → AbBS ១
ក bbs 1#ក bbabcb$A → aA ១
ក A 1 bBS 1 #ក bbabcb$ផ្លាស់ប្តូរ
ក ១ bbs 1#ខ baabcb$ក 1 → ខ
ខ bbs 1#ខ baabcb$ផ្លាស់ប្តូរ
ខ B.S. 1#ខ aabcb$ផ្លាស់ប្តូរ
ខ S1#ក abcb$ខ → អ៊ី
ស១# ក abcb$S 1 → AbBS ១
ក bbs 1#ក abcb$A → aA ១
ក bbs 1#ក abcb$A → aA ១
ក A 1 bBS 1 #ក abcb$ផ្លាស់ប្តូរ
ក ១ bbs 1#ក bcb$ក ១ → ក
ក bbs 1#ក bcb$ផ្លាស់ប្តូរ
ខ B.S. 1#ខ cb$ផ្លាស់ប្តូរ
ខ S1#គ b$ខ → គ
គ S1#គ b$ផ្លាស់ប្តូរ
ស១# ខ$ S 1 → AbBS ១
ក bbs 1#ខ$ អេ→ε
ខ B.S. 1#ខ$ ផ្លាស់ប្តូរ
ខ S1#$ ខ → អ៊ី
ស១# $ ស 1 → ε
# $ រួចរាល់

បង្កើតឧបករណ៍វិភាគ LR(k)

ការគណនា k ជា LR(k)

មិនមានក្បួនដោះស្រាយដែលអនុញ្ញាតក្នុងករណីទូទៅដើម្បីគណនា k សម្រាប់វេយ្យាករណ៍តាមអំពើចិត្តនោះទេ។ ជាធម្មតាវាមានតម្លៃក្នុងការព្យាយាមបង្កើតឧបករណ៍ញែក LR (1) ។ ប្រសិនបើវាមានប្រតិបត្តិការច្រើនបំផុតមួយក្នុងមួយឈុត (Shift, Reduce ឬ Accept) នោះវេយ្យាករណ៍គឺ LR(0)។ ទោះយ៉ាងណាក៏ដោយ ប្រសិនបើការប៉ះទង្គិច និងការប៉ះទង្គិចកើតឡើងនៅពេលបង្កើតឧបករណ៍ញែក LR(1) នោះវេយ្យាករណ៍នេះមិនមែនជា LR(1) ហើយវាមានតម្លៃព្យាយាមបង្កើត LR(2)។ ប្រសិនបើវាបរាជ័យក្នុងការសាងសង់វាបន្ទាប់មក LR (3) ជាដើម។

ការបញ្ចប់វេយ្យាករណ៍

ចូរបន្ថែមច្បាប់ថ្មី S" → S ហើយធ្វើឱ្យ S" ជា axiom នៃវេយ្យាករណ៍។ ច្បាប់បន្ថែមនេះត្រូវបានទាមទារដើម្បីកំណត់នៅពេលដែលអ្នកវិភាគបញ្ចប់ ហើយខ្សែសង្វាក់បញ្ចូលត្រូវបានអនុញ្ញាត។ ការ​ចូល​រៀន​ធ្វើ​ឡើង​ប្រសិន​បើ​អាច​ធ្វើ​ការ​បង្រួប​បង្រួម​បាន​តាម​ច្បាប់ S → S”។

ការសាងសង់ប្រព័ន្ធ Canonical នៃសំណុំនៃ LR ដែលអាចទទួលយកបាន (1) - ស្ថានភាព

នៅពេលចាប់ផ្តើមមានសំណុំ I 0 ជាមួយនឹងការកំណត់រចនាសម្ព័ន្ធរបស់ឧបករណ៍វិភាគ S" → .S, $ ។ បន្ទាប់មកប្រតិបត្តិការបិទត្រូវបានអនុវត្តចំពោះការកំណត់រចនាសម្ព័ន្ធនេះរហូតដល់លទ្ធផលនៃកម្មវិធីរបស់វាមិនមានការកំណត់ថ្មីត្រូវបានបន្ថែមទេ។ ការផ្លាស់ប្តូរទៅសំណុំថ្មីត្រូវបានសាងសង់ដោយការផ្លាស់ប្តូរចំណុចដោយតួអក្សរមួយទៅខាងស្តាំ (ការលោតត្រូវបានធ្វើឡើងដោយតួអក្សរដែលបន្ទាប់ពីចំនុចមុនពេលលោត និងមុនវាបន្ទាប់ពីការលោត) និងការកំណត់ទាំងនោះដែលទទួលបានពីតួអក្សរដែលមានស្រាប់។ តាមរបៀបនេះត្រូវបានបន្ថែមទៅឈុតទាំងនេះ។ ប្រតិបត្តិការបិទក៏ត្រូវបានអនុវត្តចំពោះពួកវាដែរ ហើយដំណើរការទាំងមូលត្រូវបានធ្វើម្តងទៀតរហូតដល់មិនមានសំណុំថ្មីលេចឡើងទៀតទេ។

ឧទាហរណ៍

បង្កើតប្រព័ន្ធ Canonical នៃសំណុំ LR (1) ដែលអាចទទួលយកបានសម្រាប់វេយ្យាករណ៍ដែលបានបញ្ជាក់៖

  • ស" → ស
  • S → ABA
  • A → Aa | ε
  • ខ → cBc | ឃ

ការសម្រេចចិត្ត៖

  • យើងបង្កើតការបិទសម្រាប់ការកំណត់រចនាសម្ព័ន្ធ S" → .S, $:
    • S → .ABA,$
  • សម្រាប់ការកំណត់រចនាសម្ព័ន្ធលទ្ធផល (S → .ABA, $) យើងក៏បង្កើតការបិទផងដែរ៖
    • A → .Aa, គ
    • A → .Aa, ឃ
    • ក →., គ
    • ក →., ឃ
  • សម្រាប់​ការ​កំណត់​រចនាសម្ព័ន្ធ​លទ្ធផល (A → .Aa, c; A → .Aa, d) យើង​ក៏​បង្កើត​ការ​បិទ៖
    • A → .Aa, ក
    • ក → ., ក
  • មិនមានការកំណត់រចនាសម្ព័ន្ធទៀតទេនៅក្នុងរដ្ឋ I 0 អាចត្រូវបានសាងសង់ - ការបិទត្រូវបានសាងសង់
  • ពី I 0 អ្នកអាចធ្វើការផ្លាស់ប្តូរតាម S និង A ហើយទទួលបានសំណុំនៃការកំណត់ I 1 និង I 2 ដែលមានធាតុផ្សំដូចខាងក្រោមៈ
    • ខ្ញុំ 1 = (S" → S. , $)
    • I 2 = (S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, ក)
  • I 1 មិនតម្រូវឱ្យបិទទេ។
  • ចូរយើងបង្កើតការបិទ I 2៖
    • B → .cBc, ក
    • ខ → .cBc, $
    • B → .d, ក
    • ខ → .d, $
  • ឈុតផ្សេងទៀតទាំងអស់ត្រូវបានសាងសង់ស្រដៀងគ្នា។

ការកសាងតារាងញែក

ជំហានចុងក្រោយក្នុងការបង្កើត LR(1) parser គឺការកសាងតារាង សកម្មភាពនិង ទៅ. តុ សកម្មភាពបង្កើតឡើងសម្រាប់បញ្ចូលតួអក្សរខ្សែអក្សរ ពោលគឺសម្រាប់ស្ថានីយ និងសញ្ញាសម្គាល់ចុងបន្ទាត់ $, តារាង ទៅត្រូវបានបង្កើតឡើងសម្រាប់និមិត្តសញ្ញាវេយ្យាករណ៍ ពោលគឺសម្រាប់ស្ថានីយ និងមិនមែនស្ថានីយ។

ការកសាងតារាង Goto

តារាង Goto បង្ហាញស្ថានភាពដែលត្រូវទៅ នៅពេលដែលនិមិត្តសញ្ញាវេយ្យាករណ៍បន្ទាប់ត្រូវបានជួបប្រទះ។ ដូច្នេះប្រសិនបើនៅក្នុងប្រព័ន្ធ Canonical នៃសំណុំមានការផ្លាស់ប្តូរពី ខ្ញុំ iក្នុង ខ្ញុំ ជដោយនិមិត្តសញ្ញា A បន្ទាប់មកនៅក្នុង Goto ( ខ្ញុំ ខ្ញុំ, ក) យើងដាក់រដ្ឋ ខ្ញុំ j. បន្ទាប់ពីបំពេញតារាង យើងសន្មត់ថានៅក្នុងក្រឡាទទេទាំងអស់ Goto( ខ្ញុំ ខ្ញុំ, ក) = កំហុស

ការកសាងតារាងសកម្មភាព

  • ប្រសិនបើមានការផ្លាស់ប្តូរនៅលើស្ថានីយ a ពីរដ្ឋ I i ទៅរដ្ឋ I j នោះ Action(I i, a) = Shift(I j)
  • ប្រសិនបើ A ≠ S" ហើយមានការកំណត់ A → α។ , a បន្ទាប់មក Action(I i , a) = កាត់បន្ថយ(A → α)
  • សម្រាប់រដ្ឋ I i ដែលមានការកំណត់រចនាសម្ព័ន្ធ S" → S., $, Action(I i, $) = ទទួលយក
  • សម្រាប់ក្រឡាទទេទាំងអស់ Action(I i, a) = Error

ឧទាហរណ៍

បង្កើតតារាងសកម្មភាព និង Goto សម្រាប់វេយ្យាករណ៍

  • ស" → ស
  • S → ABA
  • A → Aa | ε
  • ខ → cBc | ឃ

ការសម្រេចចិត្ត៖

សកម្មភាពទៅ
កគឃ$ សស"កខកគឃ
ខ្ញុំ ០កាត់បន្ថយ (A → ε)កាត់បន្ថយ (A → ε)កាត់បន្ថយ (A → ε) ខ្ញុំ ១ ខ្ញុំ ២
ខ្ញុំ ១ ទទួលយក
ខ្ញុំ ២ប្ដូរ (I 6)ប្ដូរ (I 4)ប្ដូរ (I 5) ខ្ញុំ ៣ខ្ញុំ ៦ខ្ញុំ ៤ខ្ញុំ ៥
ខ្ញុំ ៣កាត់បន្ថយ (A → ε) កាត់បន្ថយ (A → ε) ខ្ញុំ ១៣
ខ្ញុំ ៤ ប្ដូរ (I 8)ប្ដូរ (I 9) ខ្ញុំ ៧ ខ្ញុំ ៨ខ្ញុំ ៩
ខ្ញុំ ៥កាត់បន្ថយ (B → ឃ) កាត់បន្ថយ (B → ឃ)
ខ្ញុំ ៦កាត់បន្ថយ (A → Aa)កាត់បន្ថយ (A → Aa)កាត់បន្ថយ (A → Aa)
ខ្ញុំ ៧ ប្ដូរ (I 10) ខ្ញុំ ១០
ខ្ញុំ ៨ ប្ដូរ (I 8)ប្ដូរ (I 9) ខ្ញុំ ១១ ខ្ញុំ ៨ខ្ញុំ ៩
ខ្ញុំ ៩ កាត់បន្ថយ (B → ឃ)
ខ្ញុំ ១០កាត់បន្ថយ (B → cBc) កាត់បន្ថយ (B → cBc)
ខ្ញុំ ១១ ប្ដូរ (I 12) ខ្ញុំ ១២
ខ្ញុំ ១២ កាត់បន្ថយ (B → cBc)
ខ្ញុំ ១៣ប្ដូរ (I 14) កាត់បន្ថយ (S → ABA) ខ្ញុំ ១៤
ខ្ញុំ ១៤កាត់បន្ថយ (A → Aa) កាត់បន្ថយ (A → Aa)

ការញែកខ្សែសង្វាក់

នៅជំហាននីមួយៗតួអក្សរកំពូលត្រូវបានអាន vពីជង់អ្នកវិភាគ ហើយយកតួអក្សរចុងក្រោយ គខ្សែសង្វាក់បញ្ចូល។

ប្រសិនបើនៅក្នុងតារាងនៃសកម្មភាពនៅចំណុចប្រសព្វ vនិង គទីតាំង៖

  • ប្ដូរ ( ខ្ញុំ k) បន្ទាប់មកដាក់លើជង់ ជាមួយហើយ​បន្ទាប់​មក ខ្ញុំ k. ឯណា គដកចេញពីខ្សែអក្សរ។
  • កាត់បន្ថយ ( ក → យូ) បន្ទាប់មកនិមិត្តសញ្ញាស្ថានីយ និងមិនមែនស្ថានីយទាំងអស់ដែលបង្កើតជាខ្សែសង្វាក់ត្រូវបានជម្រះចេញពីកំពូលនៃជង់ យូបន្ទាប់មករដ្ឋមើលទៅ ខ្ញុំ មនៅសល់នៅលើកំពូល។ នេះបើយោងតាមតារាងផ្លាស់ប្តូរនៅចំណុចប្រសព្វ ខ្ញុំ មនិង កស្វែងរករដ្ឋបន្ទាប់ ខ្ញុំ ស. បន្ទាប់ពីនោះ A ត្រូវបានរុញលើជង់ហើយបន្ទាប់មក ខ្ញុំ ស. បន្ទាត់នៅតែមិនផ្លាស់ប្តូរ។
  • យល់ព្រម បន្ទាប់មកការញែកត្រូវបានបញ្ចប់
  • ភាពទទេគឺជាកំហុសមួយ។

ឧទាហរណ៍

ចូរយើងបង្កើតការញែកខ្សែអក្សរ aaaccdcc៖

ជង់បន្ទាត់សកម្មភាព
ខ្ញុំ ០ ក aaccdcc$កាត់បន្ថយ (A → ε) ចូលទៅ I 2
ខ្ញុំ 0 អេ ខ្ញុំ ២ ក aaccdcc$ប្ដូរ (I 6)
I 0 A I 2 ក ខ្ញុំ ៦ ក accdcc$កាត់បន្ថយ (A → Aa) ចូលទៅ I 2
ខ្ញុំ 0 អេ ខ្ញុំ ២ ក accdcc$ប្ដូរ (I 6)
I 0 A I 2 ក ខ្ញុំ ៦ ក ccdcc$កាត់បន្ថយ (A → Aa) ចូលទៅ I 2
ខ្ញុំ 0 អេ ខ្ញុំ ២ ក ccdcc$ប្ដូរ (I 6)
I 0 A I 2 ក ខ្ញុំ ៦ គ cdcc$កាត់បន្ថយ (A → Aa) ចូលទៅ I 2
ខ្ញុំ 0 អេ ខ្ញុំ ២ គ cdcc$ប្ដូរ (I 4)
I 0 A I 2 s ខ្ញុំ ៤ គ dcc$ប្ដូរ (I 8)
I 0 A I 2 គ I 4 គ ខ្ញុំ ៨ ឃ cc$ប្ដូរ (I 9)
I 0 A I 2 c I 4 c I 8 ឃ ខ្ញុំ ៩ គ c$កាត់បន្ថយ (B → d) ចូលទៅ I 11
I 0 A I 2 c I 4 c I 8 B ខ្ញុំ ១១ គ c$ប្ដូរ (I 12)
I 0 A I 2 c I 4 c I 8 B I 11 គ ខ្ញុំ ១២ គ$ កាត់បន្ថយ (B → cBc) ចូលទៅ I 7
I 0 A I 2 C I 4 B ខ្ញុំ ៧ គ$ ប្ដូរ (I 10)
I 0 A I 2 c I 4 B I 7 គ ខ្ញុំ ១០ $ កាត់បន្ថយ (B → cBc) ចូលទៅ I 3
I 0 A I 2 B ខ្ញុំ ៣ $ កាត់បន្ថយ (A → ε) ចូលទៅ I 13
I 0 A I 2 B I 3 A ខ្ញុំ ១៣ $ កាត់បន្ថយ (S → ABA) ចូលទៅ I 1
ខ្ញុំ 0 ស ខ្ញុំ ១ $ ទទួលយក

ការបកប្រែកន្សោមនព្វន្ធ (ក្បួនដោះស្រាយ Seti-Ullman)

ចំណាំ។កូដ​នេះ​ត្រូវ​បាន​បង្កើត​ឡើង​ដោយ​ស្ទីល doggy Motorola-like, i.e.

Op Arg1, Arg2

តំណាង​ឱ្យ

Arg2 = Arg1 Op Arg2

សាងសង់ដើមឈើ

មែកធាងត្រូវបានសាងសង់ជាធម្មតាសម្រាប់កន្សោមនព្វន្ធ៖ នៅឫស ប្រតិបត្តិការដែលមានអាទិភាពទាបបំផុត បន្តដោយប្រតិបត្តិការដែលមានអាទិភាពខ្ពស់ជាងបន្តិច ហើយដូច្នេះនៅលើ។ វង់ក្រចកមានអាទិភាពខ្ពស់បំផុត។ ប្រសិនបើមានប្រតិបត្តិការជាច្រើនដែលមានអាទិភាពដូចគ្នា - a op b op c នោះមែកធាងត្រូវបានសាងសង់ដូចជាសម្រាប់កន្សោម (a op b) op c ។

ឧទាហរណ៍

បង្កើតមែកធាងសម្រាប់កន្សោម a + b / (d + a − b × c / d − e) + c × d

ការសម្រេចចិត្ត៖យើងសរសេរកន្សោមក្នុងទម្រង់

((a) + ((b) / (((((d) + (a)) − ((b) × (c)) / (d)) − (e)))) + ((c) × ( ឃ))

បន្ទាប់មកនៅឫសនៃមែកធាងរងនីមួយៗនឹងមានប្រតិបត្តិការមួយ ហើយកន្សោមក្នុងតង្កៀបនៅខាងឆ្វេង និងខាងស្តាំរបស់វានឹងក្លាយជាមែកធាងរងរបស់វា។ ឧទាហរណ៍ សម្រាប់កន្សោមរង ((ខ) × (គ)) / (ឃ) ប្រតិបត្តិការ “/” នឹងស្ថិតនៅឫសនៃអនុមែកធាងដែលត្រូវគ្នា ហើយកន្សោមរង ((ខ) × (គ)) និង (ឃ) ) នឹងក្លាយជាដើមឈើតូចៗរបស់វា។

ប្លង់ដើមឈើ (ការគណនាចំនួនចុះឈ្មោះ)

  • ប្រសិនបើចំនុចកំពូលគឺជាស្លឹកខាងឆ្វេង (នោះគឺជាអថេរ) នោះយើងសម្គាល់វាដោយសូន្យ។
  • ប្រសិនបើ vertex គឺជាស្លឹកត្រឹមត្រូវ នោះយើងសម្គាល់វាដោយមួយ។
  • ប្រសិនបើយើងសម្គាល់មែកធាងរងទាំងពីរសម្រាប់ចំណុចកំពូលមួយចំនួន នោះយើងសម្គាល់វាដូចខាងក្រោម៖
    • ប្រសិនបើអនុមែកធាងខាងឆ្វេង និងស្តាំត្រូវបានដាក់ស្លាកដោយលេខផ្សេងគ្នា បន្ទាប់មកជ្រើសរើសធំបំផុតនៃពួកវា
    • ប្រសិនបើដើមឈើរងខាងឆ្វេង និងស្តាំត្រូវបានដាក់ស្លាកលេខដូចគ្នានោះ មែកធាងរងនេះត្រូវបានផ្តល់លេខមួយដែលធំជាងមួយដែលដាក់ស្លាកដើមឈើរង។
ការសម្គាល់ស្លឹកប្លង់ដើមឈើដែលមានដើមឈើរងដូចគ្នាបេះបិទមែកធាងរងខាងឆ្វេងត្រូវបានដាក់ស្លាកលេខធំមែកធាងរងខាងស្តាំត្រូវបានដាក់ស្លាកដោយលេខធំ
ត្រឹមត្រូវ - ដូចគ្នាដូចជាបុព្វបុរស។
  • ប្រសិនបើស្លាក ឆ្វេងកូនចៅ ច្រើនទៀតស្លាក ត្រឹមត្រូវ។បន្ទាប់មក ត្រឹមត្រូវ។កុមារត្រូវបានចាត់តាំងឱ្យចុះឈ្មោះ មួយទៀតជាងបុព្វបុរស និង ឆ្វេង - ដូចគ្នាដូចជាបុព្វបុរស។

    • កូដត្រូវបានបង្កើតឡើងដោយឆ្លងកាត់ដើមឈើពីក្រោមទៅកំពូលដូចខាងក្រោម:

    1. គ្មានលេខកូដត្រូវបានបង្កើតសម្រាប់ចំនុចកំពូលដែលមានស្លាកលេខ 0

    2. ប្រសិនបើផ្នែកខាងលើជាសន្លឹក X ដែលមានស្លាកលេខ 1 ហើយចុះឈ្មោះ R ខ្ញុំបន្ទាប់មកលេខកូដ

    ផ្លាស់ទី X, រី

    3. ប្រសិនបើផ្នែកខាងលើគឺខាងក្នុងជាមួយនឹងការចុះឈ្មោះ R ខ្ញុំហើយកូនខាងឆ្វេងរបស់វាគឺសន្លឹក X ដែលមានស្លាកលេខ 0 បន្ទាប់មកវាត្រូវគ្នានឹងលេខកូដ

    <Код правого поддерева>OpX, រី

    4. ប្រសិនបើ subtrees នៃ vertex ជាមួយ register R ខ្ញុំ- មិនទុក ហើយស្លាកនៃចំនុចកំពូលខាងស្តាំគឺធំជាង ឬស្មើនឹងស្លាករបស់ខាងឆ្វេង (ដែលមានបញ្ជីឈ្មោះ Rj, j = i + 1) បន្ទាប់មកលេខកូដត្រូវគ្នានឹងចំនុចកំពូល។

    <Код ត្រឹមត្រូវ។មែកធាងរង ><Код ឆ្វេងដើមឈើរង > Op Rj, Ri

    5. ប្រសិនបើ subtrees នៃ vertex ជាមួយ register R ខ្ញុំ- មិនទុក និងស្លាកសញ្ញានៃកំពូលខាងស្តាំ (សម្រាប់ការចុះឈ្មោះ Rj, j = i + 1) តិចជាងស្លាកសញ្ញាខាងឆ្វេង បន្ទាប់មកលេខកូដត្រូវគ្នានឹងចំនុចកំពូល។

    ការចែកចាយការចុះឈ្មោះត្រូវបានបង្ហាញនៅក្នុងក្រាហ្វនៅខាងស្តាំ។ លេខកូដដែលបានបង្កើត៖

    ផ្លាស់ទី d, R0 ;R0 = d ផ្លាស់ទី c, R1 ;R1 = c MUL b, R1 ;R1 = (b × c) DIV R1, R0 ;R0 = (b × c) / d ផ្លាស់ទី a, R1 ;R1 = a បន្ថែម d, R1 ;R1 = a + d SUB R1, R0 ;R0 = (a + d) − ((b × c) / d) ផ្លាស់ទី e, R1 ;R1 = e SUB R0, R1 ;R1 = ((a + ឃ) − ((b × គ) / ឃ)) − អ៊ី ផ្លាស់ទី R1, R0; R0 = ((a + d) − ((b × c) / d)) − e DIV b, R0 ;R0 = b / (((a + d) − (( (b × c) / d))) − e) បន្ថែម a, R0 ;R0 = a + (b / (((a + d) − ((b × c) / d )) − e)) ផ្លាស់ទី d, R1 ;R1 = d MUL c, R1 ;R1 = c×d ADD R0, R1 ;R1 = (a + (b / (((a + d)) − ((b × c ) / d)) − e))) + (c × d) MOVE R1, R0;R0 = (a + (b / (((a + d) − ((b × c) / d))) − e) )) + (គ × ឃ)

    ការបកប្រែកន្សោមឡូជីខល

    ផ្នែកនេះបង្ហាញពីរបៀបបង្កើតកូដសម្រាប់ការវាយតម្លៃខ្ជិលនៃកន្សោមប៊ូលីន។ ជាលទ្ធផលនៃក្បួនដោះស្រាយ បំណែកនៃកូដត្រូវបានទទួល ដែលដោយប្រើប្រតិបត្តិការ TST, BNE, BEQ គណនាកន្សោមឡូជីខលដោយប្តូរទៅស្លាកមួយក្នុងចំណោមស្លាក: TRUELAB ឬ FALSELAB ។

    សាងសង់ដើមឈើ

    មែកធាងនៃកន្សោមឡូជីខលឆ្លុះបញ្ចាំងពីលំដាប់ដែលវាត្រូវបានវាយតម្លៃយោងទៅតាមអាទិភាពនៃប្រតិបត្តិការ ពោលគឺដើម្បីវាយតម្លៃតម្លៃនៃថ្នាំងមែកធាង (ដែលជាប្រតិបត្តិការលើ operands ពីរដែលជា subtrees នៃ node) យើងត្រូវ ដំបូងគណនាតម្លៃនៃដើមឈើរងរបស់វា។

    អាទិភាពប្រតិបត្តិការ៖ប្រតិបត្តិករ NOT មានអាទិភាពខ្ពស់បំផុត តាមពីក្រោយដោយ AND ហើយបន្ទាប់មក OR ។ ប្រសិនបើប្រតិបត្តិការឡូជីខលផ្សេងទៀតត្រូវបានប្រើនៅក្នុងកន្សោម នោះពួកគេត្រូវតែបង្ហាញតាមរយៈវិធីទាំងបីនេះតាមវិធីជាក់លាក់មួយ (ជាធម្មតាមិនមានប្រតិបត្តិការផ្សេងទៀតទេ ហើយការបំប្លែងកន្សោមមិនត្រូវបានទាមទារ)។ សមាគមសម្រាប់ប្រតិបត្តិការដែលមានអាទិភាពដូចគ្នាគឺពីឆ្វេងទៅស្តាំ ពោលគឺ A និង B និង C ត្រូវបានចាត់ទុកជា (A និង B) និង C

    ឧទាហរណ៍

    សាងសង់មែកធាងសម្រាប់កន្សោមឡូជីខលមិនមែន A ឬ B និង C និង (B ឬមិនមែន C) ។

    ការសម្រេចចិត្ត៖សូមមើលដ្យាក្រាមនៅខាងស្តាំ។

    សម្រាប់កំពូលនីមួយៗនៃមែកធាង គុណលក្ខណៈ 4 ត្រូវបានគណនា៖

    • លេខថ្នាំង
    • ស្លាកដែលត្រូវលោតទៅ ប្រសិនបើកន្សោមក្នុងថ្នាំងមិនពិត (ស្លាកក្លែងក្លាយ fl)
    • ស្លាកដែលត្រូវលោតទៅប្រសិនបើកន្សោមនៅក្នុងថ្នាំងគឺពិត (ស្លាកពិត, tl)
    • ស្លាកសញ្ញា (សញ្ញា) (សម្រាប់ព័ត៌មានលម្អិត សូមមើលខាងក្រោម)

    ចំនុចបញ្ឈរត្រូវបានរាប់តាមលំដាប់ចៃដន្យ លក្ខខណ្ឌតែមួយគត់គឺភាពប្លែកនៃលេខថ្នាំង។

    ប្លង់ដើមឈើត្រូវបានធ្វើដូចខាងក្រោមៈ

    • fl បញ្ជាក់ចំនួននៃ vertex ដែលការផ្លាស់ប្តូរត្រូវបានធ្វើឡើង ឬ falselab ប្រសិនបើ vertex នេះមិនពិត
    • tl បង្ហាញពីចំនួននៃ vertex ដែលការផ្លាស់ប្តូរត្រូវបានធ្វើឡើង ឬ truelab ប្រសិនបើ vertex នេះគឺពិត

    សញ្ញាបញ្ជាក់ក្នុងករណីដែលការវាយតម្លៃនៃអនុមែកធាងបច្ចុប្បន្នអាចត្រូវបានបញ្ចប់។

    សម្រាប់ឫសដើមឈើ fl=falselab, tl=truelab, sign=false ។

    ដូចនេះ៖

    ឧទាហរណ៍

    សម្គាល់មែកធាងដែលបានសាងសង់សម្រាប់កន្សោមឡូជីខលមិនមែន A ឬ B និង C និង (B ឬមិនមែន C) ។

    ការបង្កើតកូដ

    ពាក្យបញ្ជាម៉ាស៊ីនប្រើក្នុងកូដដែលបានបង្កើត៖

    • TST - ពិនិត្យមើលអំណះអំណាងសម្រាប់ការពិត និងកំណត់ទង់ ប្រសិនបើអាគុយម៉ង់មិនពិត
    • BNE - លោតទៅស្លាកប្រសិនបើទង់មិនត្រូវបានកំណត់ ពោលគឺលក្ខខណ្ឌដែលបានពិនិត្យជាមួយ TST ពិត
    • BEQ - លោតលើស្លាកប្រសិនបើទង់ត្រូវបានកំណត់ ពោលគឺលក្ខខណ្ឌដែលបានពិនិត្យជាមួយ TST មិនពិត

    កូដត្រូវបានបង្កើតឡើងដូចខាងក្រោមៈ

    • ដើមឈើត្រូវឆ្លងកាត់ពីឫស សម្រាប់ AND និង OR មែកធាងរងខាងឆ្វេងត្រូវឆ្លងកាត់មុន បន្ទាប់មកខាងស្តាំ
    • សម្រាប់ vertex នីមួយៗបានឆ្លងកាត់ លេខរបស់វា (ស្លាក) ត្រូវបានបោះពុម្ព
    • សម្រាប់សន្លឹក A (number, tl, fl, sign) TST A ត្រូវបានបោះពុម្ព
      • ប្រសិនបើសញ្ញា == ពិត BNE tl ត្រូវបានបោះពុម្ព
      • ប្រសិនបើសញ្ញា == មិនពិត BEQ fl ត្រូវបានបោះពុម្ព

    ឧទាហរណ៍

    សម្រាប់កន្សោមខាងលើ កូដខាងក្រោមនឹងត្រូវបានបង្កើត៖

    1:2:4: TST A BEQ TRUELAB 3:5:7: TST B BEQ FALSELAB 8: TST C BEQ FALSELAB 6:9: TST B BNE TRUELAB 10:11: TST C BNE FALSELAB TRUELAB: FALSELAB:

    វិធីសាស្រ្តផ្គូផ្គងគំរូ

    គំនិតនៃវិធីសាស្រ្តគឺថាសម្រាប់ផ្នែកដូចគ្នានៃកម្មវិធីកូដអាចត្រូវបានបង្កើតតាមវិធីផ្សេងគ្នាហើយជាលទ្ធផលការបង្កើនប្រសិទ្ធភាពអាចត្រូវបានសម្រេចសម្រាប់ប៉ារ៉ាម៉ែត្រមួយឬផ្សេងទៀត។

    ការបង្កើតបញ្ហា

    មានគំរូជាច្រើន ដែលនីមួយៗត្រូវបានកំណត់ដោយបំណែកនៃតំណាងកម្រិតមធ្យម ដែលវាអាចអនុវត្តបាន ទម្ងន់ និងលេខកូដដែលបានបង្កើត។ មានមែកធាងតំណាងកម្រិតមធ្យម ដែលជាបំណែកនៃកម្មវិធីដែលវាចាំបាច់ដើម្បីបង្កើតកូដ។ គោលដៅគឺដើម្បីសាងសង់គម្របដើមឈើតំណាងកម្រិតមធ្យមជាមួយនឹងគំរូដើម្បីឱ្យទម្ងន់សរុបនៃគំរូមានតិចតួចបំផុត។

    លំនាំគឺជាការណែនាំអំពីការជួបប្រជុំគ្នា និងដើមឈើញែកដែលត្រូវគ្នានឹងពួកគេ។ សម្រាប់គំរូនីមួយៗ ពេលវេលាប្រតិបត្តិរបស់វា (ជារង្វង់) ត្រូវបានគេស្គាល់។ ដោយមានជំនួយរបស់ពួកគេ យើងនឹងបង្កើតកូដល្អបំផុត (ក្នុងលក្ខខណ្ឌនៃពេលវេលាប្រតិបត្តិ)។

    ឧទាហរណ៍គំរូ

    ការកសាងតំណាងកម្រិតមធ្យម

    ដំបូង យើងបង្កើតមែកធាងញែកសម្រាប់កន្សោមទាំងមូល។

    ការកសាងការគ្របដណ្តប់

    ឥឡូវនេះសម្រាប់ចំនុចកំពូលនីមួយៗ (យើងឆ្លងកាត់ពួកវាតាមលំដាប់លំដោយពីស្លឹកទៅឫស) យើងនឹងបង្កើតកូដល្អបំផុតសម្រាប់មែកធាងរងរបស់វា។ ដើម្បីធ្វើដូចនេះយើងគ្រាន់តែឆ្លងកាត់គំរូទាំងអស់ដែលអាចអនុវត្តបាននៅចំនុចកំពូលដែលបានផ្តល់ឱ្យ។ ពេលវេលាប្រតិបត្តិនៅពេលប្រើលំនាំជាក់លាក់មួយនឹងជាផលបូកនៃពេលវេលាដែលវាត្រូវការដើម្បីវាយតម្លៃអាគុយម៉ង់របស់វា (ហើយយើងដឹងពីលេខកូដល្អបំផុតសម្រាប់ការគណនាពួកវារួចហើយ អរគុណចំពោះលំដាប់ឆ្លងកាត់ដើមឈើ) និងពេលវេលាប្រតិបត្តិនៃគំរូខ្លួនឯង។ ក្នុងចំណោមជម្រើសទាំងអស់ដែលទទួលបាន យើងជ្រើសរើសយកមួយណាដែលល្អបំផុត - វានឹងក្លាយជាកូដដ៏ល្អបំផុតសម្រាប់អនុមែកធាងនៃចំនុចកំពូលនេះ។ នៅឫសនៃមែកធាង យើងទទួលបានកូដល្អបំផុតសម្រាប់កន្សោមទាំងមូល។

    ការបង្កើតកូដ

    វាមិនចាំបាច់ក្នុងការសរសេរកូដសម្រាប់បញ្ឈរទាំងអស់នោះទេ - វាគ្រប់គ្រាន់ក្នុងការសរសេរពេលវេលាដែលត្រូវការអប្បបរមា និងគំរូដែលអ្នកត្រូវការប្រើ។ អ្វីៗផ្សេងទៀតពីនេះត្រូវបានស្ដារឡើងវិញយ៉ាងងាយស្រួល។

    យើងមានចំនួនចុះឈ្មោះគ្មានកំណត់ក្នុងបញ្ហាទាំងនេះ ដូច្នេះរាល់ពេលដែលអ្នកអាចប្រើថ្មីមួយ។

    ការសាងសង់ RV យោងទៅតាម DKA

    ការស្ថាបនា NFA យោងទៅតាមវេយ្យាករណ៍លីនេអ៊ែរស្តាំ

    ការបញ្ចូលវេយ្យាករណ៍

    ដើម្បីបំប្លែង COP-វេយ្យាករណ៍តាមអំពើចិត្តទៅជាទម្រង់កាត់បន្ថយ អ្នកត្រូវតែអនុវត្តជំហានខាងក្រោម៖

    • លុបតួអក្សរដែលមិនចេះរីងស្ងួតទាំងអស់;
    • លុបតួអក្សរដែលមិនអាចទៅដល់បានទាំងអស់;

    ការដកតួអក្សរដែលគ្មានប្រយោជន៍ចេញ

    ច្រកចូល៖ COP-វេយ្យាករណ៍ G = (T, N, P, S) ។

    លទ្ធផល៖វេយ្យាករណ៍ COP-G' = (T, N', P', S) ដែលមិនមាននិមិត្តសញ្ញាមិនច្បាស់លាស់ ដែល L(G) = L(G')។

    វិធីសាស្រ្ត៖

    សំណុំបង្កើតឡើងវិញ N 0 , N 1 , ...

    1. N 0 = ∅, i = 1 ។
    2. N i = (A | (A → α) ∈ P និង α ∈ (N i − 1 ∪ T)*) ∪ N i-1 ។
    3. ប្រសិនបើ N i ≠ N i - 1 បន្ទាប់មក i = i + 1 ហើយទៅជំហានទី 2 បើមិនដូច្នេះទេ N ' = N i ; P' មានច្បាប់នៃសំណុំ P ដែលមានតែនិមិត្តសញ្ញាពី N ' ∪ T; G' = (T, N', P', S) ។

    និយមន័យ៖និមិត្តសញ្ញា x ∈ (T ∪ N) ត្រូវបានគេនិយាយថាមិនអាចទៅដល់ក្នុងវេយ្យាករណ៍ G = (T, N, P, S) ប្រសិនបើវាមិនបង្ហាញក្នុងទម្រង់មនោសញ្ចេតនាណាមួយនៃវេយ្យាករណ៍នេះ។

    ឧទាហរណ៍

    លុបតួអក្សរដែលគ្មានប្រយោជន៍ចេញពីវេយ្យាករណ៍ G((A, B, C, D, E, F, S), (a, b, c, d, e, f, g), P, S)

    • S → AcDe | CaDbCe | សាកា | aCb | dFg
    • A → SeAd | cSA
    • B → CaBd | aDBc | BSC | bfg
    • C → Ebd | សែប | aAc | cfF
    • ឃ → fCE | ac | dEdAS | ε
    • អ៊ី → ESacD | អេក | អ៊ីអេហ្វ

    ការសម្រេចចិត្ត

    • N 0 = ∅
    • N 1 = (B (B → bfg), D (D → ac), E (E → aec))
    • N 2 = (B, D, E, C (C → Ebd))
    • N 3 = (B, D, E, C, S (S → aCb))
    • N 4 \u003d (B, D, E, C, S) \u003d N 3

    G"((B,C,D,E,S), (a, b, c, d, e, f, g), P", S)

    • S → CaDbCe | សាកា | aCb
    • B → CaBd | aDBc | BSC | bfg
    • C → Ebd | សេប
    • ឃ → fCE | ac | ε
    • អ៊ី → ESacD | អេក

    ការដកតួអក្សរដែលមិនអាចទាក់ទងបាន។

    ច្រកចូល៖វេយ្យាករណ៍ COP G = (T, N, P, S)

    លទ្ធផល៖ COP-វេយ្យាករណ៍ G' = (T', N', P', S) ដែលមិនមាននិមិត្តសញ្ញាដែលមិនអាចទៅដល់បាន ដែល L(G) = L(G')។

    វិធីសាស្រ្ត៖

    1. V 0 = (S); ខ្ញុំ = 1 ។
    2. V i = (x | x ∈ (T ∪ N), (A → αxβ) ∈ P និង A ∈ V i − 1 ) ∪ V i-1 ។
    3. ប្រសិនបើ V i ≠ V i - 1 បន្ទាប់មក i = i + 1 ហើយទៅជំហានទី 2 បើមិនដូច្នេះទេ N ' = V i ∩ N; T ' = V i ∩ T ; P' មានច្បាប់នៃសំណុំ P ដែលមាននិមិត្តសញ្ញាតែពី V i ; G' = (T', N', P', S) ។

    និយមន័យ៖ COP-វេយ្យាករណ៍ G ត្រូវបានគេនិយាយថាត្រូវបានកាត់បន្ថយប្រសិនបើវាមិនមាននិមិត្តសញ្ញាដែលមិនអាចសម្រេចបាន និងគ្មានមេរោគ។

    ឧទាហរណ៍

    លុបតួអក្សរដែលមិនអាចទៅដល់បានពីវេយ្យាករណ៍ G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

    • S → CaDbCe | សាកា | aCb
    • B → CaBd | aDBc | BSC | bfg
    • C → Ebd | សេប
    • ឃ → fCE | ac | ε
    • អ៊ី → ESacD | អេក

    ការសម្រេចចិត្ត

    • V 0 = (S)
    • V 1 = (S, C (S → CaDbCe), D (S → CaDbCe), a (S → CaDbCe), b (S → CaDbCe), e (S → CaDbCe))
    • V 2 = (S, C, D, a, b, e, E (C → Ebd), d (C → Ebd), f (D → fCE))
    • V 3 = (S, C, D, E, a, b, d, e, f, c (E → ESacD))
    • V 4 \u003d (S, C, D, E, a, b, d, e, f, c) \u003d V 3

    G""((C,D,E,S), (a, b, c, d, e, f), P"", S)

    • S → CaDbCe | សាកា | aCb
    • C → Ebd | សេប
    • ឃ → fCE | ac | ε
    • អ៊ី → ESacD | អេក
    ដោយចំនួនសរុបនៃតួអក្សរនៃអក្ខរក្រមនៃនិមិត្តសញ្ញានិងសញ្ញានៃប្រតិបត្តិការនិងតង្កៀបនៅក្នុងកំណត់ត្រា r ។

    មូលដ្ឋាន. Automata សម្រាប់កន្សោមប្រវែង 1៖ ហើយត្រូវបានបង្ហាញក្នុងរូបខាងក្រោម។


    អង្ករ។ ៥.១.

    ចំណាំថា automata ទាំងបីនេះនីមួយៗមាន សំណុំនៃរដ្ឋចុងក្រោយរួមមានរដ្ឋមួយ។

    ជំហាន​បញ្ចូល​. ឥឡូវនេះ ចូរយើងសន្មតថាសម្រាប់នីមួយៗ កន្សោមធម្មតា។ប្រវែង<= k построен соответствующий НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное កន្សោមធម្មតា។ r នៃប្រវែង k+1 ។ អាស្រ័យលើប្រតិបត្តិការចុងក្រោយ វាអាចមានទម្រង់មួយក្នុងចំណោមទម្រង់បី៖ (r 1 + r 2), (r 1 r 2) ឬ (r 1) * ។ អនុញ្ញាតឱ្យ NFAs ទទួលស្គាល់ភាសា L r1 និង L r2 រៀងគ្នា។ ដោយមិនបាត់បង់ភាពទូទៅ យើងនឹងសន្មត់ថាពួកគេមានរដ្ឋផ្សេងៗគ្នា៖ .

    បន្ទាប់មក NFA ដែលដ្យាក្រាមត្រូវបានបង្ហាញក្នុងរូប។ 5.2 ស្គាល់ភាសា។


    អង្ករ។ ៥.២.

    ម៉ាស៊ីននេះមាន សំណុំនៃរដ្ឋដែលជាកន្លែងដែល q 0 គឺជាស្ថានភាពដំបូងថ្មី q f គឺជាស្ថានភាពចុងក្រោយថ្មី (ប្លែក!) ហើយកម្មវិធីរួមមានកម្មវិធី automaton M 1 និង M 2 និងពាក្យបញ្ជាផ្លាស់ប្តូរថ្មីចំនួនបួន៖ . ជាក់ស្តែង ភាសាដែលទទួលស្គាល់ដោយ NFA M រួមមានពាក្យទាំងអស់ពី L ( M 1 ) និងមកពី L ( M 2 ) ។ ម៉្យាងវិញទៀត ពាក្យនីមួយៗយក q 0 ទៅ q f ហើយបន្ទាប់ពីជំហានដំបូង ផ្លូវដែលនាំវាឆ្លងកាត់ q 0 1 ឬ q 0 2 ។ ដោយសាររដ្ឋ M 1 និង M 2 មិនប្រសព្វគ្នា នោះក្នុងករណីដំបូង ផ្លូវនេះអាចទៅដល់ q f បានតែដោយ -transition ពី q f 1 ហើយបន្ទាប់មក . ដូចគ្នានេះដែរនៅក្នុងករណីទីពីរ។

    សម្រាប់ការបញ្ចេញមតិ ដ្យាក្រាមនៃ NFA ដែលទទួលស្គាល់ភាសា L r ត្រូវបានបង្ហាញក្នុងរូបខាងក្រោម។


    អង្ករ។ ៥.៣.

    ម៉ាស៊ីននេះមាន សំណុំនៃរដ្ឋ , រដ្ឋដំបូង q 0 = q 0 1 , ស្ថានភាពចុងក្រោយ q f = q f 2 ហើយកម្មវិធីនេះរួមបញ្ចូលកម្មវិធី automaton M 1 និង M 2 និងការណែនាំថ្មីមួយទៀត - ការផ្លាស់ប្តូរពីរដ្ឋចុងក្រោយ M 1 ទៅរដ្ឋដំបូង M 2 , i.e. . នៅទីនេះវាក៏ច្បាស់ដែរថា ផ្លូវណាមួយពី q 0 = q 0 1 ទៅ q f = q f 2 ឆ្លងកាត់ -transition ពី q f 1 ទៅ q 0 2 ។ ដូច្នេះ​រាល់​ពាក្យ​ដែល​អនុញ្ញាត​ដោយ M គឺ​ជា​ការ​ផ្សំ​នៃ​ពាក្យ​មួយ​ចំនួន​មក​ពី L M1) ជាមួយ​នឹង​ពាក្យ​ខ្លះ​មក​ពី L M2) ហើយ​ការ​ភ្ជាប់​ពាក្យ​ទាំង​នោះ​ត្រូវ​បាន​អនុញ្ញាត។ ដូច្នេះ NFA M ទទួលស្គាល់ភាសា។

    អនុញ្ញាតឱ្យ r = r 1 * ។ ដ្យាក្រាមនៃ NFA ដែលទទួលស្គាល់ភាសា L r = L r1* = L M1 * ត្រូវបានបង្ហាញក្នុងរូបភព។ ៥.៣.


    អង្ករ។ ៥.៣.

    ម៉ាស៊ីននេះមាន សំណុំនៃរដ្ឋដែលជាកន្លែងដែល q 0 គឺជាស្ថានភាពដំបូងថ្មី q f គឺជាស្ថានភាពចុងក្រោយថ្មី (តែមួយគត់!) ហើយកម្មវិធីនេះរួមបញ្ចូលកម្មវិធី automaton M 1 និងពាក្យបញ្ជាផ្លាស់ប្តូរថ្មីចំនួនបួន៖ . ជាក់ស្តែង, ។ សម្រាប់ពាក្យមិនទទេ w តាមនិយមន័យនៃពាក្យដដែលៗ សម្រាប់ k ខ្លះ >= 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 1 ដោយ -transition ទីបំផុតពី q f 1 ដោយ -transition បញ្ចប់ដោយ q f ។ ដូច្នេះពាក្យបែបនេះ។

    ពីទ្រឹស្តីបទ 4.2 និង 5.1 យើងទទួលបានដោយផ្ទាល់

    កូរ៉ូឡារី ៥.១. សម្រាប់អ្នករាល់គ្នា កន្សោមធម្មតា។មនុស្សម្នាក់អាចបង្កើត automaton កំណត់កំណត់ប្រកបដោយប្រសិទ្ធភាព ដែលទទួលស្គាល់ភាសាដែលតំណាងដោយកន្សោមនេះ។

    សេចក្តីថ្លែងការណ៍នេះគឺជាឧទាហរណ៍មួយ។ ទ្រឹស្តីបទសំយោគ: យោងទៅតាមការពិពណ៌នាភារកិច្ច (ភាសាដូចជា កន្សោមធម្មតា។) កម្មវិធី (DFA) ដែលប្រតិបត្តិវាត្រូវបានសាងសង់យ៉ាងមានប្រសិទ្ធភាព។ ការសន្ទនាក៏ជាការពិតផងដែរ - ទ្រឹស្តីបទនៃការវិភាគ.

    ទ្រឹស្តីបទ ៥.២. សម្រាប់ automaton finite deterministic (ឬ non-deterministic) និមួយៗអាចសាងសង់បាន។ កន្សោមធម្មតា។ដែលតំណាងឱ្យភាសាដែលទទួលស្គាល់ដោយ automaton នេះ។

    ភស្តុតាងនៃទ្រឹស្តីបទនេះគឺពិតជាបច្ចេកទេស និងហួសពីវិសាលភាពនៃវគ្គសិក្សារបស់យើង។

    ដូច្នេះ យើងអាចសន្និដ្ឋានបានថា ថ្នាក់នៃភាសា automata កំណត់ស្របគ្នាជាមួយនឹងថ្នាក់ ភាសាធម្មតា។. នៅក្នុងអ្វីដែលបន្ទាប់ យើងនឹងហៅវាយ៉ាងសាមញ្ញ ថ្នាក់នៃភាសាស្វ័យប្រវត្តិ.

    automaton M r ដែលត្រូវបានសាងសង់នៅក្នុងភស្តុតាងនៃទ្រឹស្តីបទ 5.1

    និយមន័យជាមូលដ្ឋាន កន្សោមទៀងទាត់នៅក្នុងអក្ខរក្រម Σ និងសំណុំធម្មតាដែលពួកគេបង្ហាញត្រូវបានកំណត់ឡើងវិញដូចខាងក្រោមៈ 1) កន្សោមធម្មតាដែលតំណាងឱ្យសំណុំធម្មតា; 2) e គឺជាកន្សោមធម្មតាដែលបង្ហាញពីសំណុំធម្មតា (e); 3) ប្រសិនបើ Σ នោះ a គឺជាកន្សោមធម្មតាដែលបង្ហាញពីសំណុំធម្មតា (a); 4) ប្រសិនបើ p និង q គឺជាកន្សោមធម្មតាដែលបង្ហាញពីសំណុំធម្មតា P និង Q បន្ទាប់មក a) (p + q) គឺជាកន្សោមធម្មតាដែលបង្ហាញពី P Q; ខ) pq គឺជាកន្សោមធម្មតាដែលបង្ហាញពី PQ; គ) p* គឺជាកន្សោមធម្មតាដែលតំណាងឱ្យ P*; 5) គ្មានអ្វីផ្សេងទៀតគឺជាការបញ្ចេញមតិធម្មតា។

    និយមន័យជាមូលដ្ឋាន ការកំណត់អាទិភាព៖ * (ការបញ្ជាក់ឡើងវិញ) – អាទិភាពខ្ពស់បំផុត; ការភ្ជាប់គ្នា; + (សហជីព) ។ ដូច្នេះ 0 + 10 * = (0 + (1 (0 *))) ។ ឧទាហរណ៍៖ 1. 01 មានន័យថា (01); 2. 0* - (0*); 3. (0+1)* - (0, 1)*; 4. (0+1)* 011 - មានន័យថាសំណុំនៃខ្សែអក្សរទាំងអស់ដែលមាន 0 និង 1 ហើយបញ្ចប់ដោយខ្សែអក្សរ 011; 5. (a+b) (a+b+0+1)* មានន័យថាសំណុំនៃខ្សែទាំងអស់ (0, 1, a, b)* ចាប់ផ្តើមដោយ a ឬ b។

    និយមន័យសំខាន់ៗនៃលេម៉ា៖ 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5 ) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α

    ការទំនាក់ទំនងរបស់ RT និង RM RM គឺជាភាសាដែលបង្កើតឡើងដោយ RT ។ ឧទាហរណ៍៖ x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d) ។ ការភ្ជាប់គ្នា៖ xy XY = (ac, ad, bc, bd) ។ k(u+o)t (k)(u, o)(t) = (ត្រីបាឡែន ឆ្មា) ឬដោយ លេម៉ា លេខ 5 និង លេខ 6 k(u+o)m = ត្រីបាឡែន + ឆ្មា (ត្រីបាឡែន ឆ្មា) . ការបញ្ជាក់៖ x = a, x* X* = (e, a, aaa, …), i.e. x* = e + xxx + …

    ទំនាក់ទំនងនៃ RT និង RM ការបង្រួបបង្រួម និងការរួបរួម៖ (xy)* = e + xyxyxy + ... (x + y)* = e + (x + y)(x + y) + ... = = e + xx + xy + yx + yy + xxx + … ឧទាហរណ៍៖ 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, ១១០, ១១១…)។ សហជីព​គឺ​ជា​ការ​ផ្លាស់​ប្តូ​រ​: x + y = y + x ការ​ភ្ជាប់​គឺ​មិន​មែន​ជា​: xy ≠ yx

    ទំនាក់ទំនងរវាង RT និង PM ឧទាហរណ៍អាទិភាព៖ x + yz (x, yz), (x + y)z (xz, yz), x + y * (e, x, y, yyy, yyyy, …), (x + y)* (e, x, y, xx, xy, yx, yy, xxx, …), (xy)* (e, xyxy, …), xy* (x, xyy, xyyy, …)។ លេមម៉ាថ្មី៖ a* + e = a*; (a + e) ​​* = a*; a*a* = a*; e* = អ៊ី; ល។

    ប្រព័ន្ធធម្មតានៃសមីការ សមីការជាមួយមេគុណធម្មតា X = a ។ X + b មានដំណោះស្រាយ (ចំនុចថេរតូចបំផុត) a*b: aa*b + b = (aa* + e)b = a*b ប្រព័ន្ធសមីការដែលមានមេគុណធម្មតា៖ X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 n ។ Xn X 2 \u003d α 20 + α 21 X 1 + α 22 X 2 + ... + α 2 n ។ Xn …………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn ។ Xn មិនស្គាល់ – Δ = (X 1, X 2, …, Xn) ។

    ប្រព័ន្ធធម្មតានៃសមីការ ក្បួនដោះស្រាយដំណោះស្រាយ (វិធីសាស្ត្រ Gauss): ជំហានទី 1. កំណត់ i = 1. ជំហានទី 2. ប្រសិនបើ i = n សូមទៅកាន់ជំហានទី 4. បើមិនដូច្នេះទេ សូមសរសេរសមីការសម្រាប់ Xi ជា Xi = αXi + β (β = β 0 ។ + βi +1 ស៊ី + 1 + … + βn.Xn)។ បន្ទាប់មក នៅខាងស្តាំដៃសម្រាប់សមីការ Xi+1, …, Xn យើងជំនួស Xi ដោយកន្សោមធម្មតា α*β។ ជំហានទី 3. បង្កើន i ដោយ 1 ហើយត្រឡប់ទៅជំហានទី 2 ។ ជំហានទី 4. សរសេរសមីការសម្រាប់ Xn ជា Xn = αXn + β ។ ទៅកាន់ជំហានទី 5 (ជាមួយ i = n) ។ ជំហានទី 5. សមីការសម្រាប់ Xi គឺ Xi = αXi + β។ សរសេរនៅលទ្ធផល Xi = α*β ក្នុងសមីការសម្រាប់ Xi– 1, …, X 1 ជំនួស α*β ជំនួសឱ្យ Xi ។ ជំហានទី 6. ប្រសិនបើ i = 1 សូមឈប់ បើមិនដូច្នេះទេ បន្ថយ i ដោយ 1 ហើយត្រឡប់ទៅជំហានទី 5 វិញ។

    ការបំប្លែង DFA ទៅជា RW សម្រាប់ DFA M = (Q, Σ, δ, q 0, F) យើងតែងប្រព័ន្ធដែលមានមេគុណធម្មតា ដែល Δ = Q: 1. យើងកំណត់ αij: = ; 2. ប្រសិនបើ δ(Xi, a) = Xj, a Σ, បន្ទាប់មក αij: = αij + a; 3. ប្រសិនបើ Xi F ឬ δ(Xi,) = HALT នោះ αi 0: = e ។ បន្ទាប់ពីដោះស្រាយ RV ដែលចង់បាននឹងជា X 1 = q 0 ។

    ការបំប្លែង DFA ទៅជា RW ឧទាហរណ៍៖ សម្រាប់លេខចំនុចថេរ យើងទទួលបានប្រព័ន្ធ q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 នៅទីនេះ៖ s ជាសញ្ញានៃលេខ, s = "+" + "-"; p – ខ្ទង់ទសភាគ, p = "."; d - លេខ, d = "0" + "1" + ... + "9" ។

    ការបំប្លែង DFA ទៅជា RW ដំណោះស្រាយ៖ q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q ​​2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. ពីសមីការទីបី៖ q 3 \u003d dq 3 + pq 4 + e \u003d d * (pq 4 + e) ​​។ ពីសមីការទីបួន៖ q 4 = dq 4 + e = d * ។

    បំលែង DFA ទៅជា RW បញ្ច្រាស៖ q 3 = d*(pq 4 + e) ​​​​= d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd* + dd *(pd* + e), q 0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e)។ ដូច្នេះ DFA នេះត្រូវគ្នាទៅនឹង RE s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e)។ ដើម្បីសម្រួល៖ s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) ​​​​= = spdd* + sdd*(pd* + e) ​​​+ pdd* + dd*(pd* + e) ​​= (s + e)(pdd* + dd*(pd* + e))) សម្រាប់កំណត់ចំណាំខ្លីជាងនេះ អ្នកអាចប្រើពាក្យដដែលៗវិជ្ជមាន aa* = a*a = a+: (s + e )(pdd*+dd*(pd*+e))=(s+e)(pd++d+pd*+d+)

    ការបំប្លែង DFA ទៅ RT ការគូសផែនទីអនុគមន៍នៃការផ្លាស់ប្តូរ DFA ទៅប្រតិបត្តិការកន្សោមធម្មតាជាមូលដ្ឋាន៖ q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*

    ការបំប្លែង DFA ទៅជា RT ការរួមបញ្ចូលគ្នាដ៏ស្មុគស្មាញនៃប្រតិបត្តិការ៖ q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a a (ab)+ q 2 b q 1 c e + (a + b)c*

    ការបំប្លែង DFA ទៅ RW សម្រាប់ RW (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d

    ការ​សរសេរ​កម្មវិធី​ក្នុង​ពេល​វេលា​ពិត​ប្រាកដ កន្សោម​ធម្មតា៖ បង្កើត​ជា​ភាសា​សរសេរ​កម្មវិធី​ជា​ច្រើន (PHP, Java. Script, …); បានអនុវត្តជាកម្មវិធីជំនួយ (ឧទាហរណ៍ ថ្នាក់ Regex សម្រាប់វេទិកា .NET) ។ ភាពខុសគ្នានៃទម្រង់សរសេរ៖ x? = x + e x (1, 3) = x + xxx ជាដើម។

    RT Programming Regex Class Constructs (System.Text.Regular.Expressions): Character Escape Sequence Interpretation b ពេលប្រើក្នុងតង្កៀបការ៉េ ត្រូវគ្នានឹងតួអក្សរ "←" (u 0008) t, r, n, a, f, v Tab (u 0009), រថក្រោះត្រឡប់មកវិញ (u 000 D), បន្ទាត់ថ្មី (u 000 A) ល. គ. តួអក្សរគ្រប់គ្រង X (ឧទាហរណ៍ c. C គឺ Ctrl+C, u 0003) e Escape (u 001 B) ooo តួអក្សរ Octal ASCII xhh Hex ASCII តួអក្សរ uhhhh តួអក្សរយូនីកូដ តួអក្សរខាងក្រោមមិនមែនជាតួអក្សរ PB ពិសេសទេ។ តួអក្សរពិសេសទាំងអស់ត្រូវតែគេចចេញជាមួយតួអក្សរនេះ។ ឧទាហរណ៍ (ក្នុងឧទាហរណ៍ លំនាំ និងខ្សែអក្សរស្វែងរកត្រូវបានផ្តល់ឱ្យ ការផ្គូផ្គងដែលរកឃើញក្នុងខ្សែអក្សរត្រូវបានគូសបញ្ជាក់): @"rnw+" – "rn ។ មានខ្សែអក្សរពីរនៅទីនេះ" .

    ការសរសេរកម្មវិធី RT សំណុំរងនៃតួអក្សរ។ តួអក្សរណាមួយក្រៅពីចុងបញ្ចប់នៃខ្សែអក្សរ (n) តួអក្សរណាមួយពីសំណុំ [^xxx] តួអក្សរណាមួយក្រៅពីតួអក្សរពីសំណុំតួអក្សរណាមួយពីជួរ] ដកនៃសំណុំមួយ ឬជួរពី p(ឈ្មោះផ្សេងទៀត) តួអក្សរណាមួយដែលបានបញ្ជាក់ តាមប្រភេទយូនីកូដដែលដាក់ឈ្មោះ P (name) តួអក្សរណាមួយ លើកលែងតែការកំណត់ដោយប្រភេទយូនីកូដដែលមានឈ្មោះ w សំណុំតួអក្សរដែលប្រើនៅពេលបញ្ជាក់អត្តសញ្ញាណ W សំណុំតួអក្សរដែលមិនត្រូវបានប្រើនៅពេលបញ្ជាក់អត្តសញ្ញាណ s Spaces S អ្វីទាំងអស់លើកលែងតែដកឃ្លា d ខ្ទង់ D មិនមែនជាខ្ទង់ ឧទាហរណ៍ : @" +" - "rn ។ មាន n ពីរបន្ទាត់នៅទីនេះ"; @"+" - "0xabcfx"; @"[^fx]+" - "0 xabcfx"; @"+" - "0xabcfx"; @"[^a-f]+" - "0 xabcfx"; @"]+" - "0xabcfx"; @"p(Lu)" - "ភ្លើងទីក្រុង"; // Lu - អក្សរធំ @"P(Lu)" - "ទីក្រុង"; @"p(Is. Cyrillic)" - "ha. OS"; // គឺ។ Cyrillic - អក្សររុស្ស៊ី

    PB Programming Anchor ^, A នៅដើមខ្សែអក្សរ $, Z នៅចុងបញ្ចប់នៃខ្សែអក្សរ ឬរហូតដល់ "n" នៅចុងបញ្ចប់នៃខ្សែអក្សរ z នៅចុងបញ្ចប់នៃខ្សែអក្សរ G ដែលការប្រកួតមុនបានបញ្ចប់ b ព្រំដែនពាក្យ B ទីតាំងណាមួយដែលមិននៅលើព្រំដែនពាក្យ ឧទាហរណ៍៖ @ "G(d)" - "(1)(3)(5)(9)"; // ការប្រកួតបី (1), (2) និង (3) @"bnS*ionb" - "អំណោយជាតិ"; @"Bendw*b" - "end sends endure lender"។

    ការសរសេរកម្មវិធីប្រតិបត្តិការ RT (បរិមាណ) *, *? និទាន + , + ? ការអះអាងឡើងវិញជាវិជ្ជមាន? , ? ? សូន្យ ឬមួយប្រកួត (n), (n)? ពិតប្រាកដ n ត្រូវគ្នា (n, ), (n, )? យ៉ាងហោចណាស់ n ត្រូវគ្នា (n, m), (n, m)? ពី n ដល់ m ផ្គូផ្គងឧទាហរណ៍ (បរិមាណទីមួយគឺលោភលន់ ស្វែងរកធាតុឱ្យបានច្រើនតាមដែលអាចធ្វើទៅបាន ទីពីរគឺខ្ជិល ស្វែងរកធាតុតិចតួចតាមដែលអាចធ្វើបាន): @"d(3, )" – "888 -5555"; @"^d(3)" - "913 -913"; @"-d(3)$" - "913 -913"; @"5+? 5" - "888 -5555"; // ការប្រកួតបី - 55, 55 និង 55 @"5+5" - "888 -5555" ។

    RT Programming Grouping () Group កំណត់ដោយស្វ័យប្រវត្តិនូវលេខ (?:) កុំរក្សាទុកក្រុម (?) ឬ (? "name") ប្រសិនបើរកឃើញត្រូវគ្នា បង្កើតក្រុមដែលមានឈ្មោះ (?) ឬលុបក្រុមដែលបានកំណត់ពីមុន និង (? "name-name") រក្សាទុកក្នុងក្រុមថ្មីនូវខ្សែអក្សររងមួយរវាងក្រុមដែលបានកំណត់ពីមុន និងក្រុមថ្មី (? imnsx:) បើក ឬបិទជម្រើសណាមួយក្នុងចំណោមប្រាំ (? -imnsx:) ជម្រើសដែលអាចធ្វើបាននៅក្នុងក្រុម៖ i - case អសកម្ម; s គឺជាបន្ទាត់មួយ (បន្ទាប់មក "." គឺជាតួអក្សរណាមួយ); m - របៀបពហុបន្ទាត់ ("^", "$" - ការចាប់ផ្តើមនិងចុងបញ្ចប់នៃបន្ទាត់នីមួយៗ); n - កុំចាប់យកក្រុមដែលគ្មានឈ្មោះ; x - មិនរាប់បញ្ចូលចន្លោះដែលមិនបានគេចចេញពីលំនាំ ហើយរួមបញ្ចូលមតិយោបល់បន្ទាប់ពីសញ្ញាលេខ (#) (?=) ការអះអាងមើលទៅខាងមុខវិជ្ជមានប្រវែងសូន្យ

    ការសរសេរកម្មវិធី RE (? !) Zero-length negative lookahead assertion (?) Non-returning (greedy) part of expressions ឧទាហរណ៍៖ @"(an)+" – "bananas annals"; @"an+" - "ប្រវត្តិដើមចេក"; // ប្រៀបធៀប, ការប្រកួតបី - an, an និង ann @"(? i: an)+" - "ba. NAnas annals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?

    Src="https://website/presentation/-112203859_437213351/image-24.jpg" alt="(!LANG:Programming RT លេខយោងក្រុម ឯកសារយោង k ឯកសារយោងក្រុមដែលមានឈ្មោះ ឧទាហរណ៍៖ @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}

    ការជំនួសកម្មវិធី RT $number ជំនួសផ្នែកនៃខ្សែអក្សរដែលត្រូវគ្នានឹងក្រុមជាមួយនឹងលេខដែលបានបញ្ជាក់ $(name) ជំនួសផ្នែកនៃខ្សែអក្សរដែលត្រូវគ្នានឹងក្រុមជាមួយនឹងឈ្មោះដែលបានបញ្ជាក់ $$ ជំនួស $$& ជំនួសដោយច្បាប់ចម្លងពេញលេញ match $` Replace the text of the input string until the match $" Replace the text of the input line after match $+ Replace the last captured group $_ Replace the whole line Comments (? #) inline comment # Comment to end of line

    លទ្ធផលកម្មវិធី RT នៃ Regex: Regex Matches() Match ។ ការប្រមូលផ្គូផ្គងក្រុម () ក្រុម។ ការចាប់យកក្រុមប្រមូល () ការចាប់យក។ ការចាប់យកការប្រមូល ()

    RT Programming Example in C++ CLI (Visual C++/CLR/CLR Console Application): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Match ^m = r-> Match (L"123 456"); int match. រាប់ = 0; while (m->Success) ( Console: : Write. Line(L"Match(0)", ++match. Count); for (int i = 1; i ក្រុម->រាប់; i++) (ក្រុម ^g = m->ក្រុម[i]; កុងសូល៖៖ សរសេរ។ បន្ទាត់(L" ក្រុម (0) = "(1)"", i, g-> តម្លៃ ); for (int j = 0; j Captures->Count; j++) ( Capture ^c = g->Captures[j]; Console: : Write.Line(L" Capture(0) = "(1)" , ទីតាំង = (2), ប្រវែង = (3)", j, c, c->សន្ទស្សន៍, c->ប្រវែង); ) ) m = m->បន្ទាប់។ ការប្រកួត(); ) ត្រឡប់ 0; ) ប្រព័ន្ធ៖ : អត្ថបទ : :ទៀង​ទា​ត។ កន្សោម

    ការដាក់បញ្ចូលសកម្មភាព និងការស្វែងរកកំហុស ការកំណត់ចំនួនខ្ទង់សំខាន់ៗក្នុងចំនួនមួយ៖ (s + e)(pd+ + d+(pd* + e)) s = +|p = ។ d = ds + e = s? = (+|-)? pd* + e = (pd*)? =.d*)? @"(+|-)? (. d+|d+(. d*)?)" ឬ @"^(+|-)? (. d+|d+(. d*)?)$" Regex r = ថ្មី Regex (@"^(+|-)? (. (? "digit"d)+|(? "digit"d)+.(? "digit"d)*)?)$"); ផ្គូផ្គង m = r ។ ផ្គូផ្គង("+1. 23456789"); if (m. Success) (ក្រុម g = m. Groups["digit"]; if (g. captures. រាប់

    ការបើកដំណើរការ និងស្វែងរកកំហុស កំណត់ទីតាំងនៃកំហុស៖ Regex r = new Regex(@"(+|-)? (. (? "digit"d)+|(?" digit"d)+.(?" digit"d)*)?)"); ខ្សែអក្សរ str = "+1.2345!678"; ផ្គូផ្គង m = r ។ ការប្រកួត (str); if (m. Success) (ក្រុម g = m. Groups["digit"]; if (g. Captures. Count 0) Console. Write. Line("Error at position 1: unexpected character "(0)", str ); else if (m.Length

    ការបើកសកម្មភាព និងការស្វែងរកកំហុស ការកំណត់ទីតាំងនៃកំហុស៖ 1. ទីតាំងដំបូងនៃខ្សែអក្សរបញ្ចូល (1) ប្រសិនបើការប្រកួតដំបូងមិនចាប់ផ្តើមពីទីតាំង Index = 0; 2. ទីតាំងបន្ទាប់ពីការប្រកួតចុងក្រោយ (ការប្រកួត។ ប្រវែង + 1) ប្រសិនបើវាមិនត្រូវគ្នានឹងទីតាំងចុងក្រោយនៃខ្សែអក្សរបញ្ចូល។ 3. ទីតាំងនៃការបំបែកទីមួយរវាងការប្រកួត (match[i]. Index + match[i]. Length + 1), ប្រសិនបើតួអក្សរបន្ទាប់ការប្រកួតមុនមិនមែនជាតួអក្សរទីមួយនៃការប្រកួតបន្ទាប់។

    សន្ទស្សន៍) បំបែក; សន្ទស្សន៍ = m[i] ។ សន្ទស្សន៍ + m[i] ។ ប្រវែង; ) កុងសូល។ សរសេរ។ បន្ទាត់("កំហុសនៅទីតាំង (0) "(1)"", សន្ទស្សន៍ + 1, str); ) "abc ។ ឆ្នាំ pqr" ត្រឹមត្រូវ; + abc ។ ឆ្នាំ pqr" - កំហុសក្នុងទីតាំង 1 ("+"); "abc ។ ឆ្នាំ pqr!" - កំហុសក្នុងទីតាំង 12 ("!"); "abc ។ ស៊ីហ្សី! pqr" - កំហុសនៅទីតាំង 8 ("!") ។

    ការដាក់បញ្ចូលសកម្មភាព និងការស្វែងរកកំហុស ប៉ុន្តែ! "abc ។ ឆ្នាំ +pqr" - កំហុសនៅទីតាំង 8 (" ") ។ វ៉ារ្យ៉ង់គំរូថ្មី៖ @"w+. w+)*. (? !$))?" សុពលភាព៖ "abc. ឆ្នាំ +pqr" - កំហុសក្នុងទីតាំង 9 ("+"); "abc ។ ឆ្នាំ pqr. "- កំហុសនៅក្នុងទីតាំង 12 (" ។ ") ។

    និយមន័យដែលមានតុល្យភាព៖ "(? "x")" បន្ថែមធាតុមួយទៅបណ្តុំដែលមានឈ្មោះថា "x"; "(? "-x")" ដកធាតុមួយចេញពីបណ្តុំ "x"; "(? (x)(?!))" ពិនិត្យមើលថាមិនមានធាតុណាមួយដែលនៅសល់ក្នុងបណ្តុំ "x" ទេ។ ភាសា L ពិពណ៌នាអំពីសេចក្តីថ្លែងការណ៍ដែលភ្ជាប់គ្នានៃភាសា Pascal “ចាប់ផ្តើមបញ្ចប់; ': @"^s*((? "begins+)+(? "-begin"ends*; s*)+)*(? (ចាប់ផ្តើម)(?!))$" ។

    DFA គឺជាករណីពិសេសរបស់ NFA ។ នៅក្នុងគាត់៖

      មិនមានរដ្ឋជាមួយ ε-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 ត្រូវបានកំណត់ដូចខាងក្រោមៈ

    ការកសាង nc ពីកន្សោមធម្មតា។

    1. សម្រាប់ ε NFA មានទម្រង់ដូចខាងក្រោម (0 គឺជារដ្ឋដំបូង 1 គឺជារដ្ឋចុងក្រោយ):

    2. សម្រាប់ការរួមបញ្ចូលនៅក្នុងភាសា NFA ដែលបានផ្តល់ឱ្យ៖

    3. អនុញ្ញាតឱ្យ N(s) និង N(t) ជា NFAs សម្រាប់កន្សោមធម្មតា s និង t ។

      សម្រាប់កន្សោមធម្មតា s|t សមាសធាតុ NFA មានទម្រង់ដូចខាងក្រោម៖

    ខ. សម្រាប់កន្សោមធម្មតា st NFA៖

    ជាមួយ។ សម្រាប់កន្សោម s* NFA មានទម្រង់៖

    ឃ. សម្រាប់កន្សោមក្នុងតង្កៀប (s) NFA N(s) ត្រូវបានប្រើដូចក្នុងកថាខណ្ឌ ក។

    រដ្ឋថ្មីនីមួយៗទទួលបានឈ្មោះបុគ្គល។ ការសាងសង់ NFA N(r) មានលក្ខណៈសម្បត្តិដូចខាងក្រោមៈ

      N(r) មានរដ្ឋមួយចំនួនដែលមិនលើសពីចំនួននិមិត្តសញ្ញាច្រើនជាង 2 ដង។

      N(r) មានស្ថានភាពដំបូង និងចុងក្រោយមួយយ៉ាងពិតប្រាកដ។ រដ្ឋចុងក្រោយមិនមានការផ្លាស់ប្តូរបន្តទេ។

      រដ្ឋនីមួយៗ N(r) មានការផ្លាស់ប្តូរ 1 សម្រាប់និមិត្តសញ្ញាពីអក្ខរក្រម () ឬមិនលើសពី 2 ε-transitions ចេញ។

    បំប្លែង ណា ទៅ ឌីកា។

    NFA នៅក្នុងរូបភាពទី 1 មានការផ្លាស់ប្តូរ 2 ពីរដ្ឋ 0 សម្រាប់និមិត្តសញ្ញា a: រដ្ឋ 0 និង 1 ។ ការផ្លាស់ប្តូរបែបនេះគឺមិនច្បាស់លាស់ដូចការផ្លាស់ប្តូរនៅក្នុង ε ដែរ។ ការធ្វើគំរូ NSCs បែបនេះដោយមានជំនួយពីកម្មវិធីកុំព្យូទ័រគឺពិបាកជាង។ និយមន័យនៃការទទួលយកបានចែងថាត្រូវតែមានផ្លូវមួយចំនួនពីរដ្ឋដំបូងទៅរដ្ឋចុងក្រោយ ប៉ុន្តែនៅពេលដែលមានផ្លូវច្រើនសម្រាប់ខ្សែអក្សរបញ្ចូលដូចគ្នា ពួកគេទាំងអស់ត្រូវតែពិចារណាដើម្បីស្វែងរកផ្លូវទៅកាន់រដ្ឋចុងក្រោយ ឬដើម្បីស្វែងរក។ ថាមិនមានផ្លូវបែបនេះទេ។

    នៅក្នុងតារាងការផ្លាស់ប្តូរ NFA ធាតុនីមួយៗត្រូវគ្នាទៅនឹងសំណុំនៃរដ្ឋ ខណៈពេលដែលនៅក្នុងតារាងការផ្លាស់ប្តូរ DFA មានតែមួយប៉ុណ្ណោះ។ ខ្លឹមសារនៃការផ្លាស់ប្តូរគឺថារដ្ឋនីមួយៗនៃ 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. Seti, D. Ullman - អ្នកចងក្រង៖ គោលការណ៍ បច្ចេកវិទ្យា ឧបករណ៍។

    ការកសាង automaton កំណត់កំណត់ពីកន្សោមធម្មតា។

    ឥឡូវនេះ យើងបង្ហាញនូវក្បួនដោះស្រាយសម្រាប់បង្កើត automaton finite deterministic ពីកន្សោមធម្មតាដែលអនុញ្ញាតឱ្យប្រើភាសាដូចគ្នា [?] ។

    អនុញ្ញាតឱ្យកន្សោមធម្មតា r ត្រូវបានផ្តល់ឱ្យក្នុងអក្ខរក្រម T. បន្ថែមសញ្ញាសម្គាល់បញ្ចប់ទៅកន្សោមធម្មតា r: (r)# ។ កន្សោមធម្មតាបែបនេះនឹងត្រូវបានគេហៅថាបានបញ្ចប់។ នៅក្នុងដំណើរការនៃការងាររបស់វា ក្បួនដោះស្រាយនឹងប្រើកន្សោមធម្មតាដែលបានបញ្ចប់។

    ក្បួនដោះស្រាយនឹងដំណើរការនៅលើមែកធាងវាក្យសម្ព័ន្ធសម្រាប់កន្សោមធម្មតាដែលបានបញ្ចប់ (r)# ដែលស្លឹកនីមួយៗត្រូវបានសម្គាល់ដោយនិមិត្តសញ្ញា និងនីមួយៗ កំពូលខាងក្នុងត្រូវបានសម្គាល់ដោយសញ្ញានៃប្រតិបត្តិការមួយ៖ (ការភ្ជាប់), | (សហជីព), * (ពាក្យដដែលៗ) ។

    ស្លឹកឈើនីមួយៗ (លើកលែងតែស្លឹកអ៊ី) នឹងត្រូវបានផ្តល់លេខតែមួយគត់ ហៅថាទីតាំង ហើយយើងនឹងប្រើវា ម្យ៉ាងវិញទៀត សំដៅលើស្លឹកឈើ និងម្យ៉ាងវិញទៀត ដើម្បីយោង និមិត្តសញ្ញាដែលត្រូវគ្នានឹងស្លឹកនេះ។ ចំណាំថាប្រសិនបើតួអក្សរមួយត្រូវបានប្រើច្រើនដងក្នុងកន្សោមធម្មតា វាមានមុខតំណែងច្រើន។

    ចូរឆ្លងកាត់មែកធាង T ពីបាតទៅកំពូលពីឆ្វេងទៅស្តាំ ហើយគណនាមុខងារចំនួនបួន៖ nullable, firstpos, lastpos និង followpos ។ មុខងារបីដំបូង - nullable, firstpos និង lastpos - ត្រូវបានកំណត់នៅលើថ្នាំងនៃមែកធាង ហើយ followpos ត្រូវបានកំណត់នៅលើសំណុំនៃមុខតំណែង។ តម្លៃនៃមុខងារទាំងអស់ លើកលែងតែ nullable គឺជាសំណុំនៃមុខតំណែង។ អនុគមន៍ followpos ត្រូវបានគណនាតាមរយៈមុខងារបីផ្សេងទៀត។

    អនុគមន៍ firstpos(n) សម្រាប់ node n នីមួយៗនៃមែកធាងវាក្យសម្ព័ន្ធកន្សោមធម្មតាផ្តល់ឱ្យសំណុំនៃមុខតំណែងដែលត្រូវគ្នានឹងតួអក្សរដំបូងនៅក្នុង ខ្សែអក្សររងបង្កើត​ដោយ​កន្សោម​រង​ជាមួយ​ចំណុច​កំពូល​នៅ n ។ ស្រដៀងគ្នានេះដែរ Lastpos(n) ផ្តល់ឱ្យសំណុំនៃមុខតំណែងដែលត្រូវគ្នានឹងតួអក្សរចុងក្រោយនៅក្នុង ខ្សែអក្សររងបង្កើតដោយ subexpressions ជាមួយ vertex n. សម្រាប់ថ្នាំង n ដែលមែកធាងរង (នោះគឺដើមឈើដែលថ្នាំងឫស n គឺ) អាចបង្កើតពាក្យទទេ កំណត់ nullable(n)=true និងសម្រាប់ថ្នាំងដែលនៅសល់ nullable(n)=false ។

    តារាងសម្រាប់គណនាមុខងារ nullable, firstpos, និង lastpos ត្រូវបានបង្ហាញក្នុងរូបភព។ ៣.១១.

    ឧទាហរណ៍ 3.7.នៅក្នុងរូបភព។ 3.12 បង្ហាញមែកធាងវាក្យសម្ព័ន្ធសម្រាប់កន្សោមធម្មតាដែលបានបញ្ចប់ (a|b) * abb# ជាមួយនឹងលទ្ធផលនៃការវាយតម្លៃមុខងារ firstpos និង lastpos ។ នៅខាងឆ្វេងនៃថ្នាំងនីមួយៗគឺជាតម្លៃនៃ firstpos នៅខាងស្តាំថ្នាំងគឺជាតម្លៃនៃ Lastpos ។ ចំណាំថាមុខងារទាំងនេះអាចត្រូវបានគណនានៅក្នុងការឆ្លងកាត់ដើមឈើមួយ។

    ប្រសិនបើខ្ញុំជាមុខតំណែង នោះ followpos(i) គឺជាសំណុំនៃមុខតំណែង j ដូចជាមាន string ខ្លះ... cd ... កើតឡើងជាភាសាដែលបានពិពណ៌នាដោយកន្សោមធម្មតា ដូចជាទីតាំងនោះ ខ្ញុំត្រូវគ្នានឹងការកើតឡើងនៃ c និងទីតាំងនេះ j គឺជាធាតុ d ។

    អង្ករ។ ៣.១១.

    អង្ករ។ ៣.១២.

    អនុគមន៍ followpos ក៏​អាច​ត្រូវ​បាន​គណនា​នៅ​ក្នុង​ការ​ឆ្លងកាត់​បាត​ឡើង​លើ​នៃ​មែកធាង​ដោយ​យោង​តាម​ច្បាប់​ទាំង​ពីរ​នេះ។

    1. អនុញ្ញាតឱ្យ n ជាថ្នាំងខាងក្នុងដែលមានប្រតិបត្តិការ (ការភ្ជាប់គ្នា) u និង v ជាកូនចៅរបស់វា។ បន្ទាប់មកសម្រាប់មុខតំណែងនីមួយៗដែលខ្ញុំបានបញ្ចូលក្នុង lastpos(u) យើងបន្ថែមទៅសំណុំនៃតម្លៃ followpos(i) the set firstpos(v)។

    2. អនុញ្ញាតឱ្យ n ជាថ្នាំងខាងក្នុងជាមួយប្រតិបត្តិការ * (ការធ្វើឡើងវិញ), u - កូនចៅរបស់វា។ បន្ទាប់មកសម្រាប់មុខតំណែងនីមួយៗដែលខ្ញុំបានបញ្ចូលក្នុង lastpos(u) យើងបន្ថែមទៅសំណុំនៃតម្លៃ followpos(i) set firstpos(u)។

    ឧទាហរណ៍ 3.8. លទ្ធផលនៃការវាយតម្លៃមុខងារ followpos សម្រាប់កន្សោមធម្មតាពីឧទាហរណ៍មុនត្រូវបានបង្ហាញក្នុងរូបភព។ ៣.១៣.

    ក្បួនដោះស្រាយ 3.3. ការសាងសង់ដោយផ្ទាល់នៃ DFA ពីកន្សោមធម្មតា។

    ច្រកចូល. កន្សោមធម្មតា r ក្នុងអក្ខរក្រម T ។

    ទិន្នផល. DFA M = (Q, T, D, q 0, F) ដូចជា L(M) = L(r)។

    វិធីសាស្រ្ត. រដ្ឋ DFA ត្រូវគ្នាទៅនឹងសំណុំនៃមុខតំណែង។

    ដំបូង Q និង D គឺទទេ។ អនុវត្តតាមជំហាន 1-6:

    (1) បង្កើតមែកធាងវាក្យសម្ព័ន្ធសម្រាប់កន្សោមធម្មតាដែលបានបន្ថែម (r)# ។

    អត្ថបទ​ដែល​ទាក់ទង