Omega-regular language
ω-باقاعدہ زبانیں ω-زبانوں کی ایک کلاس ہیں جو باقاعدہ زبانوں کی تعریف کو لامحدود الفاظ تک عام کرتی ہیں۔ رسمی تعریف ایک ω-زبان L ω-ریگولر ہے اگر اس کی شکل Aω ہو جہاں A ایک باقاعدہ زبان ہے جس میں خالی سٹرنگ AB نہیں ہے، ایک باقاعدہ زبان A کا امتزاج اور ایک ω-ریگولر زبان B (نوٹ کریں کہ BA اچھی طرح سے متعین نہیں ہے) A ≤ B جہاں A اور B ω-ریگولر زبانیں ہیں (اس اصول کو صرف محدود طور پر کئی بار لاگو کیا جا سکتا ہے) Aω کے عناصر A سے الفاظ کو لامحدود طور پر کئی بار جوڑ کر حاصل کیے جاتے ہیں۔ نوٹ کریں کہ اگر A باقاعدہ ہے، تو Aω لازمی طور پر ω-باقاعدہ نہیں ہے، کیونکہ A مثال کے طور پر {ε} ہو سکتا ہے، جو سیٹ صرف خالی تار پر مشتمل ہے، اس صورت میں Aω = A، جو کہ ω-زبان نہیں ہے اور اس لیے ω-باقاعدہ زبان نہیں ہے۔ یہ اس تعریف کا سیدھا سیدھا نتیجہ ہے کہ ω-باقاعدہ زبانیں قطعی طور پر A1B1ω کی شکل کی ω-زبانیں ہیں۔ کچھ n کے لیے ≤ anBnω، جہاں Ais اور Bis باقاعدہ زبانیں ہیں اور Bis خالی تار پر مشتمل نہیں ہیں۔ بوچی آٹومیٹن تھیوریم کے مساوی: ایک ω-زبان کو بوچی آٹومیٹن تسلیم کرتا ہے اگر اور صرف اس صورت میں جب وہ ω-ریگولر زبان ہو۔ ثبوت: ہر ω-باقاعدہ زبان کو غیر متعین بوچی آٹومیٹن کے ذریعے پہچانا جاتا ہے ؛ ترجمہ تعمیری ہے۔ ω-ریگولر زبان کی تعریف پر بوچی آٹومیٹا اور ساختی انڈکشن کی بندش کی خصوصیات کا استعمال کرتے ہوئے، یہ آسانی سے دکھایا جا سکتا ہے کہ کسی بھی دی گئی ω-ریگولر زبان کے لیے بوچی آٹومیٹن بنایا جا سکتا ہے۔ اس کے برعکس، کسی دیئے گئے بوچی آٹومیٹن کے لیے، ہم ایک ω-ریگولر زبان بناتے ہیں اور پھر ہم دکھائیں گے کہ اس زبان کو A سے پہچانا جاتا ہے۔ ایک ω-لفظ کے لیے w = a1a2. W (i, j) کو W کا محدود حصہ AI + 1.aj-1aj ہونے دیں۔ ہر ایک کے لیے، ہم ایک باقاعدہ زبان Lq، q 'کی وضاحت کرتے ہیں جسے محدود آٹومیٹن قبول کرتا ہے۔ لیما: ہم دعوی کرتے ہیں کہ بوچی آٹومیٹن اے زبان کے ثبوت کو تسلیم کرتا ہے: فرض کریں کہ لفظ اور q0، q1، q2،. W پر A کا ایک قبول شدہ رن ہے۔ لہذا، q0 میں ہے اور F میں ایسی حالت ہونی چاہیے جو قبول کرنے والے رن میں لامحدود کثرت سے ہوتی ہے۔ آئیے اشاریہ جات i0، i1، i2 کی سختی سے بڑھتی ہوئی لامحدود ترتیب کا انتخاب کریں۔ اس طرح کہ، تمام k ≤ 0 کے لیے، ہے۔ لہذا، اور، سب کے لیے، اس لیے، اس کے برعکس، فرض کریں کہ کچھ کے لیے اور اس لیے، ایک لامحدود اور سختی سے بڑھتی ہوئی ترتیب i0، i1، i2 ہے۔ اس طرح کہ اور، سب کے لیے Lq، q 'کی تعریف کے مطابق، لفظ w (0، i0) پر سے ایک تک کا ایک محدود سلسلہ ہے۔ تمام k ≤ 0 کے لیے، لفظ w (ik، ik + 1) سے لے کر آن تک کا ایک محدود سلسلہ ہوتا ہے۔ اس تعمیر سے، اے کا ایک رن ہوتا ہے، جو شروع ہوتا ہے اور جس میں لامحدود کثرت سے ہوتا ہے۔ اس لیے۔ موناڈک سیکنڈ آرڈر منطق کے مساوی بوچی نے 1962 میں دکھایا کہ ω-ریگولر زبانیں بالکل وہی ہیں جن کی تعریف ایک خاص موناڈک سیکنڈ آرڈر منطق میں کی جا سکتی ہے جسے S1S کہا جاتا ہے۔ کتابچہ ولف گینگ تھامس، "لامحدود اشیاء پر آٹومیٹا"۔ جان وین لیوین، ایڈیٹر، ہینڈ بک آف تھیوریٹیکل کمپیوٹر سائنس، جلد بی: رسمی ماڈل اور سیمنٹکس، صفحات 133-192۔ ایلسیویئر سائنس پبلشرز، ایمسٹرڈیم، 1990۔ رسمی زبانیں