Омега-язык

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

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

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

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

ОперацииПравить

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

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

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

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

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

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

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

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