زبان امگا

به هر مجموعه از رشته‌های به طول نامتناهی از یک الفبای مشخص، یک **زبان امگا (زبان ω)** تعریف شده بر روی آن الفبا می‌گویند.

## تعریف رسمی
فرض می‌کنیم Σ الفبایی دلخواه باشد. یک رشته *نامتناهی*، که به آن ***رشته امگا*** نیز گفته می‌شود، یک توالی نامتناهی از حروف الفبای Σ به صورت a0a1a2... است. همان‌طور که هر رشته متناهی به طول n از الفبای Σ را می‌توان با یک تابع به صورت f:\{0,1,2,...,n-1\} \rightarrow\Sigma نمایش داد که در آن f(i) نمایش حرف i ام رشته‌است، هر رشته امگا از این الفبا را نیز می‌توان به صورت یک تابع f:N \rightarrow\Sigma در نظر گرفت که در آن f(n) حرف n ام در رشته مورد نظر است. هم چنین در مقابل \Sigma^* که در نظریه زبان صوری به مجموعه همه رشته‌های *متناهی* از الفبای Σ گفته می‌شود، مجموعه همهٔ رشته‌های امگا که بر روی الفبای Σ تعریف می‌شود با \Sigma^\omega نشان داده می‌شود. اجتماع \Sigma^\omega و \Sigma^* یعنی مجموعه همهٔ رشته‌های الفبای Σ با \Sigma^\infty نمایش داده می‌شود.

به هر مجموعه L\subseteq\Sigma^\omega از رشته‌های امگا، یک **زبان امگا** گفته می‌شود.

### کاربرد
**تأیید برنامه ([[:en:Verification|verification]])**: به عنوان کدبندی اجراهای پایان‌ناپذیر یک برنامه.

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

## تکرار ω (تکرار بی‌نهایت)
**تکرار ω** (به انگلیسی: *ω-iteration*) برای زبان L\subseteq\Sigma^*، زبان امگای L^\omega است که به صورت L^\omega=\{w_1w_2w_3...|\ w_i\in L\setminus\{\epsilon\}\} تعریف می‌شود.

توجه داریم که برخلاف مفهوم مشابه در مورد رشته‌های متناهی که در آن \{\epsilon\}^*=\{\emptyset\}، در مورد تکرار ω تساوی \{\epsilon\}^\omega=\{\emptyset\} به این دلیل که همهٔ رشته‌های L^\omega باید دارای طول نامتناهی باشند، نمی‌تواند درست باشد و بنابراین داریم: \{\epsilon\}^\omega=\emptyset.

## عملیات‌های زبان امگا
برخی از عملیات‌های تعریف شده بر روی زبان‌های امگا عبارت‌اند از:
* **اجتماع و اشتراک:** اگر L و L^' دو زبان امگا باشند، اجتماع و اشتراک آنها نیز زبان امگا هستند که به ترتیب به صورت L \cup L^'=\{w\ |\ w\in L \ \lor w \in L^'\} و L \cap L^'=\{w\ |\ w\in L \ \land w \in L^'\} تعریف می‌شوند.
* **الحاق:** الحاق یک زبان امگای L و یک زبان یا زبان امگای L^'، یک زبان امگا است که به صورت L.L^'=\{w_1w_2\ |\ w_1 \in L \ \land w_2 \in L^'\} تعریف می‌شود.
* **پیشوند:** اگر w یک رشته امگا باشد، زبان صوری pref(w) همهٔ پیشوندهای w را در خود دارد و *پیشوند* w نامیده می‌شود.
* **حد:** اگر Lیک زبان با طول متناهی باشد، رشته امگای w را در *حد <math>L</math>* می‌گوییم اگر و تنها اگر pref(w)\cap L یک مجموعه *نامتناهی* باشد. عملیات حد بر روی زبان *<math>L</math>* را با L^\delta نشان می‌دهیم.

## فاصله بین رشته‌های امگا
فاصله بین دو رشته امگا به صورت یک تابع به شکل d: \Sigma^\omega \times\Sigma^\omega\rightarrow R تعریف می‌شود که در آن d(w_1,w_2)=inf\{2^{-|x|}: x \in \Sigma^* \ \land\  x\in pref(w_1)\ \land\  x\in pref(w_2)\}.

در تعریف بالا |x| طول x و inf زیرینه در مجموعه اعداد حقیقی است.

به این ترتیب اگر w_1=w_2 خواهیم داشت: d(w_1,w_2)=0.

## زیرکلاس‌ها
مهمترین زیر کلاس زبان‌های امگا، زبان‌های ***منظم امگا (به انگلیسی: [[:en:Omega-regular_language|omega-regular]])*** هستند که تعریف زبان‌های منظم را به رشته‌های نامتناهی تعمیم می‌دهند.
بندانگشتی|Julius Richard Büchi

### زبان‌های منظم امگا
زبان امگای L یک زبان منظم امگا است اگر به یکی از شکل‌های زیر باشد:
* A^\omega که در آن A یک زبان منظم غیر تهی است که رشته تهی را در خود ندارد.
* A.B که در آن A یک زبان منظم و B یک زبان منظم امگا است.
* A \cup B که در آن A و B زبان‌های منظم امگا هستند.

#### ماشین Büchi
ماشین Büchi که توسط J.R. Büchi تعریف شده‌است به عنوان تشخیص دهنده زبان‌های منظم امگا مطرح می‌باشد که به این ترتیب مسئله عضویت این زبان‌ها تصمیم‌پذیر با وجود این ماشین تصمیم پذیر خواهد بود.
بندانگشتی|مثالی از ماشین 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

رده:زبان‌های صوری
رده:علوم نظری رایانه
رده:نظریه محاسبات