Омега-язык

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

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

Пусть $\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.