✖

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

मान लीजिए दो रेगुलर भाषाएँ 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 रेगुलर है।

कोई स्ट्रिंग भाषाओं के सर्वनिष्ठ में है, यदि वह भाषा L1 में भी है और L2 में भी। अर्थात् स्ट्रिंग को ऑटोमेटा A1 भी स्वीकार करे और ऑटोमेटा A2 भी। हम वही विचार अपनाएँगे, जो हमने रेगुलर भाषाओं के सम्मिलन में अपनाया था; केवल अंतिम अवस्थाओं का समुच्चय बदल देंगे।

विधि का औपचारिक रूप

हमारे पास दो ऑटोमेटा हैं,

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

हम ऑटोमेटा A = ⟨Q, Σ, δ, q, F⟩ बनाते हैं, जो भाषा L(A1) ∩ L(A2) स्वीकार करता है। यहाँ

  • Q = Q1 × Q2
  • Σ= Σ1 ∩ Σ2
  • q = ⟨q0, p0⟩
  • F = F1 × F2

संक्रमण फलन δ के लिए यह संबंध सत्य होगा:

∀q∈Q1,p∈Q2:δ(⟨q,p⟩,a)=⟨δ1(q,a),δ2(p,a)⟩

उदाहरण

मान लीजिए यह ऑटोमेटा A1 है, जो वे सभी स्ट्रिंगें स्वीकार करता है, जिनमें 1 की संख्या सम है:

और ऑटोमेटा A2, जो वे स्ट्रिंगें स्वीकार करता है, जिनमें 0 की संख्या विषम है:

हम ऐसा ऑटोमेटा बनाएँगे, जो इन भाषाओं का सर्वनिष्ठ स्वीकार करेगा। इस ऑटोमेटा की अवस्थाओं का समुच्चय Q = Q1 × Q2 रूप का है, प्रारंभिक अवस्था ⟨q0, p0⟩ है और अंतिम अवस्थाएँ F1 × F2 हैं:

आगे हम संक्रमण इस प्रकार जोड़ते हैं कि δ(⟨q,p⟩, a) = ⟨δ1(q, a), δ2(p, a)⟩:

इस ऑटोमेटा में, उदाहरण के लिए, अवस्था ⟨q0, p0⟩ से प्रतीक 0 का संक्रमण अवस्था ⟨q0,p1⟩ में जाता है। इसका अर्थ है कि ऑटोमेटा A1 में अवस्था q0 से प्रतीक 0 का संक्रमण वापस अवस्था q0 में जाता है। और ऑटोमेटा A2 में प्रतीक 0 का संक्रमण अवस्था p0 से अवस्था p1 में जाता है।

ऑटोमेटा को आप आज़मा सकते हैं। उसे 110 या 00000 जैसी स्ट्रिंगें स्वीकार करनी चाहिए (इनमें 1 की संख्या सम और साथ ही 0 की संख्या विषम है), परंतु 11, 111, 1010 जैसी स्ट्रिंगें स्वीकार नहीं करनी चाहिए।

स्रोत

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