रेगुलर भाषा का संवरक
हमारे पास रेगुलर भाषा L है। हम सिद्ध करेंगे कि भाषा L का संवरक फिर से रेगुलर भाषा है।
भाषा का संवरक क्या है
भाषा L के संवरक (क्लीनी संवरक, Kleene star) को L∗ से दर्शाते हैं। संवरक में वे सभी स्ट्रिंगें हैं, जिन्हें भाषा L की परिमित संख्या में स्ट्रिंगों के संयोजन से बनाया जा सकता है। संवरक को हम इस प्रकार परिभाषित कर सकते हैं:
जहाँ ∘ संयोजन की संक्रिया है और W पूर्ण संख्याओं (शून्य सहित) का समुच्चय है। संवरक में रिक्त स्ट्रिंग ϵ भी होती है।
औपचारिक विधि
हम लगभग वैसे ही आगे बढ़ेंगे, जैसे भाषाओं के संयोजन में। केवल दो भिन्न ऑटोमेटा जोड़ने के बजाय हम एक ही ऑटोमेटा को स्वयं से जोड़ेंगे — ऑटोमेटा की अंतिम अवस्थाओं से ऑटोमेटा की प्रारंभिक अवस्था में एप्सिलॉन संक्रमण खींचेंगे। परंतु संवरक में रिक्त स्ट्रिंग भी होनी चाहिए। इसकी व्यवस्था कैसे करें? हम प्रारंभिक अवस्था को अंतिम अवस्था बना सकते हैं। तब ऐसा ऑटोमेटा रिक्त स्ट्रिंग स्वीकार कर लेगा, परंतु वह कोई और स्ट्रिंग भी स्वीकार कर सकता है, जो संवरक में नहीं है। इसलिए इसके बजाय हम एक नई प्रारंभिक अवस्था बनाते हैं और इस नई प्रारंभिक अवस्था से पुरानी प्रारंभिक अवस्था में एक एप्सिलॉन संक्रमण खींचते हैं।
हमारे पास रेगुलर भाषा L1 और इसे स्वीकार करने वाला ऑटोमेटा है:
हम अनियतात्मक ऑटोमेटा A = ⟨Q, Σ, δ, qs, F⟩ बनाते हैं, जिसके लिए:
- Q = Q1 ∪ {qs}
- Σ= Σ1
- F = F1 ∪ {qs}
संक्रमण फलन δ हम इस प्रकार परिभाषित करते हैं:
उदाहरण
मान लीजिए यह ऑटोमेटा A1 है, जो स्ट्रिंगें 00 या 11 स्वीकार करता है:
तब भाषा L(A1) का संवरक उन सभी स्ट्रिंगों की भाषा है, जो युग्मों 00 और 11 से बनी हैं, जैसे 0000, 110011, 11110000 आदि। इस संवरक को स्वीकार करने वाला ऑटोमेटा हम ऐसे बनाएँगे: एक नई प्रारंभिक अवस्था qs बनाते हैं, जिससे पूर्व प्रारंभिक अवस्था q0 में एप्सिलॉन संक्रमण जाता है, और अवस्थाओं q3 और q4 से अवस्था q0 में एप्सिलॉन संक्रमण जोड़ते हैं:
हम सत्यापित कर सकते हैं कि यह ऑटोमेटा वास्तव में स्ट्रिंगें 0000, 110011, 11110000 स्वीकार करता है, परंतु, उदाहरण के लिए, स्ट्रिंग 1010 स्वीकार नहीं करता।
स्रोत
विषय-सूची: रेगुलर भाषाओं के संवृतता गुण, रेगुलर भाषाओं का सम्मिलन, रेगुलर भाषाओं का सर्वनिष्ठ, रेगुलर भाषाओं का अंतर, रेगुलर भाषा का पूरक, रेगुलर भाषाओं का संयोजन, रेगुलर भाषा का संवरक