✖

रेगुलर भाषा का पूरक

हमारे पास रेगुलर भाषा L है। हम सिद्ध करेंगे कि भाषा L का पूरक फिर से रेगुलर भाषा है।

पूरक क्या है

भाषा L के पूरक से हमारा अर्थ उन सभी स्ट्रिंगों से है, जो भाषा L में नहीं हैं। पूरक को L' से दर्शाते हैं। अर्थात् वर्णमाला Σ के लिए:

L′={w∈Σ∗|w∉L}.

उदाहरण के लिए, उन स्ट्रिंगों की भाषा का पूरक, जिनमें कम से कम एक बार प्रतीक 1 आता है, वह भाषा होगी, जिसकी स्ट्रिंगों में प्रतीक 1 एक बार भी नहीं आता।

विधि

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

उदाहरण

मान लीजिए यह ऑटोमेटा है:

भाषा के पूरक को स्वीकार करने वाला ऑटोमेटा ऐसा दिखेगा:

स्रोत

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