زبان امگا

فرض می‌کنیم Σ الفبایی دلخواه باشد. یک رشته نامتناهی، که به آن رشته امگا نیز گفته می‌شود، یک توالی نامتناهی از حروف الفبای Σ به صورت ${\displaystyle {\text{a}}_0^{}{\text{a}}_1^{}{\text{a}}_2^{}\cdot \cdot \cdot }$

به هر مجموعه ${\displaystyle L\subseteq {\mathrm{\Sigma }}^{\omega }}$

کاربرد

تأیید برنامه (verification): به عنوان کدبندی اجراهای پایان‌ناپذیر یک برنامه.

حساب (arithmetic): به عنوان کدبندی‌های مجموعه‌های اعداد حقیقی.

تکرار ω (به انگلیسی: ω-iteration) برای زبان ${\displaystyle L\subseteq {\mathrm{\Sigma }}^{\ast }}$

توجه داریم که برخلاف مفهوم مشابه در مورد رشته‌های متناهی که در آن ${\displaystyle \{ϵ{\}}^{\ast }=\{\mathrm{\varnothing }\}}$

برخی از عملیات‌های تعریف شده بر روی زبان‌های امگا عبارت‌اند از:

• اجتماع و اشتراک: اگر ${\displaystyle L}$
  و ${\displaystyle L^{{}^{\prime }}}$
  دو زبان امگا باشند، اجتماع و اشتراک آنها نیز زبان امگا هستند که به ترتیب به صورت ${\displaystyle L\cup L^{{}^{\prime }}=\{w|w\in L\vee w\in L^{{}^{\prime }}\}}$
  و ${\displaystyle L\cap L^{{}^{\prime }}=\{w|w\in L\wedge w\in L^{{}^{\prime }}\}}$
  تعریف می‌شوند.
• الحاق: الحاق یک زبان امگای ${\displaystyle L}$
  و یک زبان یا زبان امگای ${\displaystyle L^{{}^{\prime }}}$
  ، یک زبان امگا است که به صورت ${\displaystyle L.L^{{}^{\prime }}=\{w_1{w}_2|w_1\in L\wedge w_2\in L^{{}^{\prime }}\}}$
  تعریف می‌شود.
• پیشوند: اگر w یک رشته امگا باشد، زبان صوری ${\displaystyle pref(w)}$
  همهٔ پیشوندهای w را در خود دارد و پیشوند w نامیده می‌شود.
• حد: اگر ${\displaystyle L}$
  یک زبان با طول متناهی باشد، رشته امگای w را در حد ${\displaystyle L}$
  می‌گوییم اگر و تنها اگر ${\displaystyle pref(w)\cap L}$
  یک مجموعه نامتناهی باشد. عملیات حد بر روی زبان ${\displaystyle L}$
  را با ${\displaystyle L^{\delta }}$
  نشان می‌دهیم.

فاصله بین دو رشته امگا به صورت یک تابع به شکل ${\displaystyle d:{\mathrm{\Sigma }}^{\omega }\times {\mathrm{\Sigma }}^{\omega }\to R}$

در تعریف بالا ${\displaystyle |x|}$

به این ترتیب اگر ${\displaystyle w_1=w_2}$

مهمترین زیر کلاس زبان‌های امگا، زبان‌های منظم امگا (به انگلیسی: omega-regular) هستند که تعریف زبان‌های منظم را به رشته‌های نامتناهی تعمیم می‌دهند.

زبان‌های منظم امگا

زبان امگای L یک زبان منظم امگا است اگر به یکی از شکل‌های زیر باشد:

• ${\displaystyle A^{\omega }}$
  که در آن A یک زبان منظم غیر تهی است که رشته تهی را در خود ندارد.
• ${\displaystyle A.B}$
  که در آن A یک زبان منظم و B یک زبان منظم امگا است.
• ${\displaystyle A\cup 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