Русская Википедия:Омега-язык
Омега-язык (ω-язык) — это множество бесконечно длинных последовательностей символов.
Формальное определение
Пусть <math>\Sigma</math> — множество символов (необязательно конечное), называемое алфавитом. По стандартной теории формальных языков, <math>\Sigma^*</math> — это множество всех конечных слов над <math>\Sigma</math>. У каждого слова есть длина, являющаяся, очевидно, натуральным числом. Следует заметить, что слово <math>w</math> длины <math>n</math> можно рассматривать как функцию из множества <math>\{0,1,\dots,n-1\}</math> в <math>\Sigma</math>. Аналогично, бесконечные слова, или ω-слова, могут рассматриваться как функции из <math>\mathbb{N}</math> в <math>\Sigma</math>, у которых значением в <math>i</math> является <math>i</math>-й символ слова. Множество всех бесконечных слов над <math>\Sigma</math> обозначается <math>\Sigma^\omega</math>. Множество всех конечных и бесконечных слов над <math>\Sigma</math> иногда записывается <math>\Sigma^\infty</math>.
Таким образом, ω-язык <math>L</math> над <math>\Sigma</math> — это подмножество <math>\Sigma^\omega</math>.
Операции
Некоторыми общими операциями над ω-языками являются:
- Пересечение и объединение. Если <math>L</math> и <math>M</math> это ω-языки, то <math>L\cup M</math> и <math>L\cap M</math> тоже являются ω-языками.
- Левая конкатенация. Пусть <math>L</math> ω-язык, а <math>K</math> язык из конечных слов. Тогда <math>K</math> можно конкатенировать с <math>L</math> и получить новый ω-язык <math>KL</math>.
- Омега (бесконечная итерация). Как подсказывает запись, операция <math>(\cdot)^\omega</math> является бесконечным вариантом оператора звезда Клини над языками конечной длины. Если <math>L</math> это формальный язык, то <math>L^\omega</math> есть ω-язык всех бесконечных последовательностей слов из <math>L</math>, или, в функциональном представлении, всех функций <math>\mathbb{N}\to L</math>.
- Префиксы. Пусть <math>w</math> — ω-слово. Тогда формальный язык <math>\operatorname{Pref}(w)</math> содержит все конечные префиксы <math>w</math>.
- Предел. Пусть дан язык конечных слов <math>L</math>. Тогда ω-слово <math>w</math> является пределом <math>L</math> тогда и только тогда, когда <math>\operatorname{Pref}(w)\cap L</math> является бесконечным множеством. Иначе говоря, для сколь угодно большого натурального числа <math>n</math> можно всегда найти слово из <math>L</math> длиной больше <math>n</math>, которое является префиксом <math>w</math>. Предел <math>L</math> записывается как <math>L^\delta</math> или <math>\vec{L}</math>.
Расстояние между ω-словами
На множестве <math>\Sigma^\omega</math> можно ввести метрику <math>d:\Sigma^\omega\times\Sigma^\omega\to\R</math> следующим образом:
- <math>d(w,v)= \inf\{ 2^{-|x|} \mid x \in \Sigma^*, x \in \operatorname{Pref}(w)\cap \operatorname{Pref}(v) \},</math>
где <math>|x|</math> обозначает длину <math>x</math> (число символов в <math>x</math>), а <math>\inf</math> — точную нижнюю грань вещественного множества.
Так, если <math>w</math> и <math>v</math> совпадают, то <math>d(w,v)=0</math>; если <math>w</math> и <math>v</math> имеют общий конечный префикс, то <math>d(w,v)=2^{-|x|}</math>, где <math>x</math> — длиннейший общий префикс <math>w</math> и <math>v</math>; а иначе (<math>w</math> и <math>v</math> различаются уже в первом символе, то есть длина общего префикса 0) <math>d(w, v)=1</math>.
Можно показать, что <math>d</math> удовлетворяет всем свойствам метрики.
Важные подклассы
Наиболее широко используемым подклассом ω-языков являются ω-регулярные языки, которые могут быть распознаны Шаблон:Не переведено 3, например Шаблон:Не переведено 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.
