✖

रेगुलर भाषाओं का सम्मिलन

मान लीजिए दो रेगुलर भाषाएँ L1, L2 हैं। हम सिद्ध करेंगे कि उनका सम्मिलन L = L1 ∪ L2 भी रेगुलर भाषा है।

नियतात्मक ऑटोमेटा द्वारा विधि

विधि का विचार

हमारे पास दो रेगुलर भाषाएँ L1 और L2 हैं और हम सिद्ध करना चाहते हैं कि उनका सम्मिलन L1 ∪ L2 फिर से रेगुलर भाषा है। L1 और L2 रेगुलर भाषाएँ हैं, इसलिए ऐसे परिमित ऑटोमेटा A1 और A2 मौजूद हैं, जो भाषाएँ L1 और L2 स्वीकार करते हैं, अर्थात् L(A1) = L1 और L(A2) = L2। आगे हम एक परिमित ऑटोमेटा A बनाएँगे, जो भाषा L1 ∪ L2 स्वीकार करेगा; इससे सिद्ध होगा कि भाषा L1 ∪ L2 रेगुलर है।

यह हम कैसे करेंगे? हमारे पास परिमित ऑटोमेटा A1 और A2 हैं, जो अलग-अलग भाषाएँ स्वीकार करते हैं। हम कह सकते हैं कि स्ट्रिंग w भाषा L1 ∪ L2 में है, यदि और केवल यदि ऑटोमेटा A1 और A2 में से कम से कम एक उसे स्वीकार करे।

ऑटोमेटा A इस तरह काम कर सकता है कि इनपुट w के लिए वह इनपुट w पर ऑटोमेटा A1 के अभिकलन का अनुकरण करेगा। यदि A1 स्ट्रिंग w को स्वीकार करे, तो A भी स्ट्रिंग w को स्वीकार करेगा। यदि A1 स्ट्रिंग w को अस्वीकार करे, तो A इनपुट w पर A2 के अभिकलन का अनुकरण करने का प्रयास करेगा। यदि A2 स्ट्रिंग w को स्वीकार करे, तो A भी स्ट्रिंग w को स्वीकार करेगा। अन्यथा वह अस्वीकार करेगा।

अब केवल यह औपचारिक रूप से बताना बाकी है कि ऑटोमेटा A किसी दूसरे ऑटोमेटा के अभिकलन का “अनुकरण” करता है, इसका क्या अर्थ है।

औपचारिक रूप

हमारे पास दो रेगुलर भाषाएँ L1 और L2 हैं, जिन्हें ये परिमित ऑटोमेटा स्वीकार करते हैं

A1=⟨Q1,Σ1,δ1,q1,F1⟩A2=⟨Q2,Σ2,δ2,q2,F2⟩.

हम परिमित ऑटोमेटा A = ⟨Q, Σ, δ, q, F⟩ बनाएँगे, जो भाषा L = L1 ∪ L2 स्वीकार करेगा। हम दो ऑटोमेटा A1, A2 के अनुकरण के विचार का उपयोग करेंगे। मान लीजिए इनपुट पर स्ट्रिंग w = w1w2… wn है और अब हम स्ट्रिंग w पर ऑटोमेटा A1 और A2 के अभिकलन का एक साथ अनुकरण करेंगे। ऑटोमेटा A1 का प्रारंभिक विन्यास ⟨q1, w1w2… wn⟩ है, A2 का प्रारंभिक विन्यास ⟨q2, w1w2… wn⟩ है। अब प्रत्येक ऑटोमेटा में हम अभिकलन का एक चरण करते हैं, जिससे हम विन्यासों ⟨δ1(q1, w1), w2… wn⟩ और ⟨δ2(q2, w1), w2… wn⟩ में पहुँचते हैं।

हम देखते हैं कि ये विन्यास केवल पहले घटक में भिन्न हैं; दूसरा घटक — स्ट्रिंग का न पढ़ा गया भाग — हमेशा समान रहता है। इसलिए अनुकरण के दौरान हमें दो ऑटोमेटा के दो विन्यास रखने की ज़रूरत नहीं है, ⟨⟨qi, qj⟩, wl… wn⟩ रूप का एक विन्यास पर्याप्त है, जहाँ qi ∈ Q1 और qj ∈ Q2 हैं। दूसरे शब्दों में, हम जो ऑटोमेटा A बना रहे हैं, उसका प्रारंभिक विन्यास ⟨⟨q1, q2⟩, w⟩ होगा। युग्म ⟨q1, q2⟩ का पहला भाग वह अवस्था है, जिसमें ऑटोमेटा A1 इस समय है, और दूसरा घटक ऑटोमेटा A2 की वर्तमान अवस्था है।

इसलिए हम लिख सकते हैं कि जो ऑटोमेटा A हम बना रहे हैं, उसकी अवस्थाओं का समुच्चय Q = Q1 × Q2 होगा। यह पिछले दोनों ऑटोमेटा की अवस्थाओं का कार्तीय गुणन होगा। आगे का विचार यह है कि ऑटोमेटा A की प्रारंभिक अवस्था ⟨q1, q2⟩ होगी, और यदि ऑटोमेटा A1 प्रतीक w1 पर अवस्था qi में जाता है और ऑटोमेटा A2 प्रतीक w1 पर अवस्था qj में, तो ऑटोमेटा A प्रतीक w1 पर अवस्था ⟨qi, qj⟩ में जाएगा।

संक्रमण फलन δ हम इस प्रकार लिखते हैं (यहाँ हम मान रहे हैं कि इस समय हम अवस्थाओं qi और qj में हैं):

δ(⟨qi,qj⟩,w)=⟨δ1(qi,w),δ2(qj,w)⟩

अब केवल छोटी बातें बाकी हैं। वर्णमाला के लिए Σ= Σ1 ∪ Σ2 है। प्रारंभिक अवस्था q = ⟨q1, q2⟩ है। और अंतिम अवस्थाएँ वे सभी युग्म ⟨qi, qj⟩ हैं, जिनके लिए या तो qi ∈ F1 या qj ∈ F2 हो।

विधि का उदाहरण

मान लीजिए दो ऑटोमेटा हैं। पहला ऑटोमेटा A1 है, जो वे सभी स्ट्रिंगें (रिक्त स्ट्रिंग सहित) स्वीकार करता है, जिनमें 0 और 1 बारी-बारी से आते हैं, अर्थात् 01, 0101, 010101, … रूप की स्ट्रिंगें

दूसरा ऑटोमेटा A2 वे स्ट्रिंगें स्वीकार करता है, जिनमें कम से कम एक शून्य है:

इन भाषाओं का सम्मिलन वे स्ट्रिंगें हैं, जिनमें या तो शून्य है या जो 01, 0101, … रूप की हैं। अब हम परिमित ऑटोमेटा A = ⟨Q, Σ, δ, q, F⟩ बनाएँगे, जो यही सम्मिलित भाषा स्वीकार करेगा। सबसे पहले हम देखेंगे कि इस नए ऑटोमेटा A की अवस्थाएँ कैसी होंगी। यह पहले और दूसरे ऑटोमेटा की अवस्थाओं का कार्तीय गुणन होगा:

Q=Q1×Q2={⟨q0,p0⟩,⟨q0,p1⟩,⟨q1,p0⟩,⟨q1,p1⟩,⟨q2,p0⟩,⟨q2,p1⟩}

ये ऑटोमेटा A की छह अवस्थाएँ हैं, जो सम्मिलित भाषा L(A1) ∪ L(A2) स्वीकार करता है। आरेख में वे ऐसी दिखेंगी:

इससे घबराइए नहीं कि यहाँ अवस्थाएँ अवस्थाओं के युग्मों से बनी हैं — यह केवल यह समझने में मदद करता है कि ऑटोमेटा में वास्तव में क्या हो रहा है। अवस्थाओं के नाम सामान्य ढंग से q0, …, q5 भी हो सकते थे। अंतिम अवस्थाएँ वे अवस्थाएँ हैं, जिनमें या तो अवस्था q0 है या p1, क्योंकि ये पहले वाले दोनों ऑटोमेटा की अंतिम अवस्थाएँ हैं। प्रारंभिक अवस्था ⟨q0, p0⟩ है।

अब हमें सभी संक्रमण ढूँढने हैं। हम ऐसी सारणी लिखते हैं:

01⟨q0,p0⟩⟨q0,p1⟩⟨q1,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q2,p1⟩

और धीरे-धीरे सारणी भरेंगे। सबसे पहले हम देखते हैं कि इनपुट 0 पर अवस्था ⟨q0, p0⟩ से संक्रमण कहाँ जाएगा। हम देखते हैं कि ऑटोमेटा A1 में इनपुट 0 पर अवस्था q0 से संक्रमण कहाँ जाता है: वह अवस्था q1 में जाता है। ऑटोमेटा A2 में शून्य पर p0 से संक्रमण अवस्था p1 में जाता है। इसलिए हम सारणी में ⟨q1, p1⟩ लिखते हैं:

01⟨q0,p0⟩⟨q1,p1⟩⟨q0,p1⟩⟨q1,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q2,p1⟩

इनपुट 1 पर हमें मिलता है: ऑटोमेटा A1 के लिए δ1(q0, 1) = q2 और ऑटोमेटा A2 के लिए δ2(p0, 1) = p0। इसलिए हमें अवस्था ⟨q2, p0⟩ मिलती है।

01⟨q0,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q0,p1⟩⟨q1,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q2,p1⟩

बाकी सारणी भी भर देते हैं:

01⟨q0,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q0,p1⟩⟨q1,p1⟩⟨q2,p1⟩⟨q1,p0⟩⟨q2,p1⟩⟨q0,p0⟩⟨q1,p1⟩⟨q2,p1⟩⟨q0,p1⟩⟨q2,p0⟩⟨q2,p1⟩⟨q2,p0⟩⟨q2,p1⟩⟨q2,p1⟩⟨q2,p1⟩

और इस सारणी के अनुसार हम आरेख का बाकी भाग बना देते हैं।

हम जाँच सकते हैं कि ऑटोमेटा ठीक से काम करता है। आइए, स्ट्रिंग 0100 को स्वीकार करने का प्रयास करें। ऑटोमेटा क्रमशः इन अवस्थाओं से गुज़रेगा

⟨q0,p0⟩,⟨q1,p1⟩,⟨q0,p1⟩,⟨q1,p1⟩,⟨q2,p1⟩

अवस्था ⟨q2, p1⟩ अंतिम अवस्था है, इसलिए ऑटोमेटा A स्ट्रिंग 0100 को स्वीकार करता है। यदि हम स्ट्रिंग 0100 को ऑटोमेटा A1 और A2 से स्वीकार करने का प्रयास करते, तो क्या होता? ऑटोमेटा A1 क्रमशः इन अवस्थाओं से गुज़रता:

q0,q1,q0,q1,q2

ऑटोमेटा अवस्था q2 में रुका, जो अंतिम अवस्था नहीं है, इसलिए ऑटोमेटा A1 यह स्ट्रिंग स्वीकार नहीं करता। ऑटोमेटा A2 का क्या?

p0,p1,p1,p1,p1

अवस्था p1 अंतिम है, इसलिए ऑटोमेटा A2 स्ट्रिंग 0100 को स्वीकार कर लेता। ध्यान दीजिए कि ऑटोमेटा A1 और A2 अवस्थाओं q2 और p1 में रुके, जो इस बात से मेल खाता है कि ऑटोमेटा A अवस्था ⟨q2, p1⟩ में रुका।

अनियतात्मक ऑटोमेटा द्वारा विधि

उदाहरण

रेगुलर भाषाओं का समुच्चय सम्मिलन के अंतर्गत संवृत है, यह हम एक अनियतात्मक ऑटोमेटा बनाकर भी सिद्ध कर सकते हैं, जो कहीं अधिक सरल होगा।

हमारे पास दो रेगुलर भाषाएँ L1, L2 हैं और हम सिद्ध करना चाहते हैं कि उनका सम्मिलन L = L1 ∪ L2 भी रेगुलर भाषा है। L1, L2 रेगुलर भाषाएँ हैं, इसलिए ऐसे ऑटोमेटा A1, A2 अवश्य होंगे, जो इन भाषाओं को स्वीकार करते हैं। अर्थात् L(A1) = L1 और L(A2) = L2। इन ऑटोमेटा की सहायता से हम ऑटोमेटा A बनाएँगे, जो भाषा L स्वीकार करेगा, अर्थात् L(A) = L।

मान लीजिए परिमित ऑटोमेटा A1 और A2 ऐसे दिखते हैं:

और

दोनों भाषाओं के सम्मिलन को स्वीकार करने वाला ऑटोमेटा हम ऐसे बनाएँगे: एक नई प्रारंभिक अवस्था बनाइए और इस अवस्था से दोनों ऑटोमेटा की पुरानी प्रारंभिक अवस्थाओं में दो एप्सिलॉन संक्रमण खींचिए। बस इतना ही। ऑटोमेटा ऐसा दिखेगा:

औपचारिक रूप (अनियतात्मक ऑटोमेटा)

हमारे पास दो ऑटोमेटा A1 = ⟨Q1, Σ, δ1, q1, F1⟩ और A2 = ⟨Q2, Σ, δ2, q2, F2⟩ हैं। हम ऑटोमेटा A = ⟨Q, Σ, δ, q0, F⟩ बनाएँगे, जो पिछले ऑटोमेटा द्वारा स्वीकृत भाषाओं का सम्मिलन स्वीकार करेगा, अर्थात् L(A) = L(A1) ∪ L(A2)। यहाँ:

  • Q = Q1 ∪ Q2 ∪ {q0}
  • F = F1 ∪ F2

और संक्रमण फलन δ हम इस प्रकार परिभाषित करते हैं:

δ(q,a)={δ1(q,a)यदिq∈Q1δ2(q,a)यदिq∈Q2{q1,q2}यदिq=q0∧a=ε∅यदिq=q0∧a≠ε

स्रोत

विषय-सूची: रेगुलर भाषाओं के संवृतता गुण, रेगुलर भाषाओं का सम्मिलन, रेगुलर भाषाओं का सर्वनिष्ठ, रेगुलर भाषाओं का अंतर, रेगुलर भाषा का पूरक, रेगुलर भाषाओं का संयोजन, रेगुलर भाषा का संवरक