Омега-язык

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

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

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

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

Операции

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

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

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

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

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

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

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

Можно показать, что $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.