Finite Automata
Finite Automata (FA) पैटर्न को पहचानने के लिए सबसे सरल मशीन है। Finite Automata या finite state machine एक अमूर्त मशीन है जिसमें पांच तत्व या टपल होते हैं। इसमें एक state से दूसरे state में जाने के लिए state और नियमों का एक समूह है, लेकिन यह लागू इनपुट प्रतीक पर निर्भर करता है। मूल रूप से यह डिजिटल कंप्यूटर का एक अमूर्त ( abstract)मॉडल है। निम्नलिखित आंकड़ा एक सामान्य स्वचालन की कुछ आवश्यक विशेषताओं को दर्शाता है।
उपरोक्त आंकड़ा ऑटोमेटा की निम्नलिखित विशेषताएं दिखाता है:
- Input
- Output
- States of automata
- State relation
- Output relation
एक परिमित ऑटोमेटा में निम्नलिखित शामिल हैं:
Finite Automata
मशीन का औपचारिक विनिर्देश है
{ Q, Σ, q, F, δ }.
types of finite automata
एफए को दो प्रकारों में वर्णित किया गया है:
- 1) Deterministic Finite Automata (DFA)
Deterministic Finite Automata
एक डीएफए में, एक विशेष इनपुट कैरेक्टर के लिए, मशीन केवल एक state में जाती है। प्रत्येक इनपुट प्रतीक के लिए प्रत्येक state पर एक संक्रमण फ़ंक्शन परिभाषित किया गया है। इसके अलावा डीएफए नल (या ε) चाल की अनुमति नहीं है, यानी, डीएफए बिना किसी इनपुट कैरेक्टर के state नहीं बदल सकता है।
उदाहरण के लिए, = {0, 1} के साथ DFA के नीचे, 0 से समाप्त होने वाली सभी स्ट्रिंग्स को स्वीकार करता है।
deterministic finite automata examples
ध्यान देने वाली एक महत्वपूर्ण बात यह है कि एक पैटर्न के लिए कई संभावित डीएफए हो सकते हैं। states की न्यूनतम संख्या वाला डीएफए आमतौर पर पसंद किया जाता है।
- 2) Nondeterministic Finite Automata(NFA)
निम्नलिखित अतिरिक्त सुविधाओं को छोड़कर एनएफए डीएफए के समान है:
1. शून्य (या ε) चाल की अनुमति है यानी, यह प्रतीकों को पढ़े बिना आगे बढ़ सकता है।
2. किसी विशेष इनपुट के लिए किसी भी संख्या में राज्यों को प्रेषित करने की क्षमता।
हालाँकि, ये उपरोक्त सुविधाएँ NFA में कोई शक्ति नहीं जोड़ती हैं। यदि हम दोनों की तुलना शक्ति के संदर्भ में करें, तो दोनों समान हैं।
उपरोक्त अतिरिक्त सुविधाओं के कारण, एनएफए का एक अलग संक्रमण कार्य है, बाकी डीएफए के समान है।
Nondeterministic Finite Automata
जैसा कि आप ट्रांजिशन फंक्शन में देख सकते हैं, नल (या ) सहित किसी भी इनपुट के लिए, एनएफए किसी भी राज्य की संख्या में जा सकता है।
उदाहरण के लिए, उपरोक्त समस्या के लिए नीचे एक NFA है
Nondeterministic Finite Automata
ध्यान देने वाली एक महत्वपूर्ण बात यह है कि एनएफए में, यदि इनपुट स्ट्रिंग के लिए कोई पथ अंतिम स्थिति की ओर जाता है, तो इनपुट स्ट्रिंग स्वीकार की जाती है। उदाहरण के लिए, उपरोक्त एनएफए में, इनपुट स्ट्रिंग "00" के लिए कई पथ हैं। चूंकि, पथों में से एक अंतिम स्थिति की ओर जाता है, "00" उपरोक्त एनएफए द्वारा स्वीकार किया जाता है।
- Justification:
चूंकि डीएफए और एनएफए में सभी टुपल्स समान हैं, टुपल्स में से एक को छोड़कर, जो ट्रांजिशन फंक्शन (δ) है
अब यदि आप निरीक्षण करें तो आप पाएंगे कि Q X Σ -> Q, Q X Σ -> 2^Q का भाग है।
आरएचएस पक्ष में, Q, 2^Qका सबसेट है जो इंगित करता है कि क्यू 2^Q में शामिल है या Q, 2^Q का हिस्सा है, हालांकि, रिवर्स सत्य नहीं है। इसलिए गणितीय रूप से, हम यह निष्कर्ष निकाल सकते हैं कि प्रत्येक DFA NFA है, लेकिन इसके विपरीत नहीं। फिर भी एनएफए को डीएफए में बदलने का एक तरीका है, इसलिए प्रत्येक एनएफए के लिए एक समान डीएफए मौजूद है।
1. एनएफए और डीएफए दोनों में समान शक्ति है और प्रत्येक एनएफए को डीएफए में अनुवादित किया जा सकता है।
2. DFA और NFA दोनों में कई अंतिम अवस्थाएँ हो सकती हैं।
3. एनएफए एक सैद्धांतिक अवधारणा से अधिक है।
4. डीएफए का उपयोग कंपाइलर में लेक्सिकल एनालिसिस में किया जाता है।
finite automata applications
- एक संकलक के शाब्दिक विश्लेषण के डिजाइन के लिए।
- नियमित अभिव्यक्तियों का उपयोग करके पैटर्न को पहचानने के लिए।
- मीली और मूर मशीनों का उपयोग करके संयोजन और अनुक्रमिक सर्किट की डिजाइनिंग के लिए।
- पाठ संपादकों में प्रयुक्त।
- वर्तनी जांचकर्ताओं के कार्यान्वयन के लिए।
No comments:
Post a Comment