From Wikipedia, the free encyclopedia
به هر مجموعه از رشتههای به طول نامتناهی از یک الفبای مشخص، یک زبان امگا (زبان ω) تعریف شده بر روی آن الفبا میگویند.
فرض میکنیم Σ الفبایی دلخواه باشد. یک رشته نامتناهی، که به آن رشته امگا نیز گفته میشود، یک توالی نامتناهی از حروف الفبای Σ به صورت است. همانطور که هر رشته متناهی به طول n از الفبای Σ را میتوان با یک تابع به صورت نمایش داد که در آن نمایش حرف i ام رشتهاست، هر رشته امگا از این الفبا را نیز میتوان به صورت یک تابع در نظر گرفت که در آن حرف n ام در رشته مورد نظر است. هم چنین در مقابل که در نظریه زبان صوری به مجموعه همه رشتههای متناهی از الفبای Σ گفته میشود، مجموعه همهٔ رشتههای امگا که بر روی الفبای Σ تعریف میشود با نشان داده میشود. اجتماع و یعنی مجموعه همهٔ رشتههای الفبای Σ با نمایش داده میشود.
به هر مجموعه از رشتههای امگا، یک زبان امگا گفته میشود.
تأیید برنامه (verification): به عنوان کدبندی اجراهای پایانناپذیر یک برنامه.
حساب (arithmetic): به عنوان کدبندیهای مجموعههای اعداد حقیقی.
تکرار ω (به انگلیسی: ω-iteration) برای زبان ، زبان امگای است که به صورت تعریف میشود.
توجه داریم که برخلاف مفهوم مشابه در مورد رشتههای متناهی که در آن ، در مورد تکرار ω تساوی به این دلیل که همهٔ رشتههای باید دارای طول نامتناهی باشند، نمیتواند درست باشد و بنابراین داریم: .
برخی از عملیاتهای تعریف شده بر روی زبانهای امگا عبارتاند از:
فاصله بین دو رشته امگا به صورت یک تابع به شکل تعریف میشود که در آن .
در تعریف بالا طول x و inf زیرینه در مجموعه اعداد حقیقی است.
به این ترتیب اگر خواهیم داشت: .
مهمترین زیر کلاس زبانهای امگا، زبانهای منظم امگا (به انگلیسی: omega-regular) هستند که تعریف زبانهای منظم را به رشتههای نامتناهی تعمیم میدهند.
زبان امگای L یک زبان منظم امگا است اگر به یکی از شکلهای زیر باشد:
ماشین Büchi که توسط J.R. Büchi تعریف شدهاست به عنوان تشخیص دهنده زبانهای منظم امگا مطرح میباشد که به این ترتیب مسئله عضویت این زبانها تصمیمپذیر با وجود این ماشین تصمیم پذیر خواهد بود.
شکل ظاهری این ماشین مانند DFA و NFA است اما شرط پذیرش در آن متفاوت است.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.