အဆုံးအဖြတ်ပေးသော နှင့် အဆုံးအဖြတ်မရှိသော အဆုံးအဖြတ်ရှိသော စက်ယန္တရားများအကြား အဓိကကွာခြားချက်ကား အဘယ်နည်း။
အဆုံးအဖြတ်ပေးသော ကန့်သတ်ပြည်နယ်စက် (DFSM) နှင့် အဆုံးအဖြတ်မရှိသော ကန့်သတ်ပြည်နယ်စက် (NFSM) တို့သည် တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီနယ်ပယ်တွင် အသုံးပြုသည့် ကန့်သတ်ပြည်နယ်စက် (FSMs) အမျိုးအစား နှစ်မျိုးဖြစ်သည်။ FSM နှစ်ခုလုံးတွင် အလားတူလက္ခဏာများ ရှိပြီး အမျိုးမျိုးသော တွက်ချက်မှုဆိုင်ရာ လုပ်ငန်းစဉ်များကို စံနမူနာပြုရန် အသုံးပြုသော်လည်း ၎င်းတို့၏ အပြုအမူနှင့် ၎င်းတို့၏ အသွင်ကူးပြောင်းမှု သဘောသဘာဝအရ ကွဲပြားသည်။
DFSM နှင့် NFSM အကြား အဓိက ကွာခြားချက်မှာ ပြည်နယ်များအကြား အကူးအပြောင်းများကို ကိုင်တွယ်ပုံတွင် ဖြစ်သည်။ DFSM တွင်၊ ပြည်နယ်တစ်ခုမှ အခြားတစ်ခုသို့ ကူးပြောင်းခြင်းကို လက်ရှိအခြေအနေနှင့် ထည့်သွင်းသင်္ကေတဖြင့် သီးခြားသတ်မှတ်ထားသည်။ ဆိုလိုသည်မှာ ပေးထားသောပြည်နယ်နှင့် ထည့်သွင်းသင်္ကေတအတွက် ဖြစ်နိုင်ချေရှိသော နောက်ပြည်နယ်တစ်ခုသာ ရှိနိုင်ပါသည်။ တစ်နည်းဆိုရသော် DFSM သည် အဆုံးအဖြတ်ပေးသည့်ပုံစံဖြင့် လုပ်ဆောင်နေပြီး နောက်တစ်ခုအခြေအနေကို လက်ရှိအခြေအနေနှင့် ထည့်သွင်းမှုတို့ဖြင့် သီးခြားသတ်မှတ်ထားသည်။
အခြားတစ်ဖက်တွင်၊ NFSM သည် ပေးထားသောပြည်နယ်နှင့် ထည့်သွင်းသင်္ကေတအတွက် ဖြစ်နိုင်သည့်နောက်ပြည်နယ်များစွာကို ခွင့်ပြုသည်။ ဆိုလိုသည်မှာ NFSM ၏ အကူးအပြောင်းလုပ်ဆောင်ချက်သည် နောက်ပြည်နယ်အတွက် တရားဝင်ရွေးချယ်စရာများစွာရှိနိုင်သည်။ တစ်နည်းဆိုရသော် NFSM သည် လက်ရှိအခြေအနေနှင့် ထည့်သွင်းမှုဖြင့် နောက်ပြည်နယ်ကို သီးခြားသတ်မှတ်မထားသော အဆုံးအဖြတ်မရှိသည့်ပုံစံဖြင့် လုပ်ဆောင်သည်။ ယင်းအစား၊ NFSM တစ်ခုသည် တစ်ခု သို့မဟုတ် တစ်ခုထက်ပိုသော ပြည်နယ်များသို့ တစ်ပြိုင်နက် ကူးပြောင်းနိုင်ပြီး ဖြစ်နိုင်ချေရှိသော တွက်ချက်မှုလမ်းကြောင်းများစွာကို ဖန်တီးပေးနိုင်သည်။
ဒီကွာခြားချက်ကို ဥပမာအနေနဲ့ သုံးသပ်ကြည့်ရအောင်။ ကျွန်ုပ်တို့တွင် 0s နှင့် 1s တို့ကို 1 ဖြင့်အဆုံးသတ်သော ရိုးရှင်းသောဘာသာစကားကို နမူနာယူသည့် NFSM နှင့် DFSM တစ်ခုရှိသည်ဆိုပါစို့။ NFSM တွင် ပြည်နယ်နှစ်ခုရှိသည်- S0 နှင့် S1 ။ DFSM တွင် Q0 နှင့် Q1 ပြည်နယ်နှစ်ခုလည်းရှိသည်။
NFSM အတွက်၊ state S0 နှင့် input သင်္ကေတ 0 အတွက် အသွင်ကူးပြောင်းရေး လုပ်ဆောင်ချက်သည် S0 နှင့် S1 ဖြစ်နိုင်သည့် နောက်ပြည်နယ်နှစ်ခု ရှိနိုင်ပါသည်။ ဆိုလိုသည်မှာ NFSM သည် state S0 တွင်ရှိပြီး input သင်္ကေတ 0 ကိုလက်ခံသောအခါ၊ ၎င်းသည် state S0 သို့မဟုတ် state S1 သို့ပြောင်းနိုင်သည်။ အခြားတစ်ဖက်တွင်၊ state S0 နှင့် input သင်္ကေတ 1 အတွက် အသွင်ကူးပြောင်းရေးလုပ်ဆောင်ချက်တွင် နောက်ထပ်ဖြစ်နိုင်သော အခြေအနေတစ်ခုသာရှိသည်- S1။ ဆိုလိုသည်မှာ NFSM သည် state S0 တွင်ရှိပြီး input သင်္ကေတ 1 ကိုလက်ခံသောအခါ၊ ၎င်းသည် state S1 သို့ အမြဲတမ်းပြောင်းသွားမည်ဖြစ်သည်။
ဆန့်ကျင်ဘက်အနေနှင့်၊ DFSM တွင် လက်ရှိအခြေအနေနှင့် ထည့်သွင်းသင်္ကေတပေါင်းစပ်မှုတစ်ခုစီအတွက် ထူးခြားသောနောက်အခြေအနေတစ်ခုရှိသည်။ ဥပမာအားဖြင့်၊ DFSM သည် Q0 ပြည်နယ်တွင်ရှိပြီး input သင်္ကေတ 0 ကို လက်ခံရရှိသောအခါ၊ ၎င်းသည် state Q0 သို့ အမြဲတမ်းပြောင်းသွားပါမည်။ အလားတူ၊ DFSM သည် Q0 ပြည်နယ်တွင်ရှိပြီး ထည့်သွင်းသင်္ကေတ 1 ကိုလက်ခံသောအခါ၊ ၎င်းသည် Q1 သို့ အမြဲတမ်းပြောင်းသွားပါမည်။
အဆုံးအဖြတ်ပေးခြင်းနှင့် အဆုံးအဖြတ်မရှိသော အကန့်အသတ်ရှိသော ပြည်နယ်စက်များကြား အဓိက ကွာခြားချက်မှာ ၎င်းတို့၏ အသွင်ကူးပြောင်းခြင်း၏ သဘောသဘာဝတွင် တည်ရှိသည်။ အဆုံးအဖြတ်ပေးသော ကန့်သတ်ပြည်နယ်စက် (DFSM) တွင် လက်ရှိအခြေအနေနှင့် အသွင်းသင်္ကေတပေါင်းစပ်မှုတစ်ခုစီအတွက် ထူးခြားသောနောက်အခြေအနေတစ်ခု ရှိပြီး၊ အတိအကျမဟုတ်သော ကန့်သတ်ချက်ပြည်နယ်စက် (NFSM) သည် လက်ရှိအခြေအနေနှင့် ထည့်သွင်းသင်္ကေတပေါင်းစပ်မှုအတွက် ဖြစ်နိုင်သည့်နောက်ပြည်နယ်များစွာကို ခွင့်ပြုပေးပါသည်။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ EITC/IS/CCTF တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ အခြေခံအချက်များ:
- အဆုံးအဖြတ်မရှိသော PDAs များကို ထည့်သွင်းစဉ်းစားခြင်းဖြင့် ပြည်နယ်များ၏ ထိပ်တန်းရာထူးကို အဓိပ္ပါယ်ဖွင့်ဆိုနိုင်သည်။ သို့သော်လည်း၊ သတ်မှတ်မသတ်မှတ်ထားသော PDA များသည် ပြည်နယ်များစွာတွင် တပြိုင်နက်တည်းမဖြစ်နိုင်သော stack တစ်ခုသာရှိသည်။ ဒါက ဘယ်လိုဖြစ်နိုင်မလဲ။
- ကွန်ရက်အသွားအလာကို ခွဲခြမ်းစိတ်ဖြာပြီး ဖြစ်နိုင်ချေရှိသော လုံခြုံရေးချိုးဖောက်မှုများကို ညွှန်ပြသည့် ပုံစံများကို ခွဲခြားသတ်မှတ်ရန် အသုံးပြုသည့် PDA ၏ ဥပမာကား အဘယ်နည်း။
- ဘာသာစကားတစ်ခုသည် အခြားဘာသာစကားတစ်ခုထက်ပို၍ အစွမ်းထက်သည်ဟု ဆိုလိုခြင်းဖြစ်သည်။
- Turing Machine မှ context-sensitive languages များကို မှတ်မိနိုင်ပါသလား။
- ဘာသာစကား U = 0^n1^n (n>=0) အဘယ်ကြောင့် ပုံမှန်မဟုတ်သနည်း။
- '1' သင်္ကေတများ ကိန်းဂဏန်းများနှင့်အတူ binary strings များကို အသိအမှတ်ပြုသည့် FSM ကို မည်ကဲ့သို့ အဓိပ္ပာယ်ဖွင့်ဆိုရန်နှင့် ထည့်သွင်းမှု string 1011 ကို လုပ်ဆောင်သည့်အခါ ၎င်းနှင့် မည်သို့ဖြစ်မည်ကို ပြသရန်။
- အဆုံးအဖြတ်မဟုတ်သောဝါဒသည် အကူးအပြောင်းလုပ်ဆောင်မှုကို မည်သို့အကျိုးသက်ရောက်သနည်း။
- ပုံမှန်ဘာသာစကားများသည် Finite State Machines များနှင့် တူညီပါသလား။
- PSPACE အတန်းသည် EXPSPACE အတန်းနှင့် မညီမျှပါသလား။
- Church-Turing Thesis အရ Turing Machine က algorithmically computable problem သည် ပြဿနာဖြစ်ပါသလား။