زبان امگا
به هر مجموعه از رشتههای به طول نامتناهی از یک الفبای مشخص، یک زبان امگا (زبان ω) تعریف شده بر روی آن الفبا میگویند.
تعریف رسمی
[ویرایش]فرض میکنیم Σ الفبایی دلخواه باشد. یک رشته نامتناهی، که به آن رشته امگا نیز گفته میشود، یک توالی نامتناهی از حروف الفبای Σ به صورت است. همانطور که هر رشته متناهی به طول n از الفبای Σ را میتوان با یک تابع به صورت نمایش داد که در آن نمایش حرف i ام رشتهاست، هر رشته امگا از این الفبا را نیز میتوان به صورت یک تابع در نظر گرفت که در آن حرف n ام در رشته مورد نظر است. هم چنین در مقابل که در نظریه زبان صوری به مجموعه همه رشتههای متناهی از الفبای Σ گفته میشود، مجموعه همهٔ رشتههای امگا که بر روی الفبای Σ تعریف میشود با نشان داده میشود. اجتماع و یعنی مجموعه همهٔ رشتههای الفبای Σ با نمایش داده میشود.
به هر مجموعه از رشتههای امگا، یک زبان امگا گفته میشود.
کاربرد
[ویرایش]تأیید برنامه (verification): به عنوان کدبندی اجراهای پایانناپذیر یک برنامه.
حساب (arithmetic): به عنوان کدبندیهای مجموعههای اعداد حقیقی.
تکرار ω (تکرار بینهایت)
[ویرایش]تکرار ω (به انگلیسی: ω-iteration) برای زبان ، زبان امگای است که به صورت تعریف میشود.
توجه داریم که برخلاف مفهوم مشابه در مورد رشتههای متناهی که در آن ، در مورد تکرار ω تساوی به این دلیل که همهٔ رشتههای باید دارای طول نامتناهی باشند، نمیتواند درست باشد و بنابراین داریم: .
عملیاتهای زبان امگا
[ویرایش]برخی از عملیاتهای تعریف شده بر روی زبانهای امگا عبارتاند از:
- اجتماع و اشتراک: اگر و دو زبان امگا باشند، اجتماع و اشتراک آنها نیز زبان امگا هستند که به ترتیب به صورت و تعریف میشوند.
- الحاق: الحاق یک زبان امگای و یک زبان یا زبان امگای ، یک زبان امگا است که به صورت تعریف میشود.
- پیشوند: اگر w یک رشته امگا باشد، زبان صوری همهٔ پیشوندهای w را در خود دارد و پیشوند w نامیده میشود.
- حد: اگر یک زبان با طول متناهی باشد، رشته امگای w را در حد میگوییم اگر و تنها اگر یک مجموعه نامتناهی باشد. عملیات حد بر روی زبان را با نشان میدهیم.
فاصله بین رشتههای امگا
[ویرایش]فاصله بین دو رشته امگا به صورت یک تابع به شکل تعریف میشود که در آن .
در تعریف بالا طول x و inf زیرینه در مجموعه اعداد حقیقی است.
به این ترتیب اگر خواهیم داشت: .
زیرکلاسها
[ویرایش]مهمترین زیر کلاس زبانهای امگا، زبانهای منظم امگا (به انگلیسی: omega-regular) هستند که تعریف زبانهای منظم را به رشتههای نامتناهی تعمیم میدهند.
زبانهای منظم امگا
[ویرایش]زبان امگای L یک زبان منظم امگا است اگر به یکی از شکلهای زیر باشد:
- که در آن A یک زبان منظم غیر تهی است که رشته تهی را در خود ندارد.
- که در آن A یک زبان منظم و B یک زبان منظم امگا است.
- که در آن A و B زبانهای منظم امگا هستند.
ماشین Büchi
[ویرایش]ماشین Büchi که توسط J.R. Büchi تعریف شدهاست به عنوان تشخیص دهنده زبانهای منظم امگا مطرح میباشد که به این ترتیب مسئله عضویت این زبانها تصمیمپذیر با وجود این ماشین تصمیم پذیر خواهد بود.
شکل ظاهری این ماشین مانند DFA و NFA است اما شرط پذیرش در آن متفاوت است.
منابع
[ویرایش]- Vincent Carnino, Sylvain Lombardy. Factorizations and Universal Automaton of Omega Languages. Developments in Language Theory, 2013
- Handbook of Formal Languages: Volume 3 Beyond Words
- Marcelo d’Amorim , Grigore Ro¸su. Efficient Monitoring of ω-Languages
- Dana Angluin, Dana Fisman. Learning Regular Omega Languages
- Omega-automaton