✖

रेगुलर भाषाओं के संवृतता गुण

भाषा L रेगुलर है, यदि और केवल यदि कोई ऐसा ऑटोमेटा A मौजूद हो, जो इस भाषा को स्वीकार करता है, अर्थात् L(A) = L। हम सिद्ध करेंगे कि रेगुलर भाषाएँ सम्मिलन, सर्वनिष्ठ, संयोजन (concatenation) और संवरक की संक्रियाओं के अंतर्गत संवृत हैं।

किसी संक्रिया के अंतर्गत समुच्चय की संवृतता

हम कहते हैं कि समुच्चय M संक्रिया ⊗ के अंतर्गत संवृत है, यदि

∀x,y∈M:x⊗y∈M

उदाहरण के लिए, प्राकृत संख्याओं के समुच्चय पर योग की संक्रिया। किन्हीं भी दो प्राकृत संख्याओं का योगफल फिर से एक प्राकृत संख्या है। इसके विपरीत, प्राकृत संख्याओं का समुच्चय घटाने की संक्रिया के अंतर्गत संवृत नहीं है, क्योंकि, उदाहरण के लिए, 7 − 15 = −8 है और संख्या −8 प्राकृत नहीं है।

हम सिद्ध करेंगे कि रेगुलर भाषाओं का समुच्चय किन संक्रियाओं के अंतर्गत संवृत है। सभी उपपत्तियाँ रचनात्मक होंगी, अर्थात् हम ऐसा ऑटोमेटा बनाएँगे, जो परिणामी भाषा को स्वीकार करता है।

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