ဆက်စပ်မှုမရှိသောဘာသာစကားသည် ဆက်စပ်မှုမရှိသောသဒ္ဒါကိုအသုံးပြု၍ ဖော်ပြနိုင်သည့် တရားဝင်ဘာသာစကားအမျိုးအစားတစ်ခုဖြစ်သည်။ ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီနယ်ပယ်တွင်၊ ပြဿနာများ၏ ရှုပ်ထွေးမှုနှင့် တွက်ချက်မှုကန့်သတ်ချက်များကို နားလည်ရန် ဆက်စပ်မှုမရှိသော ဘာသာစကားများသည် အရေးကြီးသောအခန်းကဏ္ဍမှ ပါဝင်ပါသည်။ ဆက်စပ်မှုမရှိသော ဘာသာစကား၏ သဘောတရားကို အပြည့်အဝနားလည်ရန်၊ ၎င်း၏အဓိပ္ပါယ်ဖွင့်ဆိုချက်နှင့် ဆက်စပ်မှုမရှိသော သဒ္ဒါ၏ အစိတ်အပိုင်းများကို စူးစမ်းလေ့လာရန် လိုအပ်ပါသည်။
ဆက်စပ်မှုမရှိသော ဘာသာစကားကို ဆက်စပ်မှုမရှိသော သဒ္ဒါဖြင့် ထုတ်ပေးနိုင်သော စာကြောင်းအစုတစ်ခုအဖြစ် သတ်မှတ်သည်။ ဆက်စပ်မှုမရှိသော သဒ္ဒါတွင် အစိတ်အပိုင်းလေးခုပါရှိသည်- terminal မဟုတ်သော သင်္ကေတအစုံ၊ terminal သင်္ကေတအစုံ၊ ထုတ်လုပ်မှုစည်းမျဉ်းအစုံနှင့် အစသင်္ကေတတစ်ခု။
terminal မဟုတ်သော သင်္ကေတများသည် နောက်ထပ် ချဲ့ထွင်နိုင်သော သို့မဟုတ် အစားထိုးနိုင်သည့် စိတ္တဇအရာများကို ကိုယ်စားပြုသည်။ ဤသင်္ကေတများကို များသောအားဖြင့် စာလုံးကြီးများဖြင့် ကိုယ်စားပြုသည်။ ဥပမာအားဖြင့်၊ ဂဏန်းသင်္ချာအသုံးအနှုန်းများအတွက် ဆက်စပ်မှုမရှိသောသဒ္ဒါတစ်ခုတွင်၊ ကျွန်ုပ်တို့တွင် E (အသုံးအနှုန်းကို ကိုယ်စားပြုခြင်း)၊ T (အသုံးအနှုန်းတစ်ခုကို ကိုယ်စားပြုခြင်း) နှင့် F (အချက်တစ်ခုကို ကိုယ်စားပြုခြင်း) ကဲ့သို့သော terminal မဟုတ်သော သင်္ကေတများရှိသည်။
အခြားတစ်ဖက်တွင် terminal သင်္ကေတများသည် ဘာသာစကား၏ အခြေခံယူနစ်များဖြစ်သည်။ ဤသင်္ကေတများကို ထပ်မံချဲ့ထွင်၍မရပါ၊ အများအားဖြင့် စာလုံးသေး သို့မဟုတ် အခြားအက္ခရာများဖြင့် ကိုယ်စားပြုပါသည်။ ဂဏန်းသင်္ချာအသုံးအနှုန်းများ၏ ဆက်စပ်မှုတွင်၊ terminal သင်္ကေတများတွင် ဂဏန်းများ (ဥပမာ၊ 0၊ 1၊ 2) နှင့် ဂဏန်းသင်္ချာအော်ပရေတာများ (ဥပမာ +၊ -၊ *၊ /) တို့ ပါဝင်နိုင်သည်။
ထုတ်လုပ်ရေးစည်းမျဉ်းများသည် terminal မဟုတ်သောသင်္ကေတများကို မည်ကဲ့သို့ချဲ့ထွင်နိုင်သည် သို့မဟုတ် အခြားသင်္ကေတများဖြင့် အစားထိုးနိုင်သည်ကို သတ်မှတ်ပါသည်။ ထုတ်လုပ်မှုစည်းမျဉ်းတစ်ခုစီတွင် ဘယ်ဘက်ခြမ်းရှိ ဂိတ်အမှတ်အသားမဟုတ်သော သင်္ကေတတစ်ခုနှင့် ညာဖက်ခြမ်းရှိ သင်္ကေတများ (ဂိတ်မဟုတ်သောနှင့် တာမီနယ်နှစ်ခုလုံး) ပါဝင်သည်။ ဤစည်းမျဉ်းများသည် ဘာသာစကားတွင် မှန်ကန်သောစာကြောင်းများထုတ်လုပ်ရန်အတွက် အသုံးပြုနိုင်သည့် ဖြစ်နိုင်သော အသွင်ပြောင်းမှုများ သို့မဟုတ် ဆင်းသက်လာမှုများကို သတ်မှတ်ပေးသည်။ ဥပမာအားဖြင့်၊ ဂဏန်းသင်္ချာအသုံးအနှုန်းများအတွက် ဆက်စပ်မှုမရှိသောသဒ္ဒါတစ်ခုတွင်၊ ကျွန်ုပ်တို့တွင် E -> E + T ကဲ့သို့သော ထုတ်လုပ်မှုစည်းမျဉ်းများ (အသုံးအနှုန်းတစ်ခုထည့်သွင်းခြင်းဖြင့် ချဲ့ထွင်နိုင်သည်ကို ညွှန်ပြခြင်း) သို့မဟုတ် T -> F (အသုံးအနှုန်းတစ်ခု ဖြစ်နိုင်သည်ကို ညွှန်ပြသည် အချက်တစ်ခုဖြင့် အစားထိုးပါသည်။)
စတင်သင်္ကေတသည် တရားဝင်စာကြောင်းများ၏ မျိုးဆက်စတင်သည့် ကနဦး terminal မဟုတ်သောသင်္ကေတကို ကိုယ်စားပြုသည်။ ၎င်းကို အများအားဖြင့် S ဖြင့် ရည်ညွှန်းသည်။ ဂဏန်းသင်္ချာအသုံးအနှုန်းများ၏ ဆက်စပ်မှုတွင်၊ စတင်သင်္ကေတသည် E ဖြစ်ကောင်းဖြစ်နိုင်ပြီး၊ မှန်ကန်သောအသုံးအနှုန်းများ၏ မျိုးဆက်သည် စကားရပ်တစ်ခုမှ စတင်သည်ဟု ညွှန်ပြပါသည်။
စကားစပ်မပါသော ဘာသာစကားတစ်ခု၏ အယူအဆနှင့် ၎င်း၏ အစိတ်အပိုင်းများကို သရုပ်ဖော်ရန်၊ ဟန်ချက်ညီသော ကွင်းကွင်းကို ဖန်တီးပေးသည့် ဘာသာစကားအတွက် ရိုးရှင်းသော စကားစပ်မပါသော သဒ္ဒါတစ်ခုကို စဉ်းစားကြည့်ကြပါစို့။ သဒ္ဒါတွင် အောက်ပါ အစိတ်အပိုင်းများ ပါဝင်သည်။
ဂိတ်မဟုတ်သော သင်္ကေတများ- S (စတင်သင်္ကေတ)
Terminal သင်္ကေတများ- (၊ )
ထုတ်လုပ်ရေးစည်းမျဉ်းများ- S --> (S) | အက်စ်အက်စ် | ε (ε သည် အလွတ်စာကြောင်းကို ကိုယ်စားပြုသည်)
ဤသဒ္ဒါတွင်၊ terminal မဟုတ်သောသင်္ကေတ S သည် မျှတသောကွင်းစဥ်ကြိုးတန်းတစ်ခုကိုကိုယ်စားပြုသည်။ ထုတ်လုပ်မှုစည်းမျဉ်းများတွင် S သည် ကွင်းအတွင်း ((S) ၊ S နှစ်ခု (SS) ကို ပေါင်းစည်းခြင်း) သို့မဟုတ် ကြိုးအလွတ် (ε) ကို ဖန်တီးခြင်းဖြင့် S ကို တိုးချဲ့နိုင်သည်ဟု သတ်မှတ်ပါသည်။
ဤသဒ္ဒါကို အသုံးပြု၍ ဟန်ချက်ညီသော ကွင်းအတွင်း ဘာသာစကားဖြင့် မှန်ကန်သော စာကြောင်းများကို ထုတ်လုပ်နိုင်ပါသည်။ ဥပမာအားဖြင့်၊ start သင်္ကေတ S ဖြင့် စတင်၍ string ((())) ကိုရရှိရန် ထုတ်လုပ်ရေးစည်းမျဉ်းများကို အသုံးပြုနိုင်ပါသည်။ ဤစာကြောင်းသည် ဟန်ချက်ညီသော ကွင်းဆက်၏ အစီအရီကို ကိုယ်စားပြုသည်။
ဆက်စပ်မှုမရှိသော ဘာသာစကားကို ဆက်စပ်မှုမရှိသော သဒ္ဒါဖြင့် ထုတ်ပေးနိုင်သော စာကြောင်းအစုတစ်ခုအဖြစ် သတ်မှတ်သည်။ အကြောင်းအရာမပါသော သဒ္ဒါတစ်ခု၏ အစိတ်အပိုင်းများတွင် terminal မဟုတ်သော သင်္ကေတများ၊ terminal သင်္ကေတများ၊ ထုတ်လုပ်မှုစည်းမျဉ်းများနှင့် အစပြုသည့် သင်္ကေတများ ပါဝင်သည်။ terminal သင်္ကေတများသည် ဘာသာစကား၏ အခြေခံယူနစ်များဖြစ်ပြီး terminal symbols များသည် တိုးချဲ့ သို့မဟုတ် အစားထိုးနိုင်သော abstract entities များကို ကိုယ်စားပြုပါသည်။ ထုတ်လုပ်ရေးစည်းမျဉ်းများသည် ဖြစ်နိုင်ချေရှိသော အသွင်ပြောင်းမှုများ သို့မဟုတ် ဆင်းသက်လာမှုများကို သတ်မှတ်ပေးပြီး စတင်သည့်သင်္ကေတသည် တရားဝင်စာကြောင်းများဖန်တီးရန်အတွက် ကနဦးမဟုတ်သော terminal သင်္ကေတကို ကိုယ်စားပြုသည်။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ စကားအထိခိုက်မခံဘာသာစကားများ:
- ဘာသာစကားတစ်ခုသည် အခြားဘာသာစကားတစ်ခုထက်ပို၍ အစွမ်းထက်သည်ဟု ဆိုလိုခြင်းဖြစ်သည်။
- Chomsky ၏သဒ္ဒါပုံမှန်ပုံစံသည် အမြဲတမ်းဆုံးဖြတ်နိုင်ပါသလား။
- Type-0 ကို အသိအမှတ်ပြုရန် လက်ရှိနည်းလမ်းများ ရှိပါသလား။ ကွမ်တမ်ကွန်ပြူတာများကို ဖြစ်နိုင်ချေရှိစေရန် ကျွန်ုပ်တို့ မျှော်လင့်ပါသလား။
- ဘာသာစကား D ၏ ဥပမာတွင်၊ string S = 0^P 1^P 0^P 1^P သည် အဘယ်ကြောင့် စုပ်ယူမှုပိုင်ဆိုင်မှုကို မထိန်းထားသနည်း။
- Pumping lemma ကိုအသုံးပြုရန် string ကိုပိုင်းခြားသောအခါတွင်ထည့်သွင်းစဉ်းစားရမည့်ကိစ္စနှစ်ရပ်ကားအဘယ်နည်း။
- ဘာသာစကား B ၏ ဥပမာတွင်၊ string a^Pb^Pc^P သည် အဘယ်ကြောင့် pumping property ကို မကိုင်ထားသနည်း။
- ရေစုပ်စက်ကို ထိန်းထားရန် ကျေနပ်ရန် လိုအပ်သည့် အခြေအနေများကား အဘယ်နည်း။
- ဘာသာစကားတစ်ခုသည် ဆက်စပ်မှုမရှိကြောင်း သက်သေပြရန်အတွက် Pumping Lemma ကို မည်သို့အသုံးပြုရမည်နည်း။
- ဆက်စပ်မှုမရှိသောဘာသာစကားများအတွက် ချပေးထားသော lemma အရ ဆက်စပ်မှုမရှိသောဘာသာစကားတစ်ခုဟု သတ်မှတ်ရန် ကျေနပ်ရမည့်အခြေအနေများကား အဘယ်နည်း။
- စကားစပ်မပါသော သဒ္ဒါများ၏ ဆက်စပ်အကြောင်းအရာတွင် ပြန်ယူခြင်း၏ သဘောတရားနှင့် ကြိုးရှည်များကို မည်ကဲ့သို့ ဖန်တီးနိုင်သည်ကို ရှင်းပြပါ။
Context Sensitive Languages တွင် နောက်ထပ်မေးခွန်းများနှင့် အဖြေများကို ကြည့်ပါ။