ऑटोमेटा से रेगुलर एक्सप्रेशन में रूपांतरण
हम दिखाएँगे कि किसी भी परिमित ऑटोमेटा को रेगुलर एक्सप्रेशन में कैसे बदला जाता है।
एल्गोरिद्म का वर्णन
इनपुट पर कोई NFA A है। सबसे पहले हम इसे GNFA में बदलते हैं। दूसरे भाग में हम हर चरण में एक अवस्था हटाते हैं, संक्रमण फलन को सही ढंग से बदलते हैं और यह तब तक दोहराते हैं, जब तक केवल दो अवस्थाएँ — प्रारंभिक और अंतिम — न बचें। इनके बीच एक किनारा होगा, जिस पर लिखा रेगुलर एक्सप्रेशन पूरे एल्गोरिद्म का परिणाम होगा। इस प्रकार पूरी विधि मुख्यतः एक अवस्था हटाने (अवस्था निरसन, state elimination) और फिर ऑटोमेटा को इस तरह ठीक करने पर टिकी है कि हमें तुल्य ऑटोमेटा मिले।
एक अवस्था हटाना
एक अवस्था कैसे हटाएँ, यह हम एक सरल उदाहरण से समझ सकते हैं। मान लीजिए हमारे ऑटोमेटा का एक भाग ऐसा दिखता है:
जहाँ Ri कुछ रेगुलर एक्सप्रेशन हैं। यदि हम अवस्था qr हटा दें, तो ऑटोमेटा कैसा दिखेगा? हम ऐसे सोच सकते हैं कि हम अवस्था qi में हैं और पूछते हैं कि इस भाग पर हम कौन-कौन सी स्ट्रिंगें जनित कर सकते हैं। यदि हम अवस्था qi से सीधे अवस्था qj में जाएँ, तो ये वे सभी स्ट्रिंगें होंगी, जो रेगुलर एक्सप्रेशन R4 से मेल खाती हैं।
परंतु यदि हम अवस्था qr में जाएँ, तो हम R1 रूप की स्ट्रिंगें जनित कर सकते हैं। अवस्था qr में हम रेगुलर एक्सप्रेशन R2 के लिए लूप कर सकते हैं, इसलिए वास्तव में हम
अब हम जानते हैं कि ऑटोमेटा के इस भाग से R4 रूप की या
अब हम आसानी से अवस्था qr हटा सकते हैं और केवल दो अवस्थाएँ qi और qj रख सकते हैं; R4 के स्थान पर हम अभी परिकलित रेगुलर एक्सप्रेशन लिखते हैं:
यह विधि हम प्रत्येक अवस्था qi से किसी अवस्था qj तक जाने वाले प्रत्येक किनारे के लिए लागू करते हैं, लूप सहित, अर्थात् उस स्थिति में भी, जब qi = qj हो।
एक अवस्था हटाने के बाद हमें तुल्य ऑटोमेटा मिलता है — ऐसा ऑटोमेटा, जो वही भाषा पहचानता है।
पूरा एल्गोरिद्म
इनपुट पर NFA A = ⟨Q, Σ, δ, q0, F⟩ है।
- NFA A को GNFA Z = ⟨Q′, Σ, δ′, q0′, qf′⟩ में बदलिए। आगे अक्षर k से हम Z में अवस्थाओं की संख्या दर्शाएँगे।
- यदि k = 2 हो, तो एल्गोरिद्म समाप्त होता है और प्रारंभिक तथा अंतिम अवस्था के बीच के किनारे पर परिणामी रेगुलर एक्सप्रेशन है।
- यदि k>2 हो, तो कोई भी ऐसी अवस्था qr चुनिए, जो प्रारंभिक और अंतिम अवस्था से भिन्न हो, अर्थात् qr ≠ q0′ और qr ≠ qf′। फिर एक नया GNFA Z′ = ⟨Q′′, Σ, δ′′,q0′,qf′⟩ बनाइए, जिसके लिए:
और सभी qi ∈ Q′′ ∖ {qf′} तथा सभी qj ∈ Q′′ ∖ {q0′} के लिए जहाँ R1 = δ′(qi,qr), R2 = δ′(qr,qr), R3 = δ′(qr, qj), R4 = δ′(qi, qj)। फिर चरण 2 पर जाइए।
उदाहरण
मान लीजिए इनपुट पर यह परिमित ऑटोमेटा है:
सबसे पहले हम इसे GNFA में बदलते हैं (अनावश्यक ∅-संक्रमण हम नहीं दिखाएँगे):
अब हम एल्गोरिद्म का दूसरा भाग लागू करते हैं और कोई नोड हटाते हैं। हम नोड q2 से शुरू करते हैं। हम नोड q2 हटाते हैं और अवस्था q1 से अवस्था qf में एक संक्रमण जोड़ते हैं। इस संक्रमण पर हम b(a|b)∗ लिखते हैं, क्योंकि नोड q1 से हम b रूप की स्ट्रिंगों के लिए अवस्था q2 में पहुँचते हैं, फिर a|b के लिए लूप कर सकते हैं, जिससे हमें (a|b)∗ मिलता है, और अंत में एप्सिलॉन नियम से qf में चले जाते हैं। यहाँ b(a|b)∗ϵ = b(a|b)∗ है। हमें यह ऑटोमेटा मिलता है:
अब आख़िरी बची अवस्था q1 हटानी है। हम अवस्था qs से अवस्था qf तक एक किनारा जोड़ते हैं। उस पर क्या लिखें? अवस्था q1 में हम एप्सिलॉन नियम से पहुँचते हैं, उसे हम सीधे छोड़ सकते हैं। फिर हम a के लिए लूप कर सकते हैं, जिससे हमें रेगुलर एक्सप्रेशन a∗ मिलता है। और अंत में किनारे से हम qf में पहुँचते हैं, इसलिए व्यंजक का b(a|b)∗ से संयोजन भी करते हैं। इस प्रकार किनारे पर हम रेगुलर एक्सप्रेशन a∗ b(a|b)∗ लिखते हैं।
अब ऑटोमेटा में केवल दो अवस्थाएँ हैं, इसलिए एल्गोरिद्म समाप्त होता है। किनारे पर परिणामी रेगुलर एक्सप्रेशन है।
स्रोत
- उदाहरण और एल्गोरिद्म का वर्णन इस पुस्तक से लिया गया है: M. Sipser: Introduction to the Theory of Computation
विषय-सूची: रेगुलर एक्सप्रेशन, रेगुलर एक्सप्रेशन से ऑटोमेटा में रूपांतरण, व्यापकीकृत अनियतात्मक परिमित ऑटोमेटा, ऑटोमेटा से रेगुलर एक्सप्रेशन में रूपांतरण