အကြောင်းအရာမပါသော သဒ္ဒါကို ပိုင်းခြားစိတ်ဖြာခြင်းတွင် သဒ္ဒါမှသတ်မှတ်ထားသော ထုတ်လုပ်ရေးစည်းမျဉ်းများအလိုက် သင်္ကေတများ၏ အစီအရီကို ခွဲခြမ်းစိတ်ဖြာခြင်း ပါဝင်သည်။ ဤလုပ်ငန်းစဉ်သည် ဆိုက်ဘာလုံခြုံရေးအပါအဝင် ကွန်ပြူတာသိပ္ပံနယ်ပယ်အသီးသီးတွင် အခြေခံအကျဆုံးဖြစ်ပြီး၊ ၎င်းသည် ကျွန်ုပ်တို့အား ဖွဲ့စည်းတည်ဆောက်ထားသော အချက်အလက်များကို နားလည်ပြီး ကြိုးကိုင်နိုင်စေပါသည်။ ဤအဖြေတွင်၊ အကြောင်းအရာမပါသော သဒ္ဒါတစ်ခုကို ပိုင်းခြားရန် အယ်လဂိုရီသမ်ကို ဖော်ပြပြီး ၎င်း၏အချိန်ရှုပ်ထွေးမှုကို ဆွေးနွေးပါမည်။
စကားစပ်မပါသော သဒ္ဒါများကို ပိုင်းခြားရန် အသုံးအများဆုံး အယ်လဂိုရီသမ်မှာ ၎င်း၏ တီထွင်သူ Cocke၊ Younger နှင့် Kasami တို့ကို အမည်ပေးထားသည့် CYK algorithm ဖြစ်သည်။ ဤအယ်လဂိုရီသမ်သည် တက်ကြွသောပရိုဂရမ်ရေးဆွဲခြင်းအပေါ်အခြေခံပြီး အောက်ခြေမှခွဲခြမ်းစိတ်ဖြာမှု၏နိယာမပေါ်တွင်လုပ်ဆောင်သည်။ ၎င်းသည် input ၏ substrings များအတွက် ဖြစ်နိုင်သော parses အားလုံးကို ကိုယ်စားပြုသည့် ခွဲခြမ်းစိတ်ဖြာဇယားကို တည်ဆောက်သည်။
CYK algorithm သည် အောက်ပါအတိုင်း အလုပ်လုပ်ပါသည်။
1. n သည် input string ၏ အရှည်ဖြစ်သည့် အတိုင်းအတာ nxn ပါသော ခွဲခြမ်းစိတ်ဖြာဇယားကို စတင်ပါ။
2. ထည့်သွင်းမှုစာကြောင်းရှိ terminal သင်္ကေတတစ်ခုစီအတွက်၊ ၎င်းကိုထုတ်လုပ်သည့်မဟုတ်သောသင်္ကေတများဖြင့် ခွဲခြမ်းစိပ်ဖြာဇယားရှိ သက်ဆိုင်ရာဆဲလ်ကိုဖြည့်ပါ။
3. စာတန်းခွဲတစ်ခုစီအတွက် l 2 မှ n နှင့် စတင်သည့်အနေအထားတစ်ခုစီအတွက် i 1 မှ n-l+1 မှ အောက်ပါတို့ကို လုပ်ဆောင်ပါ-
a အခန်းကန့်အမှတ် p တစ်ခုစီအတွက် i မှ i+l-2 နှင့် ထုတ်လုပ်မှုစည်းမျဉ်း A -> BC တစ်ခုစီအတွက်၊ ဆဲလ်များ (i၊ p) နှင့် (p+1၊ i+l-1) တွင် နာမ်မဟုတ်သော သင်္ကေတများ B နှင့် C ပါရှိမရှိ စစ်ဆေးပါ။ အသီးသီး။ သို့ဆိုလျှင်၊ A ကို ဆဲလ်ထဲသို့ ထည့်ပါ (i၊ i+l-1)။
4. သဒ္ဒါ၏အစသင်္ကေတသည် ဆဲလ် (1၊ n) တွင်ရှိနေပါက၊ ထည့်သွင်းသည့်စာကြောင်းသည် သဒ္ဒါမှဆင်းသက်လာနိုင်သည်။ မဟုတ်ရင် မလုပ်နိုင်ဘူး။
CYK algorithm ၏ အချိန်ရှုပ်ထွေးမှုသည် O(n^3 * |G|) ဖြစ်ပြီး n သည် input string နှင့် |G| သဒ္ဒါ၏အရွယ်အစားဖြစ်သည်။ ဤရှုပ်ထွေးမှုသည် ခွဲခြမ်းစိတ်ဖြာဇယားတွင် ဖြည့်ရန်အသုံးပြုသည့် nested loops မှ ဖြစ်ပေါ်လာသည်။ algorithm သည် ဖြစ်နိုင်ချေရှိသော အပိုင်းခွဲအမှတ်များနှင့် တန်းခွဲတစ်ခုစီ၏ ထုတ်လုပ်မှုစည်းမျဉ်းအားလုံးကို စစ်ဆေးပြီး ကုဗအချိန်ရှုပ်ထွေးမှုကို ဖြစ်ပေါ်စေသည်။
အယ်လဂိုရီသမ်ကို သရုပ်ဖော်ရန်၊ အောက်ပါ ဆက်စပ်သဒ္ဒါကို ထည့်သွင်းစဉ်းစားပါ။
S --> AB | ဘီစီ
A --> AA | a
B --> AB | ခ
C --> BC | ဂ
ပြီးတော့ input string "abc" ဤနမူနာအတွက် ခွဲခြမ်းစိတ်ဖြာမှုဇယားသည် အောက်ပါအတိုင်း တွေ့ရလိမ့်မည်-
| ၁ | 1 | 2 |
—-|—–|—–|—–|
၁ | A၊S | B၊C | ၎ |
—-|—–|—–|—–|
2 | | B၊C | A|
—-|—–|—–|—–|
3 | | | ဂ|
—-|—–|—–|—–|
ဤဇယားတွင်၊ ဆဲလ် (1၊ 3) တွင် start သင်္ကေတ S ပါရှိသည်၊ ထည့်သွင်းထားသောစာကြောင်း "abc" သည် ပေးထားသောသဒ္ဒါမှ ဆင်းသက်လာနိုင်ကြောင်း ညွှန်ပြပါသည်။
CYK algorithm ကဲ့သို့သော ဆက်စပ်မှုမရှိသော သဒ္ဒါကို ပိုင်းခြားရန် အယ်လဂိုရီသမ်သည် ကျွန်ုပ်တို့အား ဖွဲ့စည်းတည်ဆောက်ထားသော အချက်အလက်များကို ပိုင်းခြားစိတ်ဖြာနားလည်နိုင်စေပါသည်။ ၎င်းသည် ခွဲခြမ်းစိတ်ဖြာမှုဇယားတစ်ခုကို တည်ဆောက်ပြီး သဒ္ဒါ၏ထုတ်လုပ်မှုစည်းမျဉ်းများနှင့်အညီ မှန်ကန်သောဆင်းသက်မှုများကို စစ်ဆေးခြင်းဖြင့် လုပ်ဆောင်သည်။ CYK algorithm ၏ အချိန်ရှုပ်ထွေးမှုသည် O(n^3 * |G|) ဖြစ်ပြီး n သည် input string နှင့် |G| သဒ္ဒါ၏အရွယ်အစားဖြစ်သည်။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ ရှုပ်ထွေး:
- PSPACE အတန်းသည် EXPSPACE အတန်းနှင့် မညီမျှပါသလား။
- P ရှုပ်ထွေးမှု အတန်းသည် PSPACE အတန်း၏ အစုခွဲတစ်ခုလား။
- အဆုံးအဖြတ်ပေးသော TM တွင် မည်သည့် NP ပြီးပြည့်စုံသော ပြဿနာအတွက် ထိရောက်သော polynomial ဖြေရှင်းချက်ကို ရှာဖွေခြင်းဖြင့် Np နှင့် P အတန်းသည် တူညီကြောင်း သက်သေပြနိုင်မလား။
- NP အတန်းသည် EXPTIME အတန်းနှင့် ညီမျှနိုင်ပါသလား။
- မသိသော NP algorithm မရှိသည့်အတွက် PSPACE တွင် ပြဿနာများရှိပါသလား။
- SAT ပြဿနာသည် NP ပြီးပြည့်စုံသောပြဿနာ ဖြစ်နိုင်ပါသလား။
- polynomial အချိန်အတွင်း ဖြေရှင်းပေးမည့် အဆုံးအဖြတ်မရှိသော turing machine တစ်ခုရှိလျှင် NP complexity class တွင် ပြဿနာရှိနိုင်ပါသလား။
- NP သည် polynomial time verifiers များပါရှိသော ဘာသာစကားများ၏ အတန်းအစားဖြစ်သည်။
- P နှင့် NP တို့သည် အမှန်တကယ် တူညီသော ရှုပ်ထွေးမှု အတန်းများ ဖြစ်ပါသလား။
- P complexity class ရှိ ဆက်စပ်ဘာသာစကားတိုင်းသည် အခမဲ့ဖြစ်ပါသလား။
Complexity တွင် နောက်ထပ်မေးခွန်းများနှင့် အဖြေများကို ကြည့်ပါ။