لغة أوميغا المنتظمة
في علوم الحاسوب ونظرية اللغات الرسمية ، تُعدّ اللغات المنتظمة من نوع ω فئةً من لغات ω تُعمّم تعريف اللغات المنتظمة ليشمل الكلمات غير المحدودة. فبينما تقبل اللغات المنتظمة سلاسل نصية محدودة (مثل السلاسل التي تبدأ بالحرف a ، أو السلاسل التي تتناوب بين a و b )، تقبل اللغات المنتظمة من نوع ω كلمات غير محدودة (مثل المتتاليات غير المحدودة التي تبدأ بالحرف a ، أو المتتاليات غير المحدودة التي تتناوب بين a و b ).
التعريف الرسمي
لتكن A لغة . نرمز بـ A ω إلى المجموعة التي يتم الحصول على عناصرها عن طريق ربط الكلمات من A عددًا لا نهائيًا من المرات، أي مجموعة الدوال.
تُعرَّف فئة لغات ω المنتظمة ω استقرائيًا على النحو التالي
- A ω ، حيث A هي لغة منتظمة لا تحتوي على السلسلة الفارغة ، هي ω-منتظمة؛
- AB ، وهي سلسلة من لغة منتظمة A ولغة منتظمة ω B (لاحظ أن BA غير محددة جيدًا)، هي لغة منتظمة ω ؛
- A ∪ B ، حيث A و B لغتان منتظمتان من نوع ω (لا يمكن تطبيق هذه القاعدة إلا عددًا محدودًا من المرات)، هي لغة منتظمة من نوع ω.
لاحظ أنه إذا كانت A منتظمة، فإن A ω ليست بالضرورة منتظمة من النوع ω، حيث يمكن أن تكون A على سبيل المثال {ε}، وهي المجموعة التي تحتوي فقط على السلسلة الفارغة ، وفي هذه الحالة A ω = A ، وهي ليست لغة من النوع ω وبالتالي ليست لغة منتظمة من النوع ω.
إنها نتيجة مباشرة للتعريف أن اللغات المنتظمة ω هي بالضبط لغات ω من الشكل A 1 B 1 ω ∪ ... ∪ A n B n ω لبعض n ، حيث A i s و B i s هي لغات منتظمة و B i s لا تحتوي على السلسلة الفارغة.
مكافئ لآلة بوشي
نظرية — يتم التعرف على لغة ω بواسطة آلة بوشي إذا وفقط إذا كانت لغة منتظمة ω.
Every ω-regular language is recognized by a nondeterministic Büchi automaton; the translation is constructive. Using the closure properties of Büchi automata and structural induction over the definition of ω-regular language, it can be easily shown that a Büchi automaton can be constructed for any given ω-regular language.
Conversely, for a given Büchi automaton A = (Q, Σ, δ, I, F), we construct an ω-regular language and then we will show that this language is recognized by A. For an ω-word w = a1a2... let w(i,j) be the finite segment ai+1...aj−1aj of w. For every q, q' ∈ Q, we define a regular languageLq,q' that is accepted by the finite automaton (Q, Σ, δ, q, {q'}).
Lemma— We claim that the Büchi automaton A recognizes the language ⋃q∈I,q′∈FLq,q' (Lq',q'− {ε} )ω.
لنفترض أن الكلمة w ∈ L ( A ) وأن q₀ , q₁ , q₂ , ... هي سلسلة قبول من A على w . بالتالي، q₀ تنتمي إلى I ، ويجب أن توجد حالة q' في F بحيث تظهر q' عددًا لا نهائيًا من المرات في سلسلة القبول. لنختر متتالية لا نهائية متزايدة تمامًا من المؤشرات i₀ , i₁ , i₂ , ... بحيث يكون qᵢᵢᵢ هو q ' لكل k ≥ 0. بالتالي ، w (0, i₀ ) ∈ L( q₀ , q ') ، ولكل k ≥ 0، w ( iᵢᵢ , iᵢ₊₁ ) ∈ L ( q ', q ' ) . بالتالي ، w ∈ L ( q₀ , q ' ) ω .
- على النقيض، لنفترض أن w ∈ L q , q' ( L q',q' − { ε } ) ω لبعض q ∈ I و q '∈ F. بالتالي، توجد متتالية لانهائية ومتزايدة تمامًا i 0 , i 1 , i 2 ... بحيث w (0, i 0 ) ∈ L q,q' ، ولكل k ≥0، فإن w ( i k , i k +1 )∈ L q',q' . بحسب تعريف L q,q' ، توجد سلسلة منتهية من A من q إلى q' على الكلمة w (0, i 0 ). لكل k ≥0، توجد سلسلة منتهية من A من q' إلى q' على الكلمة w ( i k , i k +1 ). بناءً على هذا البناء، توجد سلسلة من A تبدأ من q وتظهر فيها q' عددًا لا نهائيًا من المرات. وبالتالي، فإن w ∈ L ( A ) .
التكافؤ مع منطق الرتبة الثانية الأحادي
أظهر بوشي في عام 1962 أن اللغات المنتظمة ω هي تحديدًا تلك التي يمكن تعريفها في منطق أحادي من الدرجة الثانية يسمى S1S.
للمزيد من القراءة
- فولفغانغ توماس، "الأوتوماتا على الكائنات اللانهائية". في جان فان ليوين ، محرر، دليل علوم الحاسوب النظرية، المجلد ب: النماذج الرسمية والدلالات ، الصفحات 133-192. دار نشر إلسيفير للعلوم، أمستردام، 1990.
- اللغات الرسمية
- كلمات لا نهائية