एक आरई से एफए का निर्माण
हम एक नियमित अभिव्यक्ति से एक Finite Automaton का पता लगाने के लिए थॉम्पसन के निर्माण का उपयोग कर सकते हैं। हम छोटी अभिव्यक्ति को नियमित अभिव्यक्ति में कम कर देंगे और इन्हें एनएफए और अंत में डीएफए में परिवर्तित कर देंगे।
कुछ मूल आरए भाव निम्नलिखित हैं -
Case 1 - एक नियमित अभिव्यक्ति 'ए' के लिए, हम निम्नलिखित एफए का निर्माण कर सकते हैं -
Case 2 - एक नियमित अभिव्यक्ति 'अब' के लिए, हम निम्नलिखित एफए का निर्माण कर सकते हैं -
Case 3 - एक नियमित अभिव्यक्ति (ए + बी) के लिए, हम निम्नलिखित एफए का निर्माण कर सकते हैं -
Case 4 - एक नियमित अभिव्यक्ति (a + b) * के लिए, हम निम्नलिखित FA का निर्माण कर सकते हैं -
तरीका
Step 1 दिए गए नियमित अभिव्यक्ति से नल चाल के साथ एक NFA का निर्माण करें।
Step 2 NFA से Null ट्रांस्फ़ॉर्म निकालें और इसे इसके बराबर DFA में परिवर्तित करें।
Problem
निम्नलिखित RA को इसके समकक्ष DFA - 1 (0 + 1) * 0 में बदलें
Solution
हम तीन अभिव्यक्ति "1", "(0 + 1) *" और "0"
अब हम निकाल देंगे εसंक्रमण। हम निकालने के बादε NDFA से परिवर्तन, हमें निम्नलिखित मिलते हैं -
यह RE - 1 (0 + 1) * के अनुरूप एक NDFA है। 0. यदि आप इसे DFA में बदलना चाहते हैं, तो अध्याय 1 में चर्चा किए गए NDFA को DFA में परिवर्तित करने की विधि को लागू करें।
पतले चाल के साथ परिमित ऑटोमेटा (NFA-N)
शून्य चाल के साथ एक परिमित ऑटोमेटन (एफए-trans) वर्णमाला सेट से इनपुट देने के बाद ही नहीं, बल्कि बिना किसी इनपुट प्रतीक के भी पारगमन करता है। बिना इनपुट के यह संक्रमण कहा जाता हैnull move।
NFA-N को औपचारिक रूप से 5-ट्यूपल (Q, ε, δ, q 0 , F) द्वारा दर्शाया जाता है , जिसमें से
Q - राज्यों का एक निर्धारित सेट
∑ - इनपुट प्रतीकों का एक परिमित सेट
δ- एक संक्रमण फ़ंक्शन a: Q × (transition ε {)}) → 2 क्यू
q0- एक प्रारंभिक अवस्था क्ष 0 ∈ क्यू
F - Q (F )Q) के अंतिम राज्य / राज्यों का एक सेट।
उपरोक्त (FA-ε) एक स्ट्रिंग सेट स्वीकार करता है - {0, 1, 01}
परिमित ऑटोमेटा से नल चाल को हटाना
अगर एक NDFA में, to- मूव X के बीच,-वर्टेक्स Y के लिए,-मूव है, तो हम इसे निम्न चरणों का उपयोग करके हटा सकते हैं -
- Y से सभी आउटगोइंग किनारों का पता लगाएं।
- किनारे से लेबल को बदले बिना X से शुरू होने वाले इन सभी किनारों को कॉपी करें।
- यदि X एक प्रारंभिक अवस्था है, तो Y को भी प्रारंभिक अवस्था बनाएं।
- यदि Y एक अंतिम स्थिति है, तो X को भी अंतिम स्थिति बनाएं।
Problem
Null के बिना NFA-without को NFA में बदलें।
Solution
Step 1 -
यहाँ is संक्रमण है q1 तथा q2, तो चलो q1 है X तथा qf है Y।
यहाँ q f से आउटगोइंग किनारों को 0 और 1 इनपुट के लिए q f है ।
Step 2 -
अब हम q f से किनारों को बदले बिना q 1 से इन सभी किनारों को कॉपी करेंगे और निम्नलिखित एफए प्राप्त करेंगे -
Step 3 -
यहाँ q 1 एक प्रारंभिक अवस्था है, इसलिए हम q f को भी प्रारंभिक अवस्था बनाते हैं ।
तो एफए बन जाता है -
Step 4 -
यहाँ q f एक अंतिम अवस्था है, इसलिए हम q 1 को भी एक अंतिम स्थिति बनाते हैं ।
तो एफए बन जाता है -
