Omega-regular language
ω-नियमित भाषाएँ ω-भाषाओं का एक वर्ग है जो नियमित भाषाओं की परिभाषा को अनंत शब्दों में सामान्यीकृत करती है। औपचारिक परिभाषा एक ω-भाषा L ω-नियमित है यदि इसका रूप Aω है जहाँ A एक नियमित भाषा है जिसमें खाली स्ट्रिंग AB नहीं है, एक नियमित भाषा A का संयोजन और एक ω-नियमित भाषा B (ध्यान दें कि BA अच्छी तरह से परिभाषित नहीं है) A ≤ B जहाँ A और B ω-नियमित भाषाएँ हैं (इस नियम को केवल कई बार सीमित रूप से लागू किया जा सकता है) Aω के तत्व A से शब्दों को अनंत रूप से कई बार जोड़कर प्राप्त किए जाते हैं। ध्यान दें कि यदि A नियमित है, तो Aω आवश्यक रूप से ω-नियमित नहीं है, क्योंकि A उदाहरण के लिए {ε} हो सकता है, जिसमें केवल खाली स्ट्रिंग होती है, इस मामले में Aω = A, जो एक ω-भाषा नहीं है और इसलिए एक ω-नियमित भाषा नहीं है। यह इस परिभाषा का एक सीधा परिणाम है कि ω-नियमित भाषाएँ सटीक रूप से A1B1ω ≤. ≤ कुछ n के लिए anBnω रूप की ω-भाषाएँ हैं, जहाँ ऐस और बिस नियमित भाषाएँ हैं और बिस में खाली स्ट्रिंग नहीं है। बुची स्वचालित प्रमेय के समतुल्यः एक ω-भाषा को बुची स्वचालित द्वारा तभी पहचाना जाता है जब वह एक ω-नियमित भाषा हो। प्रमाणः प्रत्येक ω-नियमित भाषा को एक गैर-निर्धारक बुची स्वचालित द्वारा पहचाना जाता है; अनुवाद रचनात्मक है। ω-नियमित भाषा की परिभाषा पर बुची ऑटोमेटा और संरचनात्मक प्रेरण के समापन गुणों का उपयोग करके, यह आसानी से दिखाया जा सकता है कि किसी भी ω-नियमित भाषा के लिए बुची ऑटोमेटन का निर्माण किया जा सकता है। इसके विपरीत, किसी दिए गए बुची स्वचालित के लिए, हम एक ω-नियमित भाषा का निर्माण करते हैं और फिर हम दिखाएंगे कि इस भाषा को ए द्वारा पहचाना जाता है। एक ω-शब्द के लिए डब्ल्यू = ए1ए2. मान लीजिए कि डब्ल्यू (आई, जे) डब्ल्यू का परिमित खंड एआई + 1.aj-1aj है। प्रत्येक के लिए, हम एक नियमित भाषा एलक्यू, क्यू 'को परिभाषित करते हैं जिसे परिमित स्वचालित द्वारा स्वीकार किया जाता है। लेम्माः हम दावा करते हैं कि बुची ऑटोमेटन ए भाषा प्रमाण को पहचानता हैः मान लीजिए कि शब्द और क्यू0, क्यू1, क्यू2,. डब्ल्यू पर ए का एक स्वीकार्य रन है। इसलिए, क्यू0 में है और एफ में एक ऐसी स्थिति होनी चाहिए जो स्वीकार करने वाले रन में असीम रूप से अक्सर होती है। आइए सूचकांक i0, i1, i2 के सख्ती से बढ़ते अनंत अनुक्रम को चुनें. जैसे कि, सभी k ≤ 0 के लिए, है। इसलिए, और, सभी के लिए, इसलिए, इसके विपरीत, मान लीजिए कि कुछ के लिए और इसलिए, एक अनंत और सख्ती से बढ़ता अनुक्रम i0, i1, i2 है. जैसे कि और, सभी के लिए Lq, q 'की परिभाषा के अनुसार, शब्द w (0, i0) पर से एक का एक सीमित रन है। सभी k ≤ 0 के लिए, शब्द w (ik, ik + 1) से एक सीमित रन है। इस निर्माण से, ए का एक रन होता है, जो असीम रूप से अक्सर शुरू होता है और जिसमें होता है। इसलिए,। मोनाडिक द्वितीय-क्रम तर्क के समतुल्यता बुची ने 1962 में दिखाया कि ω-नियमित भाषाएँ ठीक वही हैं जो S1S नामक एक विशेष मोनाडिक द्वितीय-क्रम तर्क में परिभाषित की जा सकती हैं। ग्रंथ सूची वोल्फगैंग थॉमस, "अनंत वस्तुओं पर स्वचालित"। जान वैन लीउवेन, संपादक, सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका, खंड बीः औपचारिक मॉडल और शब्दार्थ, पृष्ठ 133-192। एल्सेवियर साइंस पब्लिशर्स, एम्स्टर्डम, 1990। औपचारिक भाषाएँ