रेगुलर भाषा का पूरक
हमारे पास रेगुलर भाषा L है। हम सिद्ध करेंगे कि भाषा L का पूरक फिर से रेगुलर भाषा है।
पूरक क्या है
भाषा L के पूरक से हमारा अर्थ उन सभी स्ट्रिंगों से है, जो भाषा L में नहीं हैं। पूरक को L' से दर्शाते हैं। अर्थात् वर्णमाला Σ के लिए:
उदाहरण के लिए, उन स्ट्रिंगों की भाषा का पूरक, जिनमें कम से कम एक बार प्रतीक 1 आता है, वह भाषा होगी, जिसकी स्ट्रिंगों में प्रतीक 1 एक बार भी नहीं आता।
विधि
विधि बहुत सरल है। हमारे पास रेगुलर भाषा L और उसे स्वीकार करने वाला नियतात्मक पूर्ण ऑटोमेटा A = ⟨Q, Σ, δ, q0, F⟩ है (प्रत्येक परिमित ऑटोमेटा को ऐसे ऑटोमेटा में बदला जा सकता है)। L' को स्वीकार करने वाला ऑटोमेटा A' हम अंतिम और गैर-अंतिम अवस्थाओं को आपस में बदलकर बनाते हैं: A' = ⟨Q, Σ, δ, q0, Q ∖ F⟩। बस इतना ही।
उदाहरण
मान लीजिए यह ऑटोमेटा है:
भाषा के पूरक को स्वीकार करने वाला ऑटोमेटा ऐसा दिखेगा:
स्रोत
विषय-सूची: रेगुलर भाषाओं के संवृतता गुण, रेगुलर भाषाओं का सम्मिलन, रेगुलर भाषाओं का सर्वनिष्ठ, रेगुलर भाषाओं का अंतर, रेगुलर भाषा का पूरक, रेगुलर भाषाओं का संयोजन, रेगुलर भाषा का संवरक