ပုံမှန်ဘာသာစကားများ၏ စကားဝိုင်းတွင် ဆုံးဖြတ်နိုင်သော မေးခွန်းတစ်ခုက ဘာကိုဆိုလိုသနည်း။
အဆုံးအဖြတ်ရနိုင်သောမေးခွန်းတစ်ခု၊ ပုံမှန်ဘာသာစကားများ၏အခြေအနေတွင်၊ အာမခံချက်မှန်ကန်သောထွက်ရှိမှုရှိသော အယ်လဂိုရီသမ်တစ်ခုဖြင့် ဖြေနိုင်သောမေးခွန်းကို ရည်ညွှန်းသည်။ တစ်နည်းဆိုရသော်၊ အချိန်အကန့်အသတ်ဖြင့် အဖြေကို ဆုံးဖြတ်နိုင်သည့် တွက်ချက်မှုဆိုင်ရာ လုပ်ထုံးလုပ်နည်းတစ်ခုရှိနေသည့်အတွက် မေးခွန်းတစ်ခုဖြစ်သည်။
ပုံမှန်ဘာသာစကားများနှင့်ပတ်သက်၍ အဆုံးအဖြတ်ရနိုင်သောမေးခွန်းတစ်ခု၏သဘောတရားကို နားလည်ရန်၊ ပုံမှန်ဘာသာစကားများကို ဦးစွာရှင်းလင်းနားလည်ရန် အရေးကြီးပါသည်။ ပုံမှန်ဘာသာစကားများသည် ကွန်ပျူတာသိပ္ပံတွင် အခြေခံကျသော အယူအဆတစ်ခုဖြစ်ပြီး အကန့်အသတ်ရှိသော အော်တိုမာတာ သို့မဟုတ် ပုံမှန်အသုံးအနှုန်းများဖြင့် အသိအမှတ်ပြုနိုင်သည့် ပုံစံများ သို့မဟုတ် စာကြောင်းအစုံများကို ဖော်ပြရန်အတွက် အသုံးပြုပါသည်။
ဆုံးဖြတ်ချက်ချနိုင်မှုသည် Turing စက် သို့မဟုတ် အခြားသော ညီမျှသော တွက်ချက်မှုပုံစံဖြင့် ထိထိရောက်ရောက် အသိအမှတ်ပြုနိုင်သည့် ဘာသာစကားများ၏ အတန်းအစားကို သတ်မှတ်ပေးသည့် ပိုင်ဆိုင်မှုတစ်ခုဖြစ်သည်။ မည်သည့် input string ကိုမဆို ပေးထားသည့် algorithm တစ်ခုရှိလျှင် string သည် language နှင့် သက်ဆိုင်သည် ၊
ပုံမှန်ဘာသာစကားများ၏ အခြေအနေတွင်၊ ဆုံးဖြတ်နိုင်သောမေးခွန်းကို အောက်ပါအတိုင်း ပုံဖော်နိုင်သည်- ပုံမှန်ဘာသာစကား L နှင့် string w တို့အား ပေးအပ်ပါက L ၏ အဖွဲ့ဝင်ဖြစ်ပါသလား။ ဘာသာစကား L ကို အသိအမှတ်ပြုသည့် ကန့်သတ် automaton တစ်ခုကို တည်ဆောက်ပြီး input string w တွင် automaton ကို အတုယူခြင်းဖြင့် ဤမေးခွန်းကို ဖြေနိုင်ပါသည်။ automaton သည် w ကိုလက်ခံပါက၊ မေးခွန်း၏အဖြေမှာ "yes"; မဟုတ်ရင် အဖြေက "မဟုတ်ဘူး"။
ဥပမာအားဖြင့်၊ ပုံမှန်ဘာသာစကား L = {0, 1}* ကို binary strings များအားလုံးကို ကိုယ်စားပြုသည့် အမျိုးအစားကို ထည့်သွင်းစဉ်းစားပါ။ w = 101010 ဟူသော စာကြောင်းဖြင့် ဆုံးဖြတ်နိုင်သော မေးခွန်းမှာ L ၏ wa အဖွဲ့ဝင်ဖြစ်ပါသလား။ ဤမေးခွန်းကိုဖြေဆိုရန်၊ ကျွန်ုပ်တို့သည် ဘာသာစကား L ကို အသိအမှတ်ပြုသည့် အကန့်အသတ်ရှိသော automaton တစ်ခုကို တည်ဆောက်နိုင်ပြီး၊ ထို့နောက် input string w တွင် automaton ကို ပုံစံတူလုပ်နိုင်သည်။ automaton သည် input string တစ်ခုလုံးကို လုပ်ဆောင်ပြီးနောက် လက်ခံသည့်အခြေအနေသို့ရောက်ရှိပါက အဖြေမှာ "yes" ဖြစ်သည်။ မဟုတ်ရင် အဖြေက "မဟုတ်ဘူး"။ ဤကိစ္စတွင်၊ automaton သည် လက်ခံသည့်အခြေအနေသို့ ရောက်ရှိသွားလိမ့်မည်၊ ထို့ကြောင့် အဖြေမှာ "Yes" ဖြစ်သည်။
ဆုံးဖြတ်ချက်ချနိုင်မှုသည် ပုံမှန်ဘာသာစကားများအတွက် ပေးထားသည့် ပုံမှန်ဘာသာစကားတိုင်းအတွက် အသင်းဝင်ပြဿနာကို ဖြေရှင်းပေးနိုင်သည့် အယ်လဂိုရီသမ်တစ်ခုရှိနေကြောင်း သေချာစေသောကြောင့် ၎င်းသည် ပုံမှန်ဘာသာစကားများ၏ အခြေအနေတွင် နှစ်လိုဖွယ်ကောင်းသောပိုင်ဆိုင်မှုတစ်ခုဖြစ်သည်။ ဤပိုင်ဆိုင်မှုသည် ဆိုက်ဘာလုံခြုံရေးအပါအဝင် ကွန်ပြူတာသိပ္ပံနယ်ပယ်အသီးသီးတွင် အရေးပါသောသက်ရောက်မှုများရှိပြီး ကျူးကျော်ဝင်ရောက်မှုရှာဖွေခြင်းစနစ်များအတွက် ပုံစံများသတ်မှတ်ရန် သို့မဟုတ် ဝင်ရောက်ထိန်းချုပ်မှုမူဝါဒများကို သတ်မှတ်ရန် ပုံမှန်ဘာသာစကားများကို မကြာခဏအသုံးပြုလေ့ရှိပါသည်။
ပုံမှန်ဘာသာစကားများ၏ စကားဝိုင်းတွင် အဆုံးအဖြတ်ရနိုင်သောမေးခွန်းသည် အာမခံချက်ရှိသော မှန်ကန်သောထွက်ပေါက်ဖြင့် အယ်လဂိုရီသမ်တစ်ခုဖြင့် ဖြေနိုင်သည့်မေးခွန်းကို ရည်ညွှန်းသည်။ အချိန်အတိုင်းအတာတစ်ခုအတွင်း အဖြေကိုဆုံးဖြတ်နိုင်သည့် တွက်ချက်မှုဆိုင်ရာလုပ်ထုံးလုပ်နည်းတစ်ခုရှိနေသည့်မေးခွန်းတစ်ခုဖြစ်သည်။ ဆုံးဖြတ်နိုင်မှုသည် ပုံမှန်ဘာသာစကားများအတွက် အသင်းဝင်ပြဿနာကို ဖြေရှင်းနိုင်သည့် အယ်လဂိုရီသမ်တစ်ခုရှိကြောင်း သေချာစေသောကြောင့် ၎င်းသည် ပုံမှန်ဘာသာစကားများ၏ အခြေအနေတွင် နှစ်လိုဖွယ်ကောင်းသောပိုင်ဆိုင်မှုတစ်ခုဖြစ်သည်။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ 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 သည် ပြဿနာဖြစ်ပါသလား။