✖

रेगुलर भाषाओं का संयोजन

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

संयोजन क्या है

दो स्ट्रिंगों “010” और “1111” के संयोजन से स्ट्रिंग “0101111” बनती है। भाषाओं के संयोजन से एक नई भाषा बनती है, जिसे हम इस तरह बनाते हैं कि एक भाषा की प्रत्येक स्ट्रिंग का दूसरी भाषा की प्रत्येक स्ट्रिंग से संयोजन करते हैं। दो स्ट्रिंगों और दो भाषाओं के संयोजन को हम छोटे वृत्त ∘ से दर्शाएँगे। तब भाषाओं L1 और L2 का संयोजन हम इस प्रकार परिभाषित कर सकते हैं:

L1∘L2={a∘b|a∈L1,b∈L2}

उपपत्ति का विचार

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

A1=⟨Q1,Σ1,δ1,q0,F1⟩A2=⟨Q2,Σ2,δ2,p0,F2⟩

हम एक अनियतात्मक ऑटोमेटा A = ⟨Q, Σ, δ, q, F⟩ बनाएँगे, जिसके “भीतर” दोनों ऑटोमेटा A1 और A2 होंगे। आधारभूत विचार यह है कि हम स्ट्रिंग को ऑटोमेटा A1 से स्वीकार करना शुरू करते हैं, और जब ऑटोमेटा A1 किसी अंतिम अवस्था में पहुँचता है, तो स्ट्रिंग के बचे हुए भाग को ऑटोमेटा A2 से स्वीकार करने का प्रयास करते हैं। यदि यह ऑटोमेटा भी स्ट्रिंग का वह भाग स्वीकार कर ले, तो ऑटोमेटा A स्ट्रिंग को स्वीकार करता है।

उदाहरण

मान लीजिए यह ऑटोमेटा A1 है, जो केवल शून्यों से बनी अरिक्त स्ट्रिंगें और वे स्ट्रिंगें स्वीकार करता है, जिनमें एक 1 के बाद केवल शून्य आते हैं (1, 10, 100, …):

और मान लीजिए यह ऑटोमेटा A2 है, जो 01 पर समाप्त होने वाली स्ट्रिंगें स्वीकार करता है:

ऑटोमेटा को हम ऐसे जोड़ते हैं: ऑटोमेटा A1 की सभी अंतिम अवस्थाओं से ऑटोमेटा A2 की प्रारंभिक अवस्था में एप्सिलॉन संक्रमण जोड़ते हैं और फिर A1 की अंतिम अवस्थाओं को सामान्य अवस्थाएँ बना देते हैं। पूरे नए ऑटोमेटा की प्रारंभिक अवस्था ऑटोमेटा A1 की प्रारंभिक अवस्था होगी:

ऑटोमेटा कैसे काम करेगा? हम ऑटोमेटा A1 के काम का अनुकरण शुरू करते हैं। यदि हम पूर्व अंतिम अवस्था q1 या q2 में पहुँचते हैं, तो हम जानते हैं कि ऑटोमेटा A1 इस स्ट्रिंग का एक भाग स्वीकार करता है। पूरी स्ट्रिंग भाषा L1 ∘ L2 में हो, इसके लिए बचा हुआ भाग दूसरे ऑटोमेटा A2 को भी स्वीकार करना होगा — इसीलिए सभी पूर्व अंतिम अवस्थाओं से एप्सिलॉन संक्रमण ऑटोमेटा A2 की प्रारंभिक अवस्था में जाते हैं।

उदाहरण के लिए, स्ट्रिंग 0001 लीजिए। यह दोनों भाषाओं के संयोजन में है, क्योंकि यह स्ट्रिंगों के संयोजन 00 ∘ 01 से बन सकती है। परंतु यह संयोजन 0 ∘ 001 से भी बन सकती है। हमारे ऑटोमेटा में हम दोनों क्रमों का अनुकरण कर सकते हैं। ऑटोमेटा इस रास्ते पर चल सकता है:

q0→0q1→0q1→εp0→0p1→1p2

इस रास्ते पर ऑटोमेटा पहले स्ट्रिंग का भाग 00 “स्वीकार” करता और फिर भाग 01। या वह इस रास्ते पर चल सकता है:

q0→0q1→εp0→0p0→0p1→1p2

और तब ऑटोमेटा पहले स्ट्रिंग का भाग 0 “स्वीकार” करता और फिर भाग 001। स्वाभाविक है कि दोनों स्थितियों में हम अंतिम अवस्था p2 में पहुँचते हैं।

औपचारिक विधि

एक बार फिर: हमारे पास दो रेगुलर भाषाएँ L1, L2 और इन भाषाओं को स्वीकार करने वाले दो ऑटोमेटा हैं:

A1=⟨Q1,Σ1,δ1,q0,F1⟩A2=⟨Q2,Σ2,δ2,p0,F2⟩

हम अनियतात्मक ऑटोमेटा A = ⟨Q, Σ, δ, q, F⟩ बनाते हैं, जिसके लिए:

  • Q = Q1 ∪ Q2 (साथ ही हम मानते हैं कि Q1 ∩ Q2 = ∅)
  • Σ= Σ1 ∪ Σ2
  • q = q0
  • F = F2

संक्रमण फलन δ हम क्रमशः बनाते हैं:

δ(q,a)={δ1(q,a)यदिq∈Q1∧q∉F1δ1(q,a)यदिq∈F1∧a≠εδ1(q,a)∪{p0}यदिq∈F1∧a=εδ2(q,a)यदिq∈Q2

स्रोत

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