✖

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

पिछले अध्यायों में प्रस्तुत परिमित ऑटोमेटा (संक्षेप में FA या DFA) हमेशा नियतात्मक था: हर क्षण स्पष्ट था कि ऑटोमेटा क्या करेगा। अब हम अनियतात्मक परिमित ऑटोमेटा (non-deterministic finite automaton, संक्षेप में NFA) की अधिक व्यापक संकल्पना देखेंगे। इसमें ऐसे संक्रमण हो सकते हैं, जो एक ही अवस्था से निकलते हैं और एक ही प्रतीक के लिए होते हैं।

उदाहरण

ऑटोमेटा का यह आरेख देखिए:

इसमें विशेष क्या है? यह कि नोड q0 से प्रतीक 0 के लिए दो किनारे निकलते हैं। इसलिए यदि हम स्ट्रिंग 001 को स्वीकार करने का प्रयास करें, तो लगेगा कि ऑटोमेटा को पता नहीं होगा कि उसे अवस्था q0 में रहना है या q1 में जाने वाले संक्रमण का अनुसरण करना है। ऐसा ऑटोमेटा अनियतात्मक होगा।

इस अर्थ में नियतात्मकता का मतलब है कि हर स्थिति में स्पष्ट है कि ऑटोमेटा क्या करेगा; अस्पष्टता की कोई गुंजाइश नहीं है। नियतात्मक ऑटोमेटा में प्रत्येक अवस्था और प्रत्येक प्रतीक के लिए केवल एक संक्रमण होता है। अनियतात्मकता का अर्थ है अस्पष्टता — एक अवस्था से एक ही प्रतीक के लिए, मान लीजिए, तीन संक्रमण निकल सकते हैं।

तो ऑटोमेटा निर्णय कैसे लेता है? अनियतात्मक ऑटोमेटा हमेशा वही संक्रमण चुनता है (कभी-कभी हम कहते हैं “अनुमान लगाता है”), जिससे स्ट्रिंग स्वीकार हो जाए; यदि ऐसा संभव हो।

यदि हम ऑटोमेटा को स्ट्रिंग 001 दें, तो स्ट्रिंग के साथ ऑटोमेटा के पास ये विकल्प हैं:

q0→q0→q0→q0q0→q0→q1→q2

साथ ही वे विकल्प भी, जिनमें वह पूरी स्ट्रिंग नहीं पढ़ पाता। पहले विकल्प में वह लगातार अवस्था q0 में रहा, जो वह निश्चित रूप से कर सकता है, संक्रमण के नियम इसकी अनुमति देते हैं। दूसरी शाखा में उसने आगे की अवस्थाओं में जाने का साहस किया और अंत में अवस्था q2 में पहुँचा, जो अंतिम अवस्था है। इस शाखा में ऑटोमेटा स्ट्रिंग स्वीकार कर लेता। अनियतात्मक ऑटोमेटा अपने-आप हमेशा वही शाखा चुनता है, जिसमें वह स्ट्रिंग स्वीकार करता है, यदि ऐसी शाखा मौजूद हो।

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

ऑटोमेटा के अभिकलन का वृक्ष निरूपण

पिछले ऑटोमेटा में थोड़ा परिवर्तन करते हैं:

अनियतात्मकता पहली अवस्था में बनी रहती है। पिछला ऑटोमेटा उन सभी स्ट्रिंगों को स्वीकार करता था, जो 01 पर समाप्त होती हैं। यह संशोधित ऑटोमेटा उन सभी स्ट्रिंगों को स्वीकार करता है, जिनमें उप-स्ट्रिंग 01 है। इसलिए यह, उदाहरण के लिए, स्ट्रिंग 101 या 0101 स्वीकार करता है। अभिकलन की सभी शाखाओं को हम एक वृक्ष से आसानी से दिखा सकते हैं; उदाहरण के लिए, स्ट्रिंग 01010 के लिए वृक्ष कुछ ऐसा हो सकता है:

शुरुआत में हम प्रारंभिक अवस्था q0 में हैं। इनपुट पर स्ट्रिंग 01010 है, पहला न पढ़ा गया अक्षर 0 है। अवस्था q0 से प्रतीक 0 के लिए दो संक्रमण निकलते हैं, अवस्थाओं q0 और q1 में। इसलिए वृक्ष में इस नोड के दो संतान होंगे: q0 और q1। आगे हम प्रतीक 1 पढ़ते हैं। यहाँ कोई अस्पष्टता नहीं है, हम अवस्थाओं q0 और q2 में जाते हैं। फिर हम अक्षर 0 पढ़ते हैं; बाईं शाखा में फिर अस्पष्टता आती है और हम अभिकलन को दो और शाखाओं में बाँट देते हैं। एक में हम फिर q0 में रहते हैं और दूसरी में q1 में जाते हैं। इसी प्रकार आगे।

ध्यान दीजिए कि कुल दो शाखाएँ अवस्था q2 में, यानी अंतिम अवस्था में, समाप्त होती हैं। अभिकलन की दो शाखाएँ हैं, जिनसे ऑटोमेटा दी गई स्ट्रिंग स्वीकार कर सकता है। इसलिए यह ऑटोमेटा स्ट्रिंग 01010 स्वीकार कर लेगा। आइए, स्ट्रिंग 1000 के लिए भी ऐसा ही वृक्ष बनाएँ।

अभिकलन या तो अवस्था q0 में रहता है या अवस्था q1 में जाता है, परंतु वहाँ से आगे जाने का कोई रास्ता नहीं है, क्योंकि इनपुट पर केवल शून्य बचे हैं और अवस्था q1 में केवल प्रतीक 1 के लिए संक्रमण है। अभिकलन की कोई भी शाखा अंतिम अवस्था में समाप्त नहीं होती, इसलिए ऑटोमेटा स्ट्रिंग 1000 स्वीकार नहीं करता।

एप्सिलॉन संक्रमण

अनियतात्मक ऑटोमेटा में हम एप्सिलॉन संक्रमण (epsilon transitions) का भी प्रयोग कर सकते हैं। ये ऐसे संक्रमण हैं, जिन्हें हम इनपुट पर कोई भी प्रतीक होने पर कर सकते हैं, और वह भी स्ट्रिंग से कोई प्रतीक पढ़े बिना। ऐसा अनियतात्मक ऑटोमेटा कैसे लिखें, जो रिक्त स्ट्रिंग, केवल 1 से बनी सभी स्ट्रिंगें और (10)n रूप की स्ट्रिंगें, अर्थात् 10, 1010, …, स्वीकार करे?

हमने ऑटोमेटा को दो “उप-ऑटोमेटा” में बाँट दिया है। ऊपर वाला 1 से बनी स्ट्रिंगों को पहचानता है, नीचे वाला (10)n रूप की स्ट्रिंगों को। आइए, स्ट्रिंग 111 को स्वीकार करने का प्रयास करें। शुरुआत में ऑटोमेटा अवस्था q0 में है और इनपुट पर स्ट्रिंग 111 है। उसके पास एप्सिलॉन संक्रमण हैं, इसलिए वह जैसा उसके लिए सुविधाजनक हो, अवस्था q1 या q2 में जाने का निर्णय ले सकता है। हम देखते हैं कि उसके लिए अवस्था q1 में जाना उपयोगी होगा। ऑटोमेटा वहाँ जाता है। इस दौरान इनपुट पर अब भी स्ट्रिंग 111 है! केवल अब वह स्ट्रिंग से प्रतीक पढ़ना शुरू करता है और अवस्था q1 से फिर q1 में जाता रहता है, जब तक पूरी स्ट्रिंग पढ़कर उसे स्वीकार नहीं कर लेता।

यदि हम 1010 को स्वीकार करने का प्रयास करें, तो ऑटोमेटा शुरुआत में अवस्था q2 में जाएगा और वहाँ से प्रतीकों को संसाधित करना शुरू करेगा; वह यह स्ट्रिंग भी स्वीकार कर लेगा।

स्ट्रिंग 1100 के लिए ऑटोमेटा कुछ भी करे, ऐसी स्ट्रिंग को वह किसी तरह स्वीकार नहीं कर सकता।

एप्सिलॉन संक्रमण और अनियतात्मकता हमारा काम कई तरह से आसान कर देते हैं। उदाहरण के लिए, इस बात की उपपत्ति कि रेगुलर भाषाओं का सम्मिलन फिर से रेगुलर भाषा है, एप्सिलॉन संक्रमणों के साथ नियतात्मक परिमित ऑटोमेटा वाली स्थिति की तुलना में बहुत सरलता से लिखी जा सकती है। उस उपपत्ति में हमारे पास इन ऑटोमेटा के उदाहरण थे

और

और फिर हमने एक नियतात्मक परिमित ऑटोमेटा बनाया था, जो दोनों भाषाओं के सम्मिलन को स्वीकार करता था। एप्सिलॉन संक्रमणों के साथ ऐसा ऑटोमेटा हम इस प्रकार बना सकते हैं:

बस एक नई प्रारंभिक अवस्था जोड़ दीजिए, उससे दो एप्सिलॉन संक्रमण दोनों पुराने ऑटोमेटा की प्रारंभिक अवस्थाओं में जाएँगे, और काम पूरा। ऑटोमेटा अनियतात्मक ढंग से तय करता है कि वह स्ट्रिंग को एक “उप-ऑटोमेटा” से स्वीकार करने का प्रयास करेगा या दूसरे से।

अनियतात्मक ऑटोमेटा की परिभाषा

हम दिखा चुके हैं कि नियतात्मक और अनियतात्मक परिमित ऑटोमेटा में क्या अंतर है; अब इसे केवल औपचारिक रूप देना बाकी है। नियतात्मक परिमित ऑटोमेटा को हमने 5-टपल ⟨Q, Σ, δ, q0, F⟩ के रूप में परिभाषित किया था, जहाँ Q अवस्थाओं का समुच्चय है, Σ वर्णमाला है, δ संक्रमण फलन है, q0 प्रारंभिक अवस्था है और F अंतिम अवस्थाओं का समुच्चय है। अनियतात्मक ऑटोमेटा की परिभाषा में केवल संक्रमण फलन की परिभाषा बदलती है।

नियतात्मक रूप में फलन कॉल δ(q, w) पर केवल एक अवस्था लौटा सकता था, जबकि अनियतात्मक रूप में वह कई अवस्थाएँ लौटा सकता है — यदि एक प्रतीक के लिए कई संक्रमण परिभाषित हों। हमें एप्सिलॉन संक्रमण भी परिभाषित करने हैं, इसलिए समुच्चय Σ ∪ {ε} को हम Σε से दर्शाते हैं, अर्थात् Σε = Σ ∪ {ε}। फलन δ को हम इस प्रकार परिभाषित करते हैं:

δ:Q×Σε→2Q

यहाँ 2Q घात समुच्चय है, यानी समुच्चय Q के सभी उपसमुच्चयों का समुच्चय। अभिकलन का औपचारिक रूप परिमित ऑटोमेटा जैसा ही है। ऑटोमेटा का विन्यास फिर से युग्म ⟨q, w⟩ ∈ Q × Σ∗ है। अभिकलन का चरण ↦ विन्यासों के समुच्चय पर ऐसा संबंध है कि

⟨qi,w0w1…wn⟩↦⟨qj,w1…wn⟩,

यदि और केवल यदि qj ∈ δ(qi, w0) हो। सबसे बड़ा अंतर इसी वाक्य में था। नियतात्मक ऑटोमेटा में यह प्रतिबंध qj = δ(qi, w0) के रूप में लिखा था, क्योंकि फलन δ हमेशा एक अवस्था लौटाता था। संक्रमण फलन का अनियतात्मक रूप अवस्थाओं का समुच्चय लौटाता है, इसलिए यहाँ संकेत ∈ है। संबंध के स्वतुल्य और संक्रामक संवरक को हम फिर ↦ ∗ से दर्शाएँगे। हम कहते हैं कि ऑटोमेटा स्ट्रिंग w को स्वीकार करता है, यदि और केवल यदि कोई ऐसा qf ∈ F मौजूद हो कि

⟨q0,w⟩↦∗⟨qf,ε⟩.

स्रोत

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