WikiSort.ru - Не сортированное

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

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

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

Таким образом, ω-язык L над Σ — это подмножество Σ^ω.

Операции

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

• Пересечение и объединение. Для данных ω-языков L и M, L ∪ M и L ∩ M являются ω-языками.
• Левая конкатенация. Пусть L ω-язык, а K язык из конечных слов. Тогда K можно конкатенировать с L и получить новый ω-язык KL.
• Омега (бесконечная итерация). Как подсказывает запись, операция (${\displaystyle \cdot }$ )^ω является бесконечным вариантом оператора звезда Клини над языками конечной длины. Для данного формального языка L, L^ω есть ω-language всех бесконечных последовательностей слов из L; или в функциональном представлении, всех функций ${\displaystyle \mathbb {N} }$ →L.
• Префиксы. Пусть w — ω-слово. Тогда формальный язык Pref(w) содержит все конечные префиксы w.
• Предел. Пусть дан язык конечной длиныe L. Тогда ω-слово w является пределом L тогда и только тогда, когда Pref(w) ∩ L является бесконечным множеством. Иначе говоря, для произвольно большого натурального числа n, можно всегда найти слово из L, чья длина больше чем n, and являющееся префиксом w. Операция предела L может быть записана как L^δ или ${\displaystyle {\vec {L}}}$ .

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

На множество Σ^ω можно ввести метрику d:Σ^ω × Σ^ω → R следующим образом:

если w и v имеют общий конечный префикс, то d(w,v)= inf {2^-|x| : x из Σ^*, и x принадлежит и Pref(w) и Pref(v) }.

иначе d(w, v)=1

где |x| интерпретируется как «длина x» (число символов x), а inf — точная нижняя грань вещественного множества. Если w=v, у них нет самого длинного общего префикса, и d(w,v)=0; можно также показать, что 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.