به هر مجموعه از رشته های به طول نامتناهی از یک الفبای مشخص، یک زبان امگا ( زبان ω ) تعریف شده بر روی آن الفبا می گویند.
فرض می کنیم Σ الفبایی دلخواه باشد. یک رشته نامتناهی، که به آن رشته امگا نیز گفته می شود، یک توالی نامتناهی از حروف الفبای Σ به صورت a 0 a 1 a 2 ⋅ ⋅ ⋅ است. همان طور که هر رشته متناهی به طول n از الفبای Σ را می توان با یک تابع به صورت f : { 0 , 1 , 2 , . . . , n − 1 } → Σ نمایش داد که در آن f ( i ) نمایش حرف i ام رشته است، هر رشته امگا از این الفبا را نیز می توان به صورت یک تابع f : N → Σ در نظر گرفت که در آن f ( n ) حرف n ام در رشته مورد نظر است. هم چنین در مقابل Σ ∗ که در نظریه زبان صوری به مجموعه همه رشته های متناهی از الفبای Σ گفته می شود، مجموعه همهٔ رشته های امگا که بر روی الفبای Σ تعریف می شود با Σ ω نشان داده می شود. اجتماع Σ ω و Σ ∗ یعنی مجموعه همهٔ رشته های الفبای Σ با Σ ∞ نمایش داده می شود.
به هر مجموعه L ⊆ Σ ω از رشته های امگا، یک زبان امگا گفته می شود.
تأیید برنامه ( verification ) : به عنوان کدبندی اجراهای پایان ناپذیر یک برنامه.
حساب ( arithmetic ) : به عنوان کدبندی های مجموعه های اعداد حقیقی.
تکرار ω ( به انگلیسی: ω - iteration ) برای زبان L ⊆ Σ ∗ ، زبان امگای L ω است که به صورت L ω = { w 1 w 2 w 3 . . . | w i ∈ L ∖ { ϵ } } تعریف می شود.
توجه داریم که برخلاف مفهوم مشابه در مورد رشته های متناهی که در آن { ϵ } ∗ = { ∅ } ، در مورد تکرار ω تساوی { ϵ } ω = { ∅ } به این دلیل که همهٔ رشته های L ω باید دارای طول نامتناهی باشند، نمی تواند درست باشد و بنابراین داریم: { ϵ } ω = ∅ .
برخی از عملیات های تعریف شده بر روی زبان های امگا عبارت اند از:
• اجتماع و اشتراک: اگر 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 ⋅ ⋅ ⋅ است. همان طور که هر رشته متناهی به طول n از الفبای Σ را می توان با یک تابع به صورت f : { 0 , 1 , 2 , . . . , n − 1 } → Σ نمایش داد که در آن f ( i ) نمایش حرف i ام رشته است، هر رشته امگا از این الفبا را نیز می توان به صورت یک تابع f : N → Σ در نظر گرفت که در آن f ( n ) حرف n ام در رشته مورد نظر است. هم چنین در مقابل Σ ∗ که در نظریه زبان صوری به مجموعه همه رشته های متناهی از الفبای Σ گفته می شود، مجموعه همهٔ رشته های امگا که بر روی الفبای Σ تعریف می شود با Σ ω نشان داده می شود. اجتماع Σ ω و Σ ∗ یعنی مجموعه همهٔ رشته های الفبای Σ با Σ ∞ نمایش داده می شود.
به هر مجموعه L ⊆ Σ ω از رشته های امگا، یک زبان امگا گفته می شود.
تأیید برنامه ( verification ) : به عنوان کدبندی اجراهای پایان ناپذیر یک برنامه.
حساب ( arithmetic ) : به عنوان کدبندی های مجموعه های اعداد حقیقی.
تکرار ω ( به انگلیسی: ω - iteration ) برای زبان L ⊆ Σ ∗ ، زبان امگای L ω است که به صورت L ω = { w 1 w 2 w 3 . . . | w i ∈ L ∖ { ϵ } } تعریف می شود.
توجه داریم که برخلاف مفهوم مشابه در مورد رشته های متناهی که در آن { ϵ } ∗ = { ∅ } ، در مورد تکرار ω تساوی { ϵ } ω = { ∅ } به این دلیل که همهٔ رشته های L ω باید دارای طول نامتناهی باشند، نمی تواند درست باشد و بنابراین داریم: { ϵ } ω = ∅ .
برخی از عملیات های تعریف شده بر روی زبان های امگا عبارت اند از:
• اجتماع و اشتراک: اگر 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 }} نشان می دهیم.
wiki: زبان امگا