- Омега-язык
-
Омега-язык (ω-язык) — это множество бесконечно длинных последовательностей символов.
Содержание
Формальное определение
Пусть Σ — множество символов (необязательно конечное). По стандартной теории формальных языков, Σ* — это множество всех конечных слов над Σ. У каждого слова есть длина, являющаяся, очевидно, натуральным числом. Следует заметить, что если дано слово w длины n, то w можно рассматривать как функцию из множества {0,1,…,n-1} → Σ. Бесконечные слова, или ω-слова, могут также быть рассмотрены как функции из в Σ, у которых значением в i является i-й символ слова. Множество всех бесконечных слов над Σ обозначается Σω. Множество всех конечных and бесконечных слов над Σ иногда записывается Σ∞.
Таким образом, ω-язык L над Σ — это подмножество Σω.
Операции
Некоторыми общими операциями над ω-языками являются:
- Пересечение и объединение. Для данных ω-языков L и M, L ∪ M и L ∩ M являются ω-языками.
- Левая конкатенация. Пусть L ω-язык, а K язык из конечных слов. Тогда K можно конкатенировать с L и получить новый ω-язык KL.
- Омега (бесконечная итерация). Как подсказывает запись, операция ()ω является бесконечным вариантом оператора звезда Клини над языками конечной длины. Для данного формального языка L, Lω есть ω-language всех бесконечных последовательностей слов из L; или в функциональном представлении, всех функций →L.
- Префиксы. Пусть w — ω-слово. Тогда формальный язык Pref(w) содержит все конечные префиксы w.
- Предел. Пусть дан язык конечной длиныe L. Тогда ω-слово w является пределом L если и только если Pref(w) ∩ L является бесконечным множеством. Иначе говоря, для произвольно большого натурального числа n, можно всегда найти слово из L, чья длина больше чем n, and являющееся префиксом w. Операция предела L может быть записана как 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.
На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.Категория:- Формальные языки
Wikimedia Foundation. 2010.