Омега-язык (ω-язык) — это множество бесконечно длинных последовательностей символов.

Формальное определение

Пусть ${\displaystyle \Sigma }$ — множество символов (необязательно конечное), называемое алфавитом. По стандартной теории формальных языков , ${\displaystyle \Sigma ^{*}}$ — это множество всех конечных слов над ${\displaystyle \Sigma }$ . У каждого слова есть длина, являющаяся, очевидно, натуральным числом. Следует заметить, что слово ${\displaystyle w}$ длины ${\displaystyle n}$ можно рассматривать как функцию из множества ${\displaystyle \{0,1,\dots ,n-1\}}$ в ${\displaystyle \Sigma }$ . Аналогично, бесконечные слова, или ω-слова, могут рассматриваться как функции из ${\displaystyle \mathbb {N} }$ в ${\displaystyle \Sigma }$ , у которых значением в ${\displaystyle i}$ является ${\displaystyle i}$ -й символ слова. Множество всех бесконечных слов над ${\displaystyle \Sigma }$ обозначается ${\displaystyle \Sigma ^{\omega }}$ . Множество всех конечных и бесконечных слов над ${\displaystyle \Sigma }$ иногда записывается ${\displaystyle \Sigma ^{\infty }}$ .

Таким образом, ω-язык ${\displaystyle L}$ над ${\displaystyle \Sigma }$ — это подмножество ${\displaystyle \Sigma ^{\omega }}$ .

Операции

Некоторыми общими операциями над ω-языками являются:

• Пересечение и объединение . Если ${\displaystyle L}$ и ${\displaystyle M}$ это ω-языки, то ${\displaystyle L\cup M}$ и ${\displaystyle L\cap M}$ тоже являются ω-языками.
• Левая конкатенация . Пусть ${\displaystyle L}$ ω-язык, а ${\displaystyle K}$ язык из конечных слов. Тогда ${\displaystyle K}$ можно конкатенировать с ${\displaystyle L}$ и получить новый ω-язык ${\displaystyle KL}$ .
• Омега (бесконечная итерация) . Как подсказывает запись, операция ${\displaystyle (\cdot )^{\omega }}$ является бесконечным вариантом оператора звезда Клини над языками конечной длины. Если ${\displaystyle L}$ это формальный язык, то ${\displaystyle L^{\omega }}$ есть ω-язык всех бесконечных последовательностей слов из ${\displaystyle L}$ , или, в функциональном представлении, всех функций ${\displaystyle \mathbb {N} \to L}$ .
• Префиксы . Пусть ${\displaystyle w}$ — ω-слово. Тогда формальный язык ${\displaystyle \operatorname {Pref} (w)}$ содержит все конечные префиксы ${\displaystyle w}$ .
• Предел . Пусть дан язык конечных слов ${\displaystyle L}$ . Тогда ω-слово ${\displaystyle w}$ является пределом ${\displaystyle L}$ тогда и только тогда, когда ${\displaystyle \operatorname {Pref} (w)\cap L}$ является бесконечным множеством. Иначе говоря, для сколь угодно большого натурального числа ${\displaystyle n}$ можно всегда найти слово из ${\displaystyle L}$ длиной больше ${\displaystyle n}$ , которое является префиксом ${\displaystyle w}$ . Предел ${\displaystyle L}$ записывается как ${\displaystyle L^{\delta }}$ или ${\displaystyle {\vec {L}}}$ .

Расстояние между ω-словами

На множестве ${\displaystyle \Sigma ^{\omega }}$ можно ввести метрику ${\displaystyle d:\Sigma ^{\omega }\times \Sigma ^{\omega }\to \mathbb {R} }$ следующим образом:

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

где ${\displaystyle |x|}$ обозначает длину ${\displaystyle x}$ (число символов в ${\displaystyle x}$ ), а ${\displaystyle \inf }$ — точную нижнюю грань вещественного множества.

Так, если ${\displaystyle w}$ и ${\displaystyle v}$ совпадают, то ${\displaystyle d(w,v)=0}$ ; если ${\displaystyle w}$ и ${\displaystyle v}$ имеют общий конечный префикс, то ${\displaystyle d(w,v)=2^{-|x|}}$ , где ${\displaystyle x}$ — длиннейший общий префикс ${\displaystyle w}$ и ${\displaystyle v}$ ; а иначе ( ${\displaystyle w}$ и ${\displaystyle v}$ различаются уже в первом символе, то есть длина общего префикса 0) ${\displaystyle d(w,v)=1}$ .

Можно показать, что ${\displaystyle d}$ удовлетворяет всем свойствам метрики.

Важные подклассы

Наиболее широко используемым подклассом ω-языков являются ω-регулярные языки, которые могут быть распознаны (англ.) ( , например автоматами Бюхи ; таким образом, вопрос распознаваемости ω-регулярного языка разрешим и несложно алгоритмизуем. Эти языки находят применение в проверке моделей программных систем.

Библиография

• Staiger, L. «ω-Languages». In G. Rozenberg and A. Salomaa , editors, Handbook of Formal Languages , Volume 3, pages 339—387. Springer-Verlag, Berlin, 1997.
• Thomas, W. «Automata on Infinite Objects». In J. van Leeuwen, editor, Handbook of Theoretical Computer Science , Volume B: Formal Models and Semantics, pages 133—192. Elsevier Science Publishers, Amsterdam, 1990.