✖

अनियतात्मक ऑटोमेटा का अनुकरण

यदि हमारे पास अनियतात्मक ऑटोमेटा है और हम जानना चाहते हैं कि वह दी गई स्ट्रिंग को स्वीकार करता है या नहीं, तो हम ऑटोमेटा को नियतात्मक में बदल सकते हैं, किसी तरह आज़माकर देख सकते हैं, या ऐसे एल्गोरिद्म का प्रयोग कर सकते हैं, जो NFA के काम का अनुकरण (simulate) करे।

एल्गोरिद्म का सिद्धांत

सिद्धांत को हम एक उपयुक्त उदाहरण पर स्पष्ट रूप से दिखाएँगे। मान लीजिए यह ऑटोमेटा है:

यह एक अनियतात्मक परिमित ऑटोमेटा है, जो कोई भाषा स्वीकार करता है। कौन-सी, इससे अभी हमें कोई मतलब नहीं है। हम दिखाएँगे कि इनपुट स्ट्रिंग 11001 के लिए ऐसे ऑटोमेटा का अभिकलन कैसा दिख सकता है। विचार यह है: हम स्ट्रिंग से एक प्रतीक संसाधित करते हैं और देखते हैं कि एक ही प्रतीक के लिए बहु-संक्रमणों के कारण हम कहाँ-कहाँ जा सकते हैं। इन सभी अवस्थाओं को हम याद रख लेते हैं और अगले चरण में मानते हैं कि हम “इन सभी अवस्थाओं में एक साथ” हैं; तब हम देखते हैं कि इन अवस्थाओं से आगे कहाँ पहुँच सकते हैं।

इस प्रकार हम उन अवस्थाओं का समुच्चय याद रखेंगे, जिनमें हम हो सकते हैं, और स्ट्रिंग का न पढ़ा गया भाग भी। शुरुआत में हमारे पास युग्म ⟨{q0}, 11001⟩ है। हम अवस्था q0 (प्रारंभिक अवस्था) में शुरू करते हैं और इनपुट पर स्ट्रिंग 11001 है। ऑटोमेटा ऐसा दिखता है; जिस अवस्था में हम हैं, वह लाल रंग और मोटी रेखा से दिखाई गई है:

पहला प्रतीक 1 है। अवस्था q0 से प्रतीक 1 के लिए केवल एक संक्रमण है, इसलिए हम अवस्था q1 में पहुँचते हैं। हम युग्म ⟨{q1}, 1001⟩ याद रखते हैं। ऑटोमेटा ऐसा दिखता है:

आगे बढ़ते हैं। स्ट्रिंग का न पढ़ा गया भाग 1001 है, इसलिए हम फिर 1 के लिए संक्रमण ढूँढते हैं। अब ये दो हैं — वापस अवस्था q0 में और अवस्था q3 में। अब हम दोनों अवस्थाओं में एक साथ जाते हैं। इसलिए हम युग्म ⟨{q0, q3}, 001⟩ याद रखते हैं।

इसके पीछे तर्क क्या है? हम जानते हैं कि प्रारंभिक अवस्था से स्ट्रिंग 11 की सहायता से अवस्था q3 और अवस्था q0, दोनों में पहुँचने का रास्ता है। अभी हमें पता नहीं कि कौन-सी शाखा काम आएगी, इसलिए हम बस दोनों याद रख लेते हैं। आगे बढ़ते हैं। इनपुट पर प्रतीक 0 है। अब हमें q0 से निकलने वाले संक्रमण भी देखने हैं और q3 से निकलने वाले भी। अवस्था q0 से संक्रमण अवस्थाओं q1 और q2 में जाते हैं, अवस्था q3 से संक्रमण वापस q1 में जाता है। इन सभी अवस्थाओं को शामिल करने पर हमें युग्म ⟨{q1, q2}, 01⟩ मिलता है:

परंतु यह चरण अभी पूरा नहीं हुआ है। हम देखते हैं कि अवस्था q2 से एक एप्सिलॉन संक्रमण अवस्था q4 में जाता है। हम जानते हैं कि एप्सिलॉन संक्रमण पर हम अगला अक्षर पढ़े बिना “कभी भी जा सकते हैं”। दूसरे शब्दों में — इनपुट स्ट्रिंग से अगला प्रतीक पढ़े बिना हम अवस्था q4 में भी जा सकते हैं। इसलिए हम अवस्था q4 को उन अवस्थाओं में जोड़ देते हैं, जिनमें हम हो सकते हैं: ⟨{q1, q2, q4}, 01⟩। ऑटोमेटा को हम इस प्रकार रंगेंगे:

आगे इनपुट पर 0 है। हम देखते हैं कि जिन तीन अवस्थाओं में हम हैं, उनसे कहाँ जा सकते हैं। q1 से हम कहीं नहीं जा सकते, क्योंकि 0 के लिए संक्रमण नहीं है। इस शाखा में अभिकलन समाप्त हो जाता है। अवस्था q4 से भी हम कहीं नहीं पहुँचते। अवस्था q2 से हम वापस अवस्था q2 में पहुँचते हैं। परंतु अवस्था q2 से फिर एक एप्सिलॉन संक्रमण अवस्था q4 में जाता है, इसलिए हम अवस्था q4 में भी पहुँच सकते हैं। इस तरह अवस्थाओं के समुच्चय {q1, q2, q4} से प्रतीक 0 के लिए हम अवस्थाओं के समुच्चय {q2, q4} में पहुँच सकते हैं और हमें युग्म ⟨{q2, q4}, 1⟩ मिलता है:

अंत में इनपुट पर प्रतीक 1 है। अवस्था q2 से हम कहीं नहीं पहुँचते, इस शाखा में अभिकलन समाप्त हो जाता है। परंतु अवस्था q4 से हम अवस्थाओं q3 और q5 में पहुँचते हैं। हमें युग्म ⟨{q3, q5}, ε⟩ मिलता है:

अब ऑटोमेटा पूरी स्ट्रिंग पढ़ चुका है और दो अवस्थाओं q3, q5 में “है”। इनमें से कम से कम एक अंतिम अवस्था है, इसलिए ऑटोमेटा स्ट्रिंग 11001 को स्वीकार करता है।

एल्गोरिद्म

सबसे पहले हमें एक ऐसा फलन चाहिए, जो प्राचल के रूप में अवस्थाओं का समुच्चय ले और ज्ञात करे कि एप्सिलॉन संक्रमणों की सहायता से हम और किन अवस्थाओं में पहुँच सकते हैं। इस प्रकार इनपुट ऑटोमेटा ⟨Q, Σ, δ, q0, F⟩ और अवस्थाओं का समुच्चय States है, और आउटपुट इन अवस्थाओं का वह अधिसमुच्चय है, जिसकी अवस्थाओं तक एप्सिलॉन संक्रमणों से पहुँचा जा सकता है। इस संक्रिया को हम समुच्चय States का एप्सिलॉन संवरक (ε-closure) कहेंगे।

FunctionEpsilonClosure(⟨Q,Σ,δ,q0,F⟩,States)NextStates←∅ForEachq∈StatesDoNextStates←NextStates∪{q}∪δ(q,ε)EndForIfNextStates∖States=∅DoReturnStatesElseReturnEpsilonClosure(⟨Q,Σ,δ,q0,F⟩,NextStates)EndIfEndFunction

इस फलन का प्रयोग हम उस फलन में करेंगे, जो अनियतात्मक ऑटोमेटा के काम का अनुकरण करेगा। इनपुट ऑटोमेटा, इनपुट स्ट्रिंग w = w1w2… wn और उन अवस्थाओं का समुच्चय है, जिनमें ऑटोमेटा इस समय है। आउटपुट उत्तर YES (हाँ) या NO (नहीं) है, इस पर निर्भर करते हुए कि ऑटोमेटा दी गई स्ट्रिंग स्वीकार करता है या नहीं।

FunctionComputeNFA(⟨Q,Σ,δ,q0,F⟩,w,States)Ifw=ϵDoIfStates∩F≠∅DoReturnYESElseReturnNOEndIfEndIfNextStates←∅ForEachq∈StatesDoNextStates←NextStates∪δ(q,w1)EndForNextStates←EpsilonClosure(⟨Q,Σ,δ,q0,F⟩,NextStates)ReturnComputeNFA(⟨Q,Σ,δ,q0,F⟩,w2w3…wn,NextStates)EndFunction

यदि हम जाँचना चाहते हैं कि ऑटोमेटा स्ट्रिंग w स्वीकार करता है या नहीं, तो फलन को इस प्रकार कॉल करते हैं: ComputeNFA(⟨Q, Σ, δ, q0, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q0, F⟩, {q0}))।

स्रोत

विषय-सूची: परिमित ऑटोमेटा, पूर्ण ऑटोमेटा, अनियतात्मक परिमित ऑटोमेटा, अनियतात्मक ऑटोमेटा का अनुकरण, NFA का DFA में रूपांतरण