परिमित ऑटोमेटा
परिमित ऑटोमेटा (अंग्रेज़ी में finite state machine या finite automaton) एक आदिम कंप्यूटर का अभिकलन मॉडल है। यह कुछ अवस्थाओं (states) और कुछ संक्रमणों (transitions) से बना होता है और दी गई स्ट्रिंग को स्वीकार या अस्वीकार कर सकता है।
उदाहरण
अनौपचारिक रूप से हम परिमित ऑटोमेटा का वर्णन अवस्था आरेख की सहायता से करेंगे:
ऑटोमेटा अवस्थाओं से बना है; आकृति में ये तीन गोल अवस्थाएँ q0, q1 और q2 हैं। इन अवस्थाओं के बीच संक्रमण हैं, यानी वे तीर। ऑटोमेटा में एक प्रारंभिक अवस्था भी होनी चाहिए, यहाँ यह अवस्था q0 है। प्रारंभिक अवस्था को प्रायः ऐसे दिखाते हैं कि उसकी ओर एक तीर आता है, जो किसी अवस्था से नहीं निकलता। इसके अलावा ऑटोमेटा में सामान्यतः एक अंतिम अवस्था होती है, जिसे हम दोहरी रेखा से दिखाते हैं; आकृति में यह अवस्था q2 है।
इस तरह बना ऑटोमेटा कुछ स्ट्रिंगों को स्वीकार करता है। हम ऑटोमेटा को स्ट्रिंगें देते हैं और ऑटोमेटा उन्हें स्वीकार करने का प्रयास करता है। यदि वह स्ट्रिंग स्वीकार कर ले, तो उत्तर देता है हाँ, अन्यथा नहीं। हमारा ऑटोमेटा अक्षरों “a, b, c” से बनी स्ट्रिंगों को स्वीकार करने का प्रयास करता है, इसलिए हम स्ट्रिंग “abbc” आज़मा सकते हैं।
हम प्रारंभिक अवस्था q0 में शुरू करते हैं और इनपुट पर स्ट्रिंग “abbc” है। आगे हम तीरों के अनुसार चलेंगे।
स्ट्रिंग को हम सामान्य ढंग से बाएँ से दाएँ पढ़ते हैं, यानी सबसे पहले प्रतीक “a” लेंगे। इनपुट “a” का तीर अवस्था q1 में जाता है, इसलिए हम वहाँ पहुँचते हैं और स्ट्रिंग से प्रतीक “a” हटा देते हैं। अब इनपुट पर स्ट्रिंग “bbc” है:
इनपुट “b” का तीर वापस नोड q1 की ओर जाता है। फिर से हम पहला अक्षर हटाते हैं और इनपुट पर स्ट्रिंग “bc” रह जाती है। हम फिर अवस्था q1 में ही रहते हैं। अंत में इनपुट पर स्ट्रिंग “c” है। अवस्था q1 से इनपुट “c” का तीर हमें अवस्था q2 में भेजता है।
इनपुट स्ट्रिंग के सभी अक्षर समाप्त हो चुके हैं और हम अवस्था q2 में हैं, जो अंतिम अवस्था है। इसलिए यह परिमित ऑटोमेटा स्ट्रिंग “abbc” को स्वीकार करता है।
यदि अंत में हम स्वीकारक अवस्था में न होते, तो ऑटोमेटा स्ट्रिंग को स्वीकार न करता। इसी तरह ऑटोमेटा स्ट्रिंग को तब भी स्वीकार नहीं करता, जब किसी अवस्था से आगे जाने का कोई रास्ता न हो। उदाहरण के लिए, इनपुट “ab” पर हम अवस्था q1 में पहुँचते और वहीं रुक जाते — ऑटोमेटा ऐसी स्ट्रिंग स्वीकार नहीं करता। स्ट्रिंग “aabbc” आज़माएँ, तो भी बात नहीं बनती, क्योंकि अवस्था q1 से अक्षर “a” का कोई तीर नहीं निकलता।
इस प्रकार परिमित ऑटोमेटा स्ट्रिंगों के किसी समुच्चय को पहचानने का काम करता है। व्यवहार में हम ऑटोमेटा का प्रयोग, उदाहरण के लिए, यह जानने के लिए कर सकते हैं कि दी गई इनपुट स्ट्रिंग मान्य ईमेल पता है या नहीं।
परिमित ऑटोमेटा की परिभाषा
परिमित ऑटोमेटा क्या है, इसकी पिछली सहज कल्पना को हमें औपचारिक रूप देना होगा, ताकि हम ऑटोमेटा के साथ आगे और बेहतर ढंग से काम कर सकें।
हम कहते हैं कि (नियतात्मक) परिमित ऑटोमेटा (DFA) एक 5-टपल ⟨Q, Σ, δ, q0, F⟩ है, जहाँ
- Q अवस्थाओं का परिमित समुच्चय है,
- Σ (बड़ा सिग्मा) वर्णमाला है (प्रतीकों/अक्षरों का परिमित समुच्चय),
- δ: Q × Σ ⟶ Q संक्रमण फलन है,
- q0 ∈ Q प्रारंभिक अवस्था है,
- F ⊆ Q अंतिम (स्वीकारक) अवस्थाओं का समुच्चय है।
पिछले ऑटोमेटा पर लौटें,
तो हम कह सकते हैं कि अवस्थाओं के समुच्चय Q में तीन अवस्थाएँ हैं: Q = {q0, q1, q2}। वर्णमाला Σ में वे अक्षर हैं, जिनसे हम स्ट्रिंगें बना सकते हैं, जिन्हें फिर ऑटोमेटा स्वीकार या अस्वीकार करेगा। यहाँ यह संभवतः वर्णमाला Σ= {a, b, c} होगी, परंतु यह इसका कोई भी अधिसमुच्चय भी हो सकती है। प्रारंभिक अवस्था q0 अवस्था q0 ही है, इसमें कुछ नहीं बदलता। इस ऑटोमेटा में अंतिम अवस्थाओं के समुच्चय में केवल एक अवस्था है: F = {q2}।
संक्रमण फलन से हमारा अर्थ उन तीन तीरों से है, जिन पर अक्षर लिखे हैं। यदि आपको संकेतन δ: Q × Σ ⟶ Q उलझाता है, तो इसका अर्थ केवल इतना है कि δ एक फलन (शायद बेहतर कहें तो प्रतिचित्रण) है, जो दो प्राचल लेता है: Q से एक अवस्था और Σ से एक अक्षर। कॉल करने पर फलन एक नई अवस्था लौटाता है। अपने संक्रमण फलन को हम सारणी से इस प्रकार परिभाषित कर सकते हैं:
इसलिए यदि हम δ(q1, c) कॉल करें, तो तीसरी पंक्ति लागू होती है और फलन उत्तर में अवस्था q2 देता है — आरेख की तरह ही। यदि हम अवस्था q1 में हैं और इनपुट पर अक्षर “c” है, तो हम अवस्था q2 में पहुँचते हैं। ऑटोमेटा किसी स्ट्रिंग को स्वीकार करता है, इसका औपचारिक अर्थ परिभाषित करने से पहले हम इस संकल्पना की सहज समझ का उपयोग करके कुछ और उदाहरण देखेंगे।
अन्य उदाहरण
-
एक ऐसा ऑटोमेटा बनाइए, जो द्विआधारी वर्णमाला, अर्थात् Σ= {0, 1}, पर काम करे और केवल उन्हीं स्ट्रिंगों को स्वीकार करे, जो 1 पर समाप्त होती हैं। उदाहरण के लिए, यह स्ट्रिंगें 1, 01, 000001, 0101011 स्वीकार करता है।
हमारे ऑटोमेटा में दो अवस्थाएँ हैं — प्रारंभिक q0 और अंतिम q1। जब भी इनपुट पर अंक 1 आता है, हम अंतिम अवस्था q1 में जाते हैं और वहीं रहते हैं। इसके विपरीत, यदि इनपुट पर अंक 0 है, तो हम गैर-अंतिम अवस्था q0 में जाते हैं और वहीं रहते हैं।
-
द्विआधारी वर्णमाला पर एक ऐसा ऑटोमेटा बनाइए, जो केवल उन स्ट्रिंगों को स्वीकार करे, जिनका पहला अक्षर आख़िरी अक्षर से भिन्न है।
पहले ही चरण में ऑटोमेटा दो “उप-ऑटोमेटा” में बँट जाता है। यदि स्ट्रिंग 0 से शुरू होती है, तो ऑटोमेटा बाएँ भाग में जाता है और वहीं रहता है; यदि 1 से शुरू होती है, तो दाएँ भाग में चला जाता है। आगे सब सामान्य है: यदि हम बाएँ भाग में हैं और इनपुट पर 1 है, तो हम अंतिम अवस्था में जाते हैं और वहीं रहते हैं। यदि इनपुट पर 0 है, तो हम अवस्था q1 में जाते हैं, जो अंतिम नहीं है।
पिछले ऑटोमेटा के विपरीत इस ऑटोमेटा में एक से अधिक अंतिम अवस्थाएँ हैं, अर्थात् F = {q3, q4}।
-
द्विआधारी वर्णमाला पर एक ऐसा ऑटोमेटा बनाइए, जो केवल उन स्ट्रिंगों को स्वीकार करे, जिनमें लगातार दो शून्य नहीं आते।
यह ऑटोमेटा दो कारणों से रोचक है। पहला, यह रिक्त स्ट्रिंग को स्वीकार करता है। ऑटोमेटा को हम रिक्त स्ट्रिंग दे सकते हैं; ऑटोमेटा उसे तब स्वीकार करता है, जब प्रारंभिक अवस्था साथ ही अंतिम अवस्था भी हो, और इस ऑटोमेटा में ऐसा ही है। रिक्त स्ट्रिंग में लगातार दो शून्य नहीं आते, इसलिए यह सही है। दूसरी रोचक बात यह है कि इस ऑटोमेटा की सभी अवस्थाएँ अंतिम हैं। ऑटोमेटा किसी स्ट्रिंग को केवल तब स्वीकार नहीं करता, जब किसी अवस्था से कोई संक्रमण न निकले। ऐसा अवस्था q1 में होता है, जिसमें 0 के लिए कोई संक्रमण नहीं है, क्योंकि तब स्ट्रिंग में लगातार दो शून्य आ जाते।
-
वर्णमाला {-,+,.,0,1,…,9} पर एक ऐसा ऑटोमेटा बनाइए, जो केवल उन स्ट्रिंगों को स्वीकार करे, जो किसी संख्या को निरूपित करती हैं। अर्थात् या तो पूर्णांक, जैसे 2, 548, 98263, या दशमलव संख्या, जैसे 5584.48, 3.14, और दोनों ऋण चिह्न वाले ऋणात्मक रूप में भी, जैसे -2, -548, -3.14, और स्पष्ट रूप से लिखे धन चिह्न के साथ भी, अर्थात् +2, +548, +3.14। साथ ही संख्या 0.123 को केवल .123 (आरंभ के शून्य के बिना) लिखना भी संभव होना चाहिए, और वह भी दोनों चिह्नों के साथ। हम एक सहायक संकेतन अपनाते हैं: दस अंकों के लिए दस संक्रमण लिखने के बजाय हम प्रतीक N का प्रयोग करेंगे।
-
द्विआधारी वर्णमाला पर एक ऐसा ऑटोमेटा बनाइए, जो केवल 0n1n रूप की स्ट्रिंगों को स्वीकार करे, अर्थात् ऐसी स्ट्रिंगें, जिनकी शुरुआत में कुछ शून्य हैं और उनके बाद उतनी ही इकाइयाँ (1)। ऐसी स्ट्रिंगों के उदाहरण हैं 0011, 00001111, 01।
ऐसा ऑटोमेटा बनाया ही नहीं जा सकता, क्योंकि हम कहीं भी शून्यों की संख्या “याद” नहीं रख सकते। हमें दूसरे उदाहरण की तरह कई “उप-ऑटोमेटा” बनाने पड़ते, परंतु ऐसे “उप-ऑटोमेटा” अपरिमित रूप से अनेक होने चाहिए, n के प्रत्येक मान के लिए एक।
ऑटोमेटा के अभिकलन का औपचारिक रूप
परिमित ऑटोमेटा को हम औपचारिक रूप से परिभाषित कर चुके हैं। अब हमें यह भी परिभाषित करना है कि ऐसा ऑटोमेटा वास्तव में करता क्या है, अर्थात् हम ऑटोमेटा का अभिकलन परिभाषित करेंगे।
ऑटोमेटा का विन्यास (configuration): हम कहते हैं कि युग्म ⟨q, w⟩ ∈ Q × Σ∗ ऑटोमेटा का विन्यास है, जहाँ q वर्तमान अवस्था है, जिसमें ऑटोमेटा है, और w स्ट्रिंग का अब तक न पढ़ा गया भाग है। Σ∗ वर्णमाला Σ का संवरक है, यानी उन सभी स्ट्रिंगों का समुच्चय, जिन्हें वर्णमाला Σ के अक्षरों से बनाया जा सकता है। संवरक में रिक्त स्ट्रिंग भी है, जिसे हम ε से दर्शाते हैं।
यदि ऑटोमेटा ⟨Q, Σ, δ, q0, F⟩ है और हम स्ट्रिंग w को स्वीकार करने का प्रयास कर रहे हैं, तो ऑटोमेटा प्रारंभिक विन्यास ⟨q0, w⟩ में होता है। यदि हम ऑटोमेटा
पर लौटें और स्ट्रिंग w = abbc को स्वीकार करना चाहें, तो प्रारंभिक विन्यास ⟨q0, abbc⟩ होगा।
अभिकलन का चरण हम समुच्चयों (Q × Σ∗) × (Q × Σ∗) के बीच, अर्थात् ऑटोमेटा के विन्यासों के बीच, संबंध ↦ के रूप में परिभाषित करते हैं। मान लीजिए w = w0w1… wn स्ट्रिंग w का अब तक न पढ़ा गया भाग है। तब हम कहते हैं कि युग्म ⟨q1, w0w1… wn⟩ और ⟨q2, w1… wn⟩ संबंध ↦ में हैं, और लिखते हैं
यदि और केवल यदि δ(q1, w0) = q2 हो। अपने उदाहरण पर लौटें, तो प्रारंभिक विन्यास ⟨q0, abbc⟩ है। आरेख से हम देखते हैं कि इनपुट “a” पर हम अवस्था q1 में जा सकते हैं। इसलिए हम लिख सकते हैं
क्योंकि δ(q0, a) = q1 है। इस तरह हमने अभिकलन का एक चरण पूरा किया — हमने देखा कि दिए गए इनपुट (= स्ट्रिंग के अब तक न पढ़े गए भाग का पहला अक्षर) पर हमें किस अवस्था में जाना चाहिए, वहाँ पहुँचे और न पढ़े गए भाग से पहला अक्षर हटा दिया। इससे हमें एक नया विन्यास मिला।
अभिकलन के चरण वाले संबंध का स्वतुल्य और संक्रामक संवरक (reflexive and transitive closure) हम ↦ ∗ से दर्शाते हैं। यदि हम लिखें K1 ↦ ∗ K2, जहाँ K1, K2 ऑटोमेटा के विन्यास हैं, तो इसका अर्थ है कि विन्यास K1 से अभिकलन के कुछ चरणों में हम विन्यास K2 तक पहुँच सकते हैं, यानी विन्यासों का ऐसा परिमित अनुक्रम मौजूद है कि:
उदाहरण के लिए, हमारे ऑटोमेटा में ⟨q0, abbc⟩ ↦ ∗ ⟨q1,bc⟩ सत्य है, क्योंकि अभिकलन के दो चरण करने पर स्ट्रिंग “bc” बचती है और हम अवस्था q1 में रहते हैं। अर्थात् विन्यासों का यह अनुक्रम मौजूद है:
ऑटोमेटा स्ट्रिंग w को स्वीकार करता है, यदि और केवल यदि कोई ऐसा qf ∈ F मौजूद हो कि
और अवस्था q2 अंतिम अवस्था है, q2 ∈ F।
ऑटोमेटा द्वारा स्वीकृत भाषा उन सभी स्ट्रिंगों का समुच्चय है, जिन्हें ऑटोमेटा स्वीकार करता है। ऑटोमेटा A की भाषा को हम L(A) से दर्शाएँगे। इस प्रकार L(A) ⊆ Σ∗ और
रेगुलर भाषा (regular language) वह भाषा है, जिसे कोई परिमित ऑटोमेटा स्वीकार करता है।
दो परिमित ऑटोमेटा तुल्य होते हैं, यदि वे एक ही भाषा स्वीकार करते हैं। अर्थात् ऑटोमेटा A1 और A2 तुल्य हैं, यदि L(A1) = L(A2) हो।
स्रोत
विषय-सूची: परिमित ऑटोमेटा, पूर्ण ऑटोमेटा, अनियतात्मक परिमित ऑटोमेटा, अनियतात्मक ऑटोमेटा का अनुकरण, NFA का DFA में रूपांतरण