Омега-язык

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

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

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

Таким образом, ω-язык $L$ над $\mathrm{\Sigma }$ — это подмножество ${\mathrm{\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$ — ω-слово. Тогда формальный язык $\mathrm{Pref}(w)$ содержит все конечные префиксы $w$.
• Предел. Пусть дан язык конечных слов $L$. Тогда ω-слово $w$ является пределом $L$ тогда и только тогда, когда $\mathrm{Pref}(w)\cap L$ является бесконечным множеством. Иначе говоря, для сколь угодно большого натурального числа $n$ можно всегда найти слово из $L$ длиной больше $n$, которое является префиксом $w$. Предел $L$ записывается как $L^{\delta }$ или $\overrightarrow{L}$.

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

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

$d(w,v)=\inf \{2^{-|x|}\mid x\in {\mathrm{\Sigma }}^{*},x\in \mathrm{Pref}(w)\cap \mathrm{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$ удовлетворяет всем свойствам метрики.

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

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

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

• 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.