Omega language
सैद्धांतिक कंप्यूटर विज्ञान के भीतर औपचारिक भाषा सिद्धांत में, एक अनंत शब्द प्रतीकों का एक अनंत-लंबाई अनुक्रम (विशेष रूप से, एक ω-लंबाई अनुक्रम) है, और एक ω-भाषा अनंत शब्दों का एक समूह है। यहाँ, ω पहली क्रमिक संख्या, प्राकृतिक संख्याओं के समूह को संदर्भित करता है। औपचारिक परिभाषा मान लीजिए कि यह प्रतीकों का एक समूह है (आवश्यक रूप से सीमित नहीं)। औपचारिक भाषा सिद्धांत से मानक परिभाषा का पालन करते हुए, σ * सभी परिमित शब्दों का समूह है। प्रत्येक परिमित शब्द की एक लंबाई होती है, जो एक प्राकृतिक संख्या है। n लंबाई के एक शब्द डब्ल्यू को देखते हुए, डब्ल्यू को सेट {0,1,., n − 1} → σ से एक फलन के रूप में देखा जा सकता है, जिसका मान i पर स्थिति i पर प्रतीक देता है। अनन्त शब्द, या ω-शब्द, को इसी तरह से कार्य के रूप में देखा जा सकता है। सभी अनंत शब्दों के समूह को σω पर निरूपित किया जाता है। सभी परिमित और अनंत शब्दों के समुच्चय को कभी-कभी  निष्पाप या  निष्पाप लिखा जाता है। इस प्रकार एक ω-भाषा L ओवर β, β का एक उपसमुच्चय है। संचालन ω-भाषाओं पर परिभाषित कुछ सामान्य संचालन हैंः अंतःच्छेदन और संघ दिए गए ω-भाषाएँ L और M, दोनों ω-भाषाएँ हैं। वाम संयोजन मान लीजिए कि L एक ω-भाषा है, और K केवल परिमित शब्दों की भाषा है। फिर K को बाईं ओर, और केवल बाईं ओर, L से जोड़ा जा सकता है ताकि नई ω-भाषा KL प्राप्त हो सके। जैसा कि संकेतन संकेत देता है, ऑपरेशन सीमित-लंबाई की भाषाओं पर क्लेन स्टार ऑपरेटर का अनंत संस्करण है। एक औपचारिक भाषा L को देखते हुए, Lω L से शब्दों के सभी अनंत अनुक्रमों की ω-भाषा है; कार्यात्मक दृष्टि से, सभी कार्यों की। उपसर्ग मान लीजिए कि डब्ल्यू एक ω-शब्द है। फिर औपचारिक भाषा प्रीफ (डब्ल्यू) में डब्ल्यू का प्रत्येक परिमित उपसर्ग होता है। सीमा एक सीमित-लंबाई वाली भाषा एल को देखते हुए, एक ω-शब्द डब्ल्यू एल की सीमा में होता है यदि और केवल अगर एक अनंत सेट हो। दूसरे शब्दों में, एक मनमाने ढंग से बड़ी प्राकृतिक संख्या n के लिए, L में कुछ शब्द चुनना हमेशा संभव है, जिसकी लंबाई n से अधिक है, और जो w का उपसर्ग है। L पर सीमा संचालन को Lδ या लिखा जा सकता है। ω-शब्दों के बीच की दूरी मीट्रिक की परिभाषा के अनुसार एक मीट्रिक स्थान में समुच्चय को इस प्रकार बनाया जा सकता हैः जहाँ |x। की व्याख्या "x की लंबाई" (x में प्रतीकों की संख्या) के रूप में की जाती है, और inf वास्तविक संख्याओं के समुच्चयों पर अनंत है। यदि तब कोई सबसे लंबा उपसर्ग x और ऐसा नहीं है। समरूपता स्पष्ट है। पारगमनता इस तथ्य से होती है कि यदि डब्ल्यू और वी में लंबाई एम और वी का अधिकतम साझा उपसर्ग है और यू में लंबाई एन का अधिकतम साझा उपसर्ग है तो डब्ल्यू और यू के पहले वर्ण समान होने चाहिए। अतः d एक मीट्रिक है। महत्वपूर्ण उपवर्ग ω-भाषाओं का सबसे व्यापक रूप से उपयोग किया जाने वाला उपवर्ग ω-नियमित भाषाओं का समूह है, जो बुची ऑटोमेटा द्वारा पहचाने जाने योग्य होने के उपयोगी गुण का आनंद लेते हैं। इस प्रकार ω-नियमित भाषा सदस्यता की निर्णय समस्या बुची स्वचालित का उपयोग करके निर्णायक है, और गणना करने के लिए काफी सरल है। यदि भाषा एक समुच्चय का शक्ति समुच्चय है (जिसे "परमाणु प्रस्ताव" कहा जाता है) तो ω-भाषा एक रैखिक समय गुण है, जिसका मॉडल जाँच में अध्ययन किया जाता है। ग्रंथ सूची पेरिन, डी. और पिन, जे. ई. "अनंत शब्दः स्वचालित, अर्धसमूह, तर्क और खेल"। शुद्ध और अनुप्रयुक्त गणित खंड 141, एल्सेवियर, 2004। स्टैगर, एल. "ω-भाषाएँ"। जी. रोजेनबर्ग और ए. सलोमा में, संपादक, औपचारिक भाषाओं की पुस्तिका, खंड 3, पृष्ठ 339-387। स्प्रिंगर-वेरलैग, बर्लिन, 1997। थॉमस, डब्ल्यू. "अनंत वस्तुओं पर ऑटोमेटा"। जान वैन लीउवेन, संपादक, सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका, खंड बीः औपचारिक मॉडल और शब्दार्थ, पृष्ठ 133-192। एल्सेवियर साइंस पब्लिशर्स, एम्स्टर्डम, 1990। गणना का सिद्धांत औपचारिक भाषाएँ