به هر مجموعه از رشته های به طول نامتناهی از یک الفبای مشخص، یک زبان امگا (زبان ω) تعریف شده بر روی آن الفبا می گویند.
اجتماع و اشتراک: اگر L {\displaystyle L} و L ′ {\displaystyle L^{'}} دو زبان امگا باشند، اجتماع و اشتراک آنها نیز زبان امگا هستند که به ترتیب به صورت L ∪ L ′ = { w | w ∈ L ∨ w ∈ L ′ } {\displaystyle L\cup L^{'}=\{w\ |\ w\in L\ \lor w\in L^{'}\}} و L ∩ L ′ = { w | w ∈ L ∧ w ∈ L ′ } {\displaystyle L\cap L^{'}=\{w\ |\ w\in L\ \land w\in L^{'}\}} تعریف می شوند.
الحاق: الحاق یک زبان امگای L {\displaystyle L} و یک زبان یا زبان امگای L ′ {\displaystyle L^{'}} ، یک زبان امگا است که به صورت L . L ′ = { w 1 w 2 | w 1 ∈ L ∧ w 2 ∈ L ′ } {\displaystyle L.L^{'}=\{w_{1}w_{2}\ |\ w_{1}\in L\ \land w_{2}\in L^{'}\}} تعریف می شود.
پیشوند: اگر w یک رشته امگا باشد، زبان صوری p r e f ( w ) {\displaystyle pref(w)} همهٔ پیشوندهای w را در خود دارد و پیشوند w نامیده می شود.
حد: اگر L {\displaystyle L} یک زبان با طول متناهی باشد، رشته امگای w را در حد L {\displaystyle L} می گوییم اگر و تنها اگر p r e f ( w ) ∩ L {\displaystyle pref(w)\cap L} یک مجموعه نامتناهی باشد. عملیات حد بر روی زبان L {\displaystyle L} را با L δ {\displaystyle L^{\delta }} نشان می دهیم.
فرض می کنیم Σ الفبایی دلخواه باشد. یک رشته نامتناهی، که به آن رشته امگا نیز گفته می شود، یک توالی نامتناهی از حروف الفبای Σ به صورت a 0 a 1 a 2 ⋅ ⋅ ⋅ {\displaystyle {\ce {a0a1a2...}}} است. همان طور که هر رشته متناهی به طول n از الفبای Σ را می توان با یک تابع به صورت f : { 0 , 1 , 2 , . . . , n − 1 } → Σ {\displaystyle f:\{0,1,2,...,n-1\}\rightarrow \Sigma } نمایش داد که در آن f ( i ) {\displaystyle f(i)} نمایش حرف i ام رشته است، هر رشته امگا از این الفبا را نیز می توان به صورت یک تابع f : N → Σ {\displaystyle f:N\rightarrow \Sigma } در نظر گرفت که در آن f ( n ) {\displaystyle f(n)} حرف n ام در رشته مورد نظر است. هم چنین در مقابل Σ ∗ {\displaystyle \Sigma ^{*}} که در نظریه زبان صوری به مجموعه همه رشته های متناهی از الفبای Σ گفته می شود، مجموعه همهٔ رشته های امگا که بر روی الفبای Σ تعریف می شود با Σ ω {\displaystyle \Sigma ^{\omega }} نشان داده می شود. اجتماع Σ ω {\displaystyle \Sigma ^{\omega }} و Σ ∗ {\displaystyle \Sigma ^{*}} یعنی مجموعه همهٔ رشته های الفبای Σ با Σ ∞ {\displaystyle \Sigma ^{\infty }} نمایش داده می شود.
به هر مجموعه L ⊆ Σ ω {\displaystyle L\subseteq \Sigma ^{\omega }} از رشته های امگا، یک زبان امگا گفته می شود.
تأیید برنامه (verification): به عنوان کدبندی اجراهای پایان ناپذیر یک برنامه.
اجتماع و اشتراک: اگر L {\displaystyle L} و L ′ {\displaystyle L^{'}} دو زبان امگا باشند، اجتماع و اشتراک آنها نیز زبان امگا هستند که به ترتیب به صورت L ∪ L ′ = { w | w ∈ L ∨ w ∈ L ′ } {\displaystyle L\cup L^{'}=\{w\ |\ w\in L\ \lor w\in L^{'}\}} و L ∩ L ′ = { w | w ∈ L ∧ w ∈ L ′ } {\displaystyle L\cap L^{'}=\{w\ |\ w\in L\ \land w\in L^{'}\}} تعریف می شوند.
الحاق: الحاق یک زبان امگای L {\displaystyle L} و یک زبان یا زبان امگای L ′ {\displaystyle L^{'}} ، یک زبان امگا است که به صورت L . L ′ = { w 1 w 2 | w 1 ∈ L ∧ w 2 ∈ L ′ } {\displaystyle L.L^{'}=\{w_{1}w_{2}\ |\ w_{1}\in L\ \land w_{2}\in L^{'}\}} تعریف می شود.
پیشوند: اگر w یک رشته امگا باشد، زبان صوری p r e f ( w ) {\displaystyle pref(w)} همهٔ پیشوندهای w را در خود دارد و پیشوند w نامیده می شود.
حد: اگر L {\displaystyle L} یک زبان با طول متناهی باشد، رشته امگای w را در حد L {\displaystyle L} می گوییم اگر و تنها اگر p r e f ( w ) ∩ L {\displaystyle pref(w)\cap L} یک مجموعه نامتناهی باشد. عملیات حد بر روی زبان L {\displaystyle L} را با L δ {\displaystyle L^{\delta }} نشان می دهیم.
فرض می کنیم Σ الفبایی دلخواه باشد. یک رشته نامتناهی، که به آن رشته امگا نیز گفته می شود، یک توالی نامتناهی از حروف الفبای Σ به صورت a 0 a 1 a 2 ⋅ ⋅ ⋅ {\displaystyle {\ce {a0a1a2...}}} است. همان طور که هر رشته متناهی به طول n از الفبای Σ را می توان با یک تابع به صورت f : { 0 , 1 , 2 , . . . , n − 1 } → Σ {\displaystyle f:\{0,1,2,...,n-1\}\rightarrow \Sigma } نمایش داد که در آن f ( i ) {\displaystyle f(i)} نمایش حرف i ام رشته است، هر رشته امگا از این الفبا را نیز می توان به صورت یک تابع f : N → Σ {\displaystyle f:N\rightarrow \Sigma } در نظر گرفت که در آن f ( n ) {\displaystyle f(n)} حرف n ام در رشته مورد نظر است. هم چنین در مقابل Σ ∗ {\displaystyle \Sigma ^{*}} که در نظریه زبان صوری به مجموعه همه رشته های متناهی از الفبای Σ گفته می شود، مجموعه همهٔ رشته های امگا که بر روی الفبای Σ تعریف می شود با Σ ω {\displaystyle \Sigma ^{\omega }} نشان داده می شود. اجتماع Σ ω {\displaystyle \Sigma ^{\omega }} و Σ ∗ {\displaystyle \Sigma ^{*}} یعنی مجموعه همهٔ رشته های الفبای Σ با Σ ∞ {\displaystyle \Sigma ^{\infty }} نمایش داده می شود.
به هر مجموعه L ⊆ Σ ω {\displaystyle L\subseteq \Sigma ^{\omega }} از رشته های امگا، یک زبان امگا گفته می شود.
تأیید برنامه (verification): به عنوان کدبندی اجراهای پایان ناپذیر یک برنامه.
wiki: زبان امگا