Omega language
نظریاتی کمپیوٹر سائنس کے اندر رسمی زبان کے نظریہ میں، ایک لامحدود لفظ علامتوں کی ایک لامحدود لمبائی کی ترتیب (خاص طور پر، ایک ω-لمبائی کی ترتیب) ہے، اور ایک ω-زبان لامحدود الفاظ کا مجموعہ ہے۔ یہاں، ω سے مراد پہلا آرڈینل نمبر، قدرتی اعداد کا مجموعہ ہے۔ رسمی تعریف آئیے کہ یہ علامتوں کا ایک مجموعہ ہے (ضروری نہیں کہ یہ محدود ہو)۔ رسمی زبان کے نظریہ سے معیاری تعریف کی پیروی کرتے ہوئے، σ * تمام محدود الفاظ کا مجموعہ ہے۔ ہر محدود لفظ کی لمبائی ہوتی ہے، جو کہ ایک قدرتی عدد ہے۔ n لمبائی کے لفظ w کو دیکھتے ہوئے، w کو سیٹ {0,1,., n − 1} → σ سے ایک فنکشن کے طور پر دیکھا جا سکتا ہے، جس کی قیمت i پر پوزیشن i پر علامت دیتی ہے۔ لامحدود الفاظ، یا ω-الفاظ، کو بھی اسی طرح سے فنکشن کے طور پر دیکھا جا سکتا ہے۔ تمام لامحدود الفاظ کے مجموعے کو σω سے ظاہر کیا جاتا ہے۔ تمام محدود اور لامحدود الفاظ کا مجموعہ جو  निष्प سے زیادہ ہے بعض اوقات  निष्प سے φ یا  निष्प سے φ لکھا جاتا ہے۔ اس طرح ایک ω-زبان L اوور σ، σω کا ذیلی مجموعہ ہے۔ آپریشنز ω-زبانوں پر بیان کردہ کچھ عام آپریشنز یہ ہیں: انٹرسیکشن اور یونین دی گئی ω-زبانیں L اور M، دونوں ω-زبانیں ہیں۔ لیفٹ کنکیٹی نیشن L کو ایک ω-زبان ہونے دیں، اور K کو صرف محدود الفاظ کی زبان ہونے دیں۔ پھر K کو بائیں طرف، اور صرف بائیں طرف، L سے جوڑا جا سکتا ہے تاکہ نئی ω-زبان KL حاصل ہو۔ اومیگا (لامحدود تکرار) جیسا کہ اشارے اشارہ کرتے ہیں، آپریشن محدود لمبائی والی زبانوں پر کلین اسٹار آپریٹر کا لامحدود ورژن ہے۔ رسمی زبان L کو دیکھتے ہوئے، Lω L سے الفاظ کے تمام لامحدود ترتیبات کی ω-زبان ہے ؛ فعال نقطہ نظر میں، تمام افعال کی۔ سابقہ W کو ایک ω-لفظ ہونے دیں۔ پھر رسمی زبان پریف (ڈبلیو) میں ڈبلیو کا ہر محدود سابقہ ہوتا ہے۔ حد ایک محدود لمبائی والی زبان ایل کو دیکھتے ہوئے، ایک ω-لفظ ڈبلیو ایل کی حد میں ہوتا ہے اگر اور صرف اس صورت میں جب ایک لامحدود سیٹ ہو۔ دوسرے لفظوں میں، من مانی طور پر بڑے قدرتی عدد n کے لیے، L میں کسی ایسے لفظ کا انتخاب کرنا ہمیشہ ممکن ہے، جس کی لمبائی n سے زیادہ ہو، اور جو w کا سابقہ ہو۔ L پر لمٹ آپریشن کو Lδ یا لکھا جا سکتا ہے۔ ω-الفاظ کے درمیان فاصلہ سیٹ کو میٹرک کی تعریف کے مطابق میٹرک اسپیس میں اس طرح بنایا جا سکتا ہے: جہاں |x | کی تشریح "x کی لمبائی" (x میں علامتوں کی تعداد) کے طور پر کی جاتی ہے، اور inf حقیقی اعداد کے سیٹوں پر لامحدود ہے۔ اگر پھر کوئی طویل ترین سابقہ x اور ایسا نہیں ہے۔ ہم آہنگی واضح ہے۔ منتقلی اس حقیقت سے ہوتی ہے کہ اگر ڈبلیو اور وی میں لمبائی ایم اور وی کا زیادہ سے زیادہ مشترکہ سابقہ ہے اور یو میں لمبائی این کا زیادہ سے زیادہ مشترکہ سابقہ ہے تو ڈبلیو اور یو کے پہلے حروف یکساں ہونے چاہئیں۔ اس لیے d ایک میٹرک ہے۔ اہم ذیلی کلاسیں ω-زبانوں کی سب سے زیادہ وسیع پیمانے پر استعمال ہونے والی ذیلی کلاس ω-باقاعدہ زبانوں کا مجموعہ ہے، جو بوچی آٹومیٹا کے ذریعے پہچانی جانے کی مفید خاصیت سے لطف اندوز ہوتی ہیں۔ اس طرح ω-باقاعدہ زبان کی رکنیت کا فیصلہ کرنے کا مسئلہ بوچی آٹومیٹن کا استعمال کرتے ہوئے فیصلہ کن ہے، اور حساب لگانا کافی سیدھا ہے۔ اگر زبان کسی سیٹ کا پاور سیٹ ہے (جسے "جوہری تجاویز" کہا جاتا ہے) تو ω-زبان ایک لکیری ٹائم پراپرٹی ہے، جس کا مطالعہ ماڈل چیکنگ میں کیا جاتا ہے۔ بیبلیوگرافی پیرین، ڈی۔ اور پن، جے۔ ای۔ "انفنائٹ ورڈز: آٹومیٹا، سیمی گروپس، لاجک اینڈ گیمز"۔ خالص اور اطلاقی ریاضی جلد 141، ایلسیویئر، 2004۔ اسٹیگر، ایل۔ "ω-زبانیں"۔ جی روزن برگ اور اے سولوما میں، ایڈیٹرز، ہینڈ بک آف فارمل لینگویجز، جلد 3، صفحات 339-387۔ سپرنگر-ورلاگ، برلن، 1997۔ تھامس، ڈبلیو۔ "آٹومیٹا آن انفینٹ آبجیکٹس"۔ جان وین لیوین، ایڈیٹر، ہینڈ بک آف تھیوریٹیکل کمپیوٹر سائنس، جلد بی: رسمی ماڈل اور سیمنٹکس، صفحات 133-192۔ ایلسیویئر سائنس پبلشرز، ایمسٹرڈیم، 1990۔ حساب کا نظریہ رسمی زبانیں