لغة أوميغا

في نظرية اللغات الرسمية ضمن علوم الحاسوب النظرية ، تُعرَّف لغة ω بأنها مجموعة من الكلمات اللانهائية، حيث تُمثل الكلمة اللانهائية سلسلةً لانهائية الطول (وتحديدًا سلسلة بطول ω) من الرموز . هنا، يشير ω إلى أول عدد ترتيبي لانهائي ، والذي يُمثل مجموعة الأعداد الطبيعية .

ليكن Σ مجموعة من الرموز (ليست بالضرورة منتهية). وفقًا للتعريف القياسي من نظرية اللغة الرسمية ، فإن Σ ^* هي مجموعة جميع الكلمات المنتهية على Σ. لكل كلمة منتهية طول، وهو عدد طبيعي. بالنظر إلى كلمة w طولها n ، يمكن اعتبار w دالة من المجموعة {0,1,..., n − 1} → Σ، حيث تمثل القيمة عند الموضع i الرمز الموجود في الموضع i . وبالمثل، يمكن اعتبار الكلمات غير المنتهية، أو كلمات ω، دوالًا من${\displaystyle \mathbb {N} }$إلى Σ. يُرمز إلى مجموعة جميع الكلمات اللانهائية على Σ بالرمز Σ ^ω . تُكتب مجموعة جميع الكلمات المنتهية واللانهائية على Σ أحيانًا بالرمز Σ ^∞ أو Σ ^≤ω .

وبالتالي فإن لغة ω L على Σ هي مجموعة فرعية من Σ ^ω .

بعض العمليات الشائعة المعرفة في لغات ω هي:

التقاطع والاتحاد

بالنظر إلى اللغات ω L و M ، فإن كل من L ∪ M و L ∩ M هي لغات ω.

الربط الأيسر

لتكن L لغة ω، و K لغة ذات كلمات محدودة فقط. عندئذٍ يمكن ربط K من اليسار، ومن اليسار فقط ، بـ L للحصول على لغة ω الجديدة KL .

أوميغا (تكرار لا نهائي)

كما تشير الرموز، فإن العملية${\displaystyle (\cdot )^{\omega }}$هي النسخة اللانهائية لمؤثر نجمة كلين على اللغات ذات الطول المحدود. بالنظر إلى لغة صورية L ، ^فإن Lω هي لغة ω لجميع المتتاليات اللانهائية من الكلمات من L ؛ من وجهة النظر الوظيفية، لجميع الدوال${\displaystyle \mathbb {N} \to L}$.

البادئات

ليكن w كلمة من نوع ω. عندئذٍ تحتوي اللغة الرسمية Pref( w ) على كل بادئة منتهية من w .

حد

بالنظر إلى لغة ذات طول محدود L ، فإن الكلمة w ذات الطول ω تقع في نهاية L إذا وفقط إذا كانت Pref( w ) ∩ L مجموعة غير منتهية . بعبارة أخرى، لأي عدد طبيعي كبير n ، من الممكن دائمًا اختيار كلمة ما في L ، طولها أكبر من n ، وتكون بادئة للكلمة w . يمكن كتابة عملية النهاية على L على النحو التالي: L ^δ أو${\displaystyle {\vec {L}}}$.

يمكن تحويل المجموعة Σ ^{ω إلى} فضاء متري من خلال تعريف المقياس${\displaystyle d:\Sigma ^{\omega }\times \Sigma ^{\omega }\rightarrow \mathbb {R} }$مثل:

${\displaystyle d(w,v)=\inf\{2^{-|x|}\mid x\in \Sigma ^{*}\ {\text{and}}\ x\in {\text{Pref}}(w)\cap {\text{Pref}}(v)\}}$

حيث يُفسَّر | x | على أنه "طول x " (عدد الرموز في x )، و inf هو الحد الأدنى على مجموعات الأعداد الحقيقية .${\displaystyle w=v}$إذن لا يوجد بادئة طويلة x، وبالتالي${\displaystyle d(w,v)=0}$التناظر واضح. وتنتج خاصية التعدي من حقيقة أنه إذا كان للـ w و v بادئة مشتركة قصوى بطول m، وكان للـ v و u بادئة مشتركة قصوى بطول n، فإن الأولى${\displaystyle \min\{m,n\}}$يجب أن تكون الأحرف w و u متطابقة، لذا${\displaystyle d(w,u)\leq 2^{-\min\{m,n\}}\leq 2^{-m}+2^{-n}=d(w,v)+d(v,u)}$وبالتالي فإن d هو مقياس.

تُعدّ مجموعة اللغات المنتظمة من نوع ω الفئة الفرعية الأكثر استخدامًا من بين لغات ω ، والتي تتميز بخاصية مفيدة تتمثل في إمكانية التعرف عليها بواسطة آلات بوشي . وبالتالي، فإن مسألة تحديد انتماء اللغة المنتظمة من نوع ω قابلة للحل باستخدام آلة بوشي، وهي مسألة حسابية بسيطة نسبيًا.

إذا كانت اللغة Σ هي مجموعة القوى لمجموعة (تسمى "القضايا الذرية") فإن اللغة ω هي خاصية زمنية خطية ، والتي يتم دراستها في التحقق من النموذج .

• بيرين، د. وبين ، ج.-إ. " الكلمات اللانهائية: الأوتوماتا، أنصاف المجموعات، المنطق والألعاب ". الرياضيات البحتة والتطبيقية المجلد 141، إلسيفير، 2004.
• ستايجر، ل. " لغات ω ". في: جي. روزنبرغ وأ . سالوما ، محرران، دليل اللغات الرسمية ، المجلد 3، الصفحات 339-387. سبرينغر-فيرلاغ، برلين، 1997.
• توماس، دبليو. "الأتمتة على الكائنات اللانهائية". في جان فان ليوين ، محرر، دليل علوم الحاسوب النظرية ، المجلد ب: النماذج الرسمية والدلالات، الصفحات 133-192. دار نشر إلسيفير للعلوم، أمستردام، 1990.