Finite automata: परिमित राज्य मशीन में राज्यों का एक सीमित सेट होता है और यह संक्रमण फ़ंक्शन (δ) के अनुसार राज्यों को बदलता है और इनपुट को संसाधित करता है और आउटपुट फ़ंक्शन (𝜆) के आधार पर आउटपुट उत्पन्न करता है। यहां हम दो ऐसी परिमित राज्य मशीनों, मीली और मूर मशीन पर चर्चा करेंगे जो आमतौर पर गणना के सिद्धांत में उपयोग की जाती हैं।
गणना के सिद्धांत में, एक महत्वपूर्ण अवधारणा परिमित राज्य मशीन है। यह गणना का एक मॉडल है जिसका उपयोग सिस्टम को डिजाइन करने के लिए किया जाता है।
मैली मशीन
मीली मशीन एक सीमित अवस्था वाली मशीन है जिसका आउटपुट वर्तमान स्थिति और संबंधित इनपुट मूल्य पर निर्भर करता है। मैली मशीन को (Q, q0, 𝛴, O, δ, 𝜆) के रूप में परिभाषित किया गया है जहां
क्यू मीली मशीन की परिमित अवस्थाओं का एक समूह है
q0 प्रारंभिक अवस्था है (प्रारंभिक अवस्था)
𝛴 इनपुट वर्णमाला है
O आउटपुट वर्णमाला है
δ संक्रमण फलन है (Q*𝛴 → Q)
𝜆 आउटपुट फ़ंक्शन है (Q*𝛴 → O)
मूर मशीन
मीली मशीन एक सीमित अवस्था वाली मशीन है जिसका आउटपुट केवल वर्तमान स्थिति पर निर्भर करता है। मूर मशीन को (Q, q0, 𝛴, O, δ, 𝜆) के रूप में परिभाषित किया गया है जहां
क्यू मीली मशीन की परिमित अवस्थाओं का एक समूह है
q0 प्रारंभिक अवस्था है (प्रारंभिक अवस्था)
𝛴 इनपुट वर्णमाला है
O आउटपुट वर्णमाला है
δ संक्रमण फलन है (Q*𝛴 → Q)
𝜆 आउटपुट फ़ंक्शन है (Q → O)
संक्रमण तालिका का उपयोग करके मीली मशीन का मूर मशीन में रूपांतरण –
इस रूपांतरण प्रक्रिया में हम मीली मशीन के एक राज्य q को कई राज्यों के साथ विभाजित करते हैं, ऐसे राज्यों की संख्या राज्य q से जुड़े विभिन्न आउटपुट की संख्या के बराबर होती है।
अतिरिक्त राज्यों को जोड़ने के बाद, जब हम पाते हैं कि राज्य q से जुड़ा आउटपुट तालिका में हर जगह समान है, तो हम आउटपुट को राज्य q के आउटपुट के रूप में जोड़ते हैं (यानी मूर मशीन में आउटपुट केवल वर्तमान स्थिति पर निर्भर करता है)।
स्तंभों को विभाजित करने के बाद, हमें एक समतुल्य मूर मशीन प्राप्त होती है।
DFA (नियतात्मक परिमित ऑटोमेटा) –
DFA नियतात्मक परिमित ऑटोमेटा को संदर्भित करता है। नियतिवाद का तात्पर्य गणना की विशिष्टता से है। यदि मशीन एक समय में एक इनपुट स्ट्रिंग एक प्रतीक को पढ़ती है तो परिमित ऑटोमेटा को नियतात्मक परिमित ऑटोमेटा कहा जाता है।
DFA में, वर्तमान स्थिति से अगली स्थिति तक विशिष्ट इनपुट के लिए केवल एक ही रास्ता है।
DFA शून्य चाल को स्वीकार नहीं करता है, यानी, DFA किसी भी इनपुट चरित्र के बिना स्थिति नहीं बदल सकता है।
DFA में कई अंतिम स्थितियाँ शामिल हो सकती हैं। इसका उपयोग कंपाइलर में लेक्सिकल विश्लेषण में किया जाता है।
NDFA –
NDFA में, एक विशेष इनपुट प्रतीक के लिए, मशीन मशीन में राज्यों के किसी भी संयोजन में जा सकती है। दूसरे शब्दों में, मशीन जिस सटीक स्थिति में चलती है उसे निर्धारित नहीं किया जा सकता है। इसलिए, इसे गैर-नियतात्मक ऑटोमेटन कहा जाता है। चूंकि इसमें राज्यों की संख्या सीमित है, इसलिए मशीन को गैर-नियतात्मक परिमित मशीन या गैर-नियतात्मक परिमित ऑटोमेटन कहा जाता है।
NDFA की औपचारिक परिभाषा
एक NDFA को 5-ट्यूपल (क्यू, ∑, δ, क्यू0, एफ) द्वारा दर्शाया जा सकता है जहां –
Q राज्यों का एक सीमित समूह है।
∑ प्रतीकों का एक सीमित सेट है जिसे अक्षर कहा जाता है।
δ संक्रमण फ़ंक्शन है जहां δ: Q × ∑ → 2Q
(यहां Q (2Q) का पावर सेट लिया गया है क्योंकि NDFA के मामले में, एक राज्य से, Q राज्यों के किसी भी संयोजन में संक्रमण हो सकता है)
q0 प्रारंभिक अवस्था है जहां से कोई भी इनपुट संसाधित होता है (q0∈ Q)।
F, Q (F ⊆ Q) की अंतिम अवस्था/अवस्थाओं का एक समूह है।
NDFA का ग्राफिकल प्रतिनिधित्व: (डीएफए के समान)
एक NDFA को डिग्राफ द्वारा दर्शाया जाता है जिसे राज्य आरेख कहा जाता है।
शीर्ष राज्यों का प्रतिनिधित्व करते हैं।
इनपुट वर्णमाला के साथ लेबल किए गए चाप संक्रमण दिखाते हैं।
प्रारंभिक अवस्था को एक खाली एकल आने वाले चाप द्वारा दर्शाया जाता है।
अंतिम अवस्था को दोहरे वृत्तों द्वारा दर्शाया गया है।
उदाहरण
मान लीजिए कि एक गैर-नियतात्मक परिमित ऑटोमेटन → है
क्यू = {ए, बी, सी}
∑ = {0, 1}
q0= {a}
एफ = {सी}
अक्सर पूछे जाने वाले प्रश्न –
एक परिमित राज्य मशीन क्या है?
एक परिमित राज्य मशीन गणना का एक मॉडल है जिसमें राज्यों का एक सीमित सेट होता है और इसका कार्य क्रमशः दो कार्यों, संक्रमण फ़ंक्शन और आउटपुट फ़ंक्शन द्वारा परिभाषित होता है।
मीली मशीन मूर मशीन से किस प्रकार भिन्न है?
मीली मशीन एक परिमित राज्य मशीन है जिसका आउटपुट वर्तमान स्थिति के साथ-साथ संबंधित इनपुट मूल्य पर निर्भर करता है, हालांकि मूर मशीन एक सीमित राज्य मशीन है जिसका आउटपुट केवल वर्तमान स्थिति पर निर्भर करता है।
एक संक्रमण फलन क्या है?
एक ट्रांज़िशन फ़ंक्शन एक ऐसा फ़ंक्शन है जो वर्तमान स्थिति और इनपुट मान के आधार पर एक ऑटोमेटन की एक राज्य से दूसरे राज्य में गति को निर्धारित करता है और आउटपुट के रूप में ऑटोमेटन के लिए अगला राज्य प्रदान करता है।
निष्कर्ष
इस लेख में एक महत्वपूर्ण अवधारणा को शामिल किया गया है कि कैसे एक संक्रमण तालिका का उपयोग करके एक मीली मशीन को मूर मशीन में परिवर्तित किया जाता है।
हम आपको अपने सपनों की नौकरी पाने के लिए कंप्यूटर की बुनियादी बातों पर बेहतर पकड़ पाने के लिए yourqueries को विजिट करते रहिये।