Омега-язык

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Формальное определение[править | править исходный текст]

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

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

Операции[править | править исходный текст]

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

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

Расстояние между ω-словами[править | править исходный текст]

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

если w и v имеют общий конечный префикс, то d(w,v)= inf {1-|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.