တဳအဝ်ရဳ အဝ်တဝ်မာတာ
တဳအဝ်ရဳ အဝ်တဝ်မာတာ (အၚ်္ဂလိက်: Automata theory) ဟီုမ္ဂးဂှ် ဒှ် ကဏ္ဍသဇိုင် မွဲ ပ္ဍဲကဵု သိပ္ပံ ကောန်ပျူတာ (Computer science) ကေုာံ သင်္ချာ (Mathematics) မအာရီုစွံ လတူ ပရေင်လ္ၚတ် စက် အာဗ်သတြက် (Abstract machines) ကေုာံ သၞောတ် ပရေင်ချပ်ဂၞန် (Computational systems) ဂမၠိုင် ရ။ ဝေါဟာရ "Automata" (အဝ်တဝ်မာတာ) ဝွံ ကၠုင်နူ အရေဝ်ဂရိတ် "αὐτόματα" မဂွံအဓိပ္ပါယ် "အရာ မချဳဓရာင် ကၠောန်ကမၠောန် နကဵု အလဵုအလဵုဍေဟ်" (Self-acting) ရ။[၁]
ဘာသာရပ်ဏအ်ဝွံ လ္ၚတ် သ္ၚေဝ်ဂၠေပ် ဒဒှ်ရ ပြသၞာ သင်္ချာ ကေုာံ ယုတ္တိဗေဒ လဵုမွဲ မာန် သောင်ကလး နကဵု စက် ကောန်ပျူတာ (Computable) ရော၊ တုဲပၠန် စက် ဂကူလဵု မာန် သောင်ကလး ပြသၞာ ဂကူလဵု ရော ဂှ်ရ။ တဳအဝ်ရဳ ဏအ်ဝွံ ဒှ် သဇိုင် အဓိက သွက် ပရေင်ဖန်ဇန် ကောန်ပျာင်လာ (Compiler)၊ ပရေင်စၟတ်သမ္တီ လၟေင်အက္ခရ် (Pattern recognition)၊ ကေုာံ ဥာဏ်ပညာ ကောန်ပျူတာ (Artificial intelligence) တအ် ရ။
၁။ နိဒါန် ကေုာံ ပွံက်အဓိပ္ပါယ် (Introduction and Definition)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]တဳအဝ်ရဳ အဝ်တဝ်မာတာ ဝွံ လ္ၚတ် ပရူ မဝ်ဒယ် သင်္ချာ (Mathematical models) မကော်စ "အဝ်တဝ်မာတာ" ရ။ အဝ်တဝ်မာတာ မွဲ ဟီုမ္ဂးဂှ် ဒှ် သၞောတ် မနွံကဵု ကဆံင်တန်တဴ (States) မကၠောန်ကမၠောန် အတိုင် သၞောဝ်ဝ် (Rules) မဖျေဟ်လဝ် ကိုပ်ကၠာ ရ။ ကာလ မလိက် ဟွံသေင်မ္ဂး တင်ဂၞင် (Input) လုပ်ကၠုင် မ္ဂး၊ စက် ဂှ် ပြံင်လှာဲ အာ ကဆံင်တန်တဴ မွဲ တုဲ မွဲ အတိုင် သၞောဝ်ဝ် ဂှ် ရ။
ပ္ဍဲကဵု ဘာသာရပ် ဏအ်၊ နွံကဵု ဝေါဟာရ သဇိုင် အဓိက ၃ သာ်-
- အက္ခရ် (Alphabet - $\Sigma$): ဒှ် ဂကောံ သင်္ကေတ ဟွံသေင်မ္ဂး မလိက် သဇိုင်။ (ဥပမာ - $\Sigma = \{0, 1\}$ သွက် သၞောတ် ဒွိ)။
- လၟေင်အက္ခရ် (String - $w$): ဒှ် လၟေင် သင်္ကေတ မရုဲကေတ် နူကဵု Alphabet။ (ဥပမာ - "01011")။
- အရေဝ်ဘာသာ ပွံက် (Formal Language - $L$): ဒှ် ဂကောံ လၟေင်အက္ခရ် ဂမၠိုင် မကိတ်ညဳ ကု သၞောဝ်ဝ် မွဲမွဲ။
၂။ ဝင် ကေုာံ ပရေင်ဇၞော်မောဝ် (History and Development)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ဝင် တဳအဝ်ရဳ အဝ်တဝ်မာတာ ဝွံ စကတဵုဒှ် ကၠုင်လဝ် ပ္ဍဲ ဗွဝ်ကၠံ ၂၀ ပ္ဍဲ အခိင် တၠပညာ သင်္ချာ တအ် ဂစာန် သ္ၚေဝ်ဂၠေပ် ပယျဵုအပိုတ်အခြာ ပရေင်ချပ်ဂၞန် (Limits of computation) ရ။
- ပ္ဍဲ သၞာံ ၁၉၃၆ ဂှ်၊ အလန် တူရိန် (Alan Turing) ခၞံဗဒှ် လဝ် စက် တူရိန် (Turing Machine) မဒှ် မဝ်ဒယ် မထ္ၜးကဵု အစောံသတ္တိ ကောန်ပျူတာ အလုံအိုတ်သီု ရ။
- ပ္ဍဲ သၞာံ ၁၉၄၃ ဂှ်၊ Warren McCulloch ကဵု Walter Pitts တအ် ပတိုန်ထ္ၜး လဝ် မဝ်ဒယ် ဇာဇၞိက် ဉာဏ် (Neural networks) မဒှ် သဇိုင် သွက် ဖာဲနာက် အဝ်တဝ်မာတာ (Finite automata) ရ။
- ပ္ဍဲ သၞာံ ၁၉၅၆ ဂှ်၊ နဝ်မ် ချောမ်စကဳ (Noam Chomsky) ဖန်ဗဒှ် လဝ် ချောမ်စကဳ ဟာဲရာကဳ (Chomsky Hierarchy) မပါ်ကရေက် သဒ္ဒါ (Grammars) ကေုာံ အရေဝ်ဘာသာ နကဵု ကဆံင် အဝ်တဝ်မာတာ မတၞဟ်ခြာ ရေင်သကအ် ရ。[၂]
၃။ သဇိုင် လညာတ် ကေုာံ မဝ်ဒယ်ဂမၠိုင် (Basic Concepts and Models)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]တဳအဝ်ရဳ ဏအ်ဝွံ ဒုင်သဇိုင် လတူ မဝ်ဒယ် စက် အဓိက ၄ သာ် မနွံကဵု အစောံသတ္တိ တၞဟ်ခြာ ရေင်သကအ် ရ။ စက် ဇၟာပ်ဇၟာပ် မွဲဝွံ နွံကဵု တင်သမ္တီ (Memory) ကေုာံ ဗီုပြင် ကၠောန်ကမၠောန် မဟွံတုပ် ရ။
- ဖာဲနာက် အဝ်တဝ်မာတာ (Finite Automata): ဟွံမဲ ကဵု တင်သမ္တီ တုဲ၊ စၟတ်သမ္တီ အရေဝ်ဘာသာ ဓမ္မတာ (Regular languages) သၟး ရ။
- ပုရှ်ဒံင်း အဝ်တဝ်မာတာ (Pushdown Automata): နွံကဵု တင်သမ္တီ ဗီုပြင် ဒက်စွံ (Stack) တုဲ၊ စၟတ်သမ္တီ အရေဝ်ဘာသာ ဟွံမဲ ကဵု သ္ၚိအင် (Context-free languages) ရ။
- လဳနဳယာ ဘံင်းဒေတ် အဝ်တဝ်မာတာ (Linear Bounded Automata): နွံကဵု တင်သမ္တီ မကန့်သတ်လဝ် တုဲ၊ စၟတ်သမ္တီ အရေဝ်ဘာသာ စပ်ကဵု သ္ၚိအင် (Context-sensitive languages) ရ။
- စက် တူရိန် (Turing Machine): နွံကဵု တင်သမ္တီ ဟွံမဲ အပိုတ်အခြာ (Infinite tape) တုဲ၊ စၟတ်သမ္တီ အရေဝ်ဘာသာ သီုဖအိုတ် မတော်ဂွံ မာန် (Recursively enumerable languages) ရ。
၄။ ဖာဲနာက် အဝ်တဝ်မာတာ (Finite Automata - FA)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ဖာဲနာက် အဝ်တဝ်မာတာ (FA) ဂှ် ဒှ် မဝ်ဒယ် မလောဲသွာ အိုတ် မွဲ ပ္ဍဲကဵု တဳအဝ်ရဳ ဏအ် ရ။ ဍေဟ်ဝွံ နွံကဵု ကဆံင်တန်တဴ (States) လၟိဟ် မရိုဟ်လၟိဟ် ဂွံ (Finite) သၟး ရ။ FA ဝွံ ညးပါ်လဝ် ၜါ သာ် -
- ဒဳတာမိန်နစ်စတစ် ဖာဲနာက် အဝ်တဝ်မာတာ (DFA - Deterministic Finite Automata): သွက် ကဆံင်တန်တဴ ဇၟာပ်ဇၟာပ် မွဲ ကေုာံ သင်္ကေတ လုပ် ဇၟာပ်ဇၟာပ် မွဲ ဂှ်၊ နွံကဵု ဂၠံင်တရဴ ပြံင်လှာဲ ဆ မွဲ ဂၠံင် ဓဝ် ဟေင် ရ။
- နန်-ဒဳတာမိန်နစ်စတစ် ဖာဲနာက် အဝ်တဝ်မာတာ (NFA - Nondeterministic Finite Automata): သွက် သင်္ကေတ လုပ် မွဲ ဂှ်၊ မာန် ပြံင်လှာဲ အာ ကဆံင်တန်တဴ ဂၠိုင်နူ မွဲ မာန် ရ (ဟွံသေင်မ္ဂး ဟွံပြံင်လှာဲ လေဝ် ဂွံ)။
ၜိုန်ရ NFA ဂှ် ရံင်အာ ထုဲထံင် ကီုလေဝ်၊ သဳအိုရဳ ထ္ၜးလဝ် ဒဒှ်ရ အစောံသတ္တိ DFA ကဵု NFA ဂှ် တုပ်သၟဟ် (Equivalent) ရေင်သကအ် ရ။ ဍေဟ်တအ် ၜါ သီုဖအိုတ် စၟတ်သမ္တီ "အရေဝ်ဘာသာ ဓမ္မတာ" (Regular Languages) မာန် ရ။
၅။ ပုရှ်ဒံင်း အဝ်တဝ်မာတာ (Pushdown Automata - PDA)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ဖာဲနာက် အဝ်တဝ်မာတာ ဝွံ ဟွံမာန် ရိုဟ်လၟိဟ် တုဲ ဟွံမာန် သောင်ကလး ပြသၞာ ဗီုကဵု "စၟတ်သမ္တီ လၟိဟ် ခ္ဍပ် $a^n b^n$" (ဥပမာ - ခ္ဍပ် ပံက် ကဵု ခ္ဍပ် ကၟာတ် ဒးတုပ်) ရ။ သွက်ဂွံ သောင်ကလး ပြသၞာ ဏအ်၊ တၠပညာ တအ် ဖန်ဗဒှ် လဝ် ပုရှ်ဒံင်း အဝ်တဝ်မာတာ (PDA) ရ။
PDA ဂှ် တုပ် ကဵု FA ကီုရ ဆဂး ဍေဟ် ထပ်စုတ် လဝ် တင်သမ္တီ မကော်စ "Stack" (ဒက်စွံ) မွဲ ရ။ Stack ဝွံ ကၠောန်ကမၠောန် အတိုင် သၞောတ်ဝ် LIFO (Last-In-First-Out) မဒှ် အရာ လက္ကရဴအိုတ် လုပ် ဂှ် ကၠာအိုတ် ဒးတိတ် ရ။ PDA ဝွံ ဒှ် သဇိုင် အဓိက သွက် ပရေင်ဖန်ဇန် သဒ္ဒါ ပရဝ်ဂရာမ် (Programming languages syntax) ကေုာံ လၟေင်ကမၠောန် ပါစဳင် (Parsing) ပ္ဍဲ ကောန်ပျာင်လာ တအ် ရ။
၆။ စက် တူရိန် (Turing Machine)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]စက် တူရိန် ဝွံ ဒှ် မဝ်ဒယ် ကောန်ပျူတာ မနွံကဵု အစောံသတ္တိ သၠုင်အိုတ် ကေုာံ ဖန်ဗဒှ် လဝ် နကဵု အလန် တူရိန် ရ။ ဍေဟ်ဝွံ နွံကဵု ဖဲ (Tape) မနွံ ဇမၠိင် ဟွံမဲ အပိုတ်အခြာ မပါ်လဝ် နကဵု အကွက် (Cells) တုဲ၊ နွံကဵု က္ဍိုပ် (Head) မမာန် ဗှ်၊ ချူ၊ ကေုာံ ပြံင်လှာဲ ပ္ဍဲ လပါ် ဇွိ ကဵု ပုင် ရ။[၃]
စက် တူရိန် ဝွံ မာန် သောင်ကလး ပြသၞာ သင်္ချာ အလုံအိုတ်သီု မမာန် တော်ဂွံ နကဵု အလ်ဂဝ်ရဳထမ် (Algorithm) ရ။ လညာတ်ဏအ်ဝွံ ကော်စ "Church-Turing Thesis" ရ။ ယဝ်ရ ပြသၞာ မွဲ သောင်ကလး နကဵု စက် တူရိန် ဟွံမာန် မ္ဂး၊ ပြသၞာ ဂှ် ကောန်ပျူတာ လဵုမွဲ လေဝ် ပ္ဍဲ ဂၠးတိ ဏအ် သောင်ကလး ဟွံမာန် ရ။
၇။ ချောမ်စကဳ ဟာဲရာကဳ (Chomsky Hierarchy)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ချောမ်စကဳ ဟာဲရာကဳ ဝွံ ဒှ် ပရေင်ပါ်ကရေက် သဒ္ဒါ ကေုာံ အရေဝ်ဘာသာ နကဵု အစောံသတ္တိ စက် အဝ်တဝ်မာတာ ရ။ ဍေဟ်ဝွံ ဒှ် သ္ၚိအင် မကိစ္စဇၞော်အိုတ် ပ္ဍဲ တဳအဝ်ရဳ အဝ်တဝ်မာတာ ရ။
| ကဆံင် | သဒ္ဒါ (Grammar) | အရေဝ်ဘာသာ (Language) | အဝ်တဝ်မာတာ (Automata) |
|---|---|---|---|
| Type-0 | သဒ္ဒါ ဟွံမဲ ကဵု အပိုတ်အခြာ (Unrestricted) | Recursively Enumerable | စက် တူရိန် (Turing Machine) |
| Type-1 | သဒ္ဒါ စပ်ကဵု သ္ၚိအင် (Context-sensitive) | Context-sensitive Language | လဳနဳယာ ဘံင်းဒေတ် အဝ်တဝ်မာတာ (LBA) |
| Type-2 | သဒ္ဒါ ဟွံမဲ ကဵု သ္ၚိအင် (Context-free) | Context-free Language | ပုရှ်ဒံင်း အဝ်တဝ်မာတာ (PDA) |
| Type-3 | သဒ္ဒါ ဓမ္မတာ (Regular) | Regular Language | ဖာဲနာက် အဝ်တဝ်မာတာ (FSM / FA) |
သ္ၚိအင် ဏအ်ဝွံ ထ္ၜးကဵု ဒဒှ်ရ Type-0 ဂှ် နွံကဵု အစောံသတ္တိ ဇၞော်အိုတ် တုဲ မာန် ထိင်ဒဝ် အရေဝ်ဘာသာ သီုဖအိုတ် ရ။ Type-3 ဂှ် နွံ အစောံသတ္တိ ဍောတ်အိုတ် ဆဂး လၟေင်ကမၠောန် တော်ဂွံ ပြဟ်အိုတ် ရ။[၄]
၈။ အပလီကေယှေန် ကေုာံ လွပ် (Applications and Usage)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]တဳအဝ်ရဳ အဝ်တဝ်မာတာ ဂှ် ၜိုန်ရ ဒှ် ဘာသာ သင်္ချာ အာဗ်သတြက် ကီုလေဝ်၊ ဍေဟ် နွံကဵု လွပ် မလှဲလး ပ္ဍဲကဵု ကွတ် ကောန်ပျူတာ ရ -
- သၞောတ် ပရဝ်ဂရာမ် ကေုာံ ကောန်ပျာင်လာ: PDA ကေုာံ FA တအ်ဂှ် စကာ ဗွဲမလှဲလး သွက်ဂွံ ပါ်ပါဲ (Lexical analysis) ကေုာံ စၟတ်သမ္တီ သဒ္ဒါ (Parsing) ပ္ဍဲ ကောန်ပျာင်လာ တအ် ရ။
- ရေဂူလာ အက်စ်ပရက်ယှေန် (Regular Expressions): မဒှ် သၞောတ် သွက်ဂွံ ဂၠာဲ မလိက် ပ္ဍဲ Text editors (ဥပမာ `grep` ပ္ဍဲ Unix) ဂှ် ဒုင်သဇိုင် လတူ FA ရ။
- ဒီဇိုင်း ဟာတ်ဝလ် (Hardware Design): သၞောတ် စက် ဖာဲနာက် (Finite state machines) ဂှ် စကာ သွက်ဂွံ ဓဇက် ဒီဇိုင်း သၞောတ် ဒဳဂျဳတေဝ် (Digital circuits) ကေုာံ CPU တအ် ရ။
- ပရေင်လ္ၚတ် အရေဝ်ဘာသာ သဘာဝ (NLP): သဒ္ဒါ Context-free တအ်ဂှ် စကာ သွက်ဂွံ သ္ၚေဝ်ဂၠေပ် လဒက်ပတန် ဝါကျ ပ္ဍဲ အရေဝ်ဘာသာ ကောန်မၞိဟ် ရ။
၉။ တဳအဝ်ရဳ ပရေင်ချပ်ဂၞန် ကေုာံ အဝ်တဝ်မာတာ (Computational Complexity and Automata)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]တဳအဝ်ရဳ အဝ်တဝ်မာတာ ဝွံ ဆက်စပ် ဒၟံင် ကု တဳအဝ်ရဳ ပရေင်ချပ်ဂၞန် (Computational Complexity Theory) ဗွဲမဇြိုဟ်နက် ရ။ တဳအဝ်ရဳ ဏအ်ဝွံ သ္ၚေဝ်ဂၠေပ် ဒဒှ်ရ "ပြသၞာ မွဲ တော်ဂွံ မာန် ဟာ" (Decidability) ကေုာံ "တော်ဂွံ ပြဟ် ဗလိုင်လဵု ရော" (Complexity) ရ။
ဥပမာ မပြာကတ်အိုတ် ဂှ် ဒှ် ပြသၞာ ဟောလ်တေန် (Halting Problem) မဒှ် အရာ မဟီုတွံ ဒဒှ်ရ "စက် တူရိန် လဵုမွဲ လေဝ် ဟွံမာန် တီ ကိုပ်ကၠာ ဒဒှ်ရ ပရဝ်ဂရာမ် မွဲမွဲ ဂှ် ဒေါအ် အာ (Halt) ဟွံသေင်မ္ဂး ကၠောန် အာ ဟွံမဲ အပိုတ်အခြာ (Infinite loop) ရော ဂှ်ရ"။ သဳအိုရဳ ဏအ်ဝွံ ထ္ၜးကဵု ပယျဵု အစောံသတ္တိ (Limitations) ကောန်ပျူတာ သီုဖအိုတ် လတူ ဂၠးတိ ဏအ် ရ。[၅]
၁၀။ အနာဂတ် ကေုာံ ပရေင်သုတေသန (Future and Research)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ပ္ဍဲကဵု ခေတ်လၟုဟ်၊ ပရေင်သုတေသန ပ္ဍဲ တဳအဝ်ရဳ အဝ်တဝ်မာတာ ဂှ် ဆက်တုဲ ဇၞော်မောဝ် အာ ဒၟံင် ဏီ ရ။ လညာတ် တၟိ တၟိ ဂမၠိုင် မပ္တံကဵု-
- ကွမ်တမ် အဝ်တဝ်မာတာ (Quantum Automata): လ္ၚတ် ပရူ မဝ်ဒယ် အဝ်တဝ်မာတာ မဒုင်သဇိုင် လတူ ရူပဗေဒ ကွမ်တမ် သွက်ဂွံ တော်ဂၞန် ဗွဲမပြဟ် ရ။
- သေလူလာ အဝ်တဝ်မာတာ (Cellular Automata): မဝ်ဒယ် မထ္ၜးကဵု ပရေင်ဇၞော်မောဝ် သၞောတ် ထုဲထံင် (Complex systems) ဥပမာ Conway's Game of Life ရ။
- AI ကေုာံ အဝ်တဝ်မာတာ: တၠပညာ တအ် ဂစာန် ပံင်ကောံ လညာတ် ဇာဇၞိက် ဉာဏ် ဇြိုဟ်နက် (Deep learning) ကေုာံ အဝ်တဝ်မာတာ သွက်ဂွံ ဖန်ဗဒှ် သၞောတ် AI မနွံကဵု ယုတ္တိဗေဒ ကေုာံ လဒက်ပတန် မခိုင်ကၠိုက် ရောင်။
နိဿဲဂမၠိုင်
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]- ↑ Sipser, M. (2012). Introduction to the Theory of Computation, 3rd, Cengage Learning, 31-35။
- ↑ Hopcroft, J. E. (2006). Introduction to Automata Theory, Languages, and Computation, 3rd, Addison-Wesley, 1-10။
- ↑ Turing, A. M. (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society s2-42 (1): 230-265.
- ↑ Chomsky, N. (1956). "Three models for the description of language". IRE Transactions on Information Theory 2 (3): 113-124.
- ↑ Martin, J. C. (2010). Introduction to Languages and the Theory of Computation, 4th, McGraw-Hill, 250-255။
ဆက်ဗှ်လ္ၚတ်
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]- သိပ္ပံ ကောန်ပျူတာ (Computer science)
- သိပ္ပံကောန်ပျူတာ မဆေင်ကဵု တဳအဝ်ရဳ (Theoretical computer science)
- စက် တူရိန် (Turing machine)
- အရေဝ်ဘာသာ ပွံက် (Formal language)
- အလ်ဂဝ်ရဳထမ် (Algorithm)