Омега-язык

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

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

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, установите ссылки в соответствии с принятыми рекомендациями. (14 июня 2009)