✖

रेगुलर भाषाओं का अंतर

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

विचार

वास्तव में सिद्ध करने को बहुत कुछ नहीं है। दो समुच्चयों के अंतर के लिए यह संबंध सत्य है:

L1∖L2=L1∩L2′,

जहाँ L2′ भाषा L2 का पूरक है। रेगुलर भाषाओं के सर्वनिष्ठ और रेगुलर भाषा के पूरक वाले अध्यायों से हम जानते हैं कि रेगुलर भाषाएँ इन दोनों संक्रियाओं के अंतर्गत संवृत हैं। इसका अर्थ है कि हम भाषाओं का सर्वनिष्ठ और भाषा का पूरक स्वीकार करने वाले ऑटोमेटा बना सकते हैं। इन ऑटोमेटा की सहायता से हम ऐसा ऑटोमेटा बना सकते हैं, जो भाषा L1 ∩ L2′ स्वीकार करे, और यही भाषा L1 ∖ L2 है।

उदाहरण

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

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

हम ऐसा ऑटोमेटा बनाएँगे, जो इन भाषाओं का अंतर स्वीकार करेगा। इसके लिए हमें ऑटोमेटा A2′ चाहिए, जो ऑटोमेटा A2 का पूरक होगा। हम बस अंतिम और गैर-अंतिम अवस्थाओं को आपस में बदल देते हैं:

अब केवल ऑटोमेटा A बनाना बाकी है, जो भाषाओं L(A1) और L(A2′) का सर्वनिष्ठ स्वीकार करेगा:

स्रोत

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