Омега-язык

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

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

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

[править | править код]

Пусть  — множество символов (необязательно конечное), называемое алфавитом. По стандартной теории формальных языков,  — это множество всех конечных слов над . У каждого слова есть длина, являющаяся, очевидно, натуральным числом. Следует заметить, что слово длины можно рассматривать как функцию из множества в . Аналогично, бесконечные слова, или ω-слова, могут рассматриваться как функции из в , у которых значением в является -й символ слова. Множество всех бесконечных слов над обозначается . Множество всех конечных и бесконечных слов над иногда записывается .

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

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

  • Пересечение и объединение. Если и это ω-языки, то и тоже являются ω-языками.
  • Левая конкатенация. Пусть ω-язык, а язык из конечных слов. Тогда можно конкатенировать с и получить новый ω-язык .
  • Омега (бесконечная итерация). Как подсказывает запись, операция является бесконечным вариантом оператора звезда Клини над языками конечной длины. Если это формальный язык, то есть ω-язык всех бесконечных последовательностей слов из , или, в функциональном представлении, всех функций .
  • Префиксы. Пусть  — ω-слово. Тогда формальный язык содержит все конечные префиксы .
  • Предел. Пусть дан язык конечных слов . Тогда ω-слово является пределом тогда и только тогда, когда является бесконечным множеством. Иначе говоря, для сколь угодно большого натурального числа можно всегда найти слово из длиной больше , которое является префиксом . Предел записывается как или .

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

[править | править код]

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

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

Так, если и совпадают, то ; если и имеют общий конечный префикс, то , где — длиннейший общий префикс и ; а иначе ( и различаются уже в первом символе, то есть длина общего префикса 0) .

Можно показать, что удовлетворяет всем свойствам метрики.

Важные подклассы

[править | править код]

Наиболее широко используемым подклассом ω-языков являются ω-регулярные языки, которые могут быть распознаны ω-автоматами[англ.], например автоматами Бюхи; таким образом, вопрос распознаваемости ω-регулярного языка разрешим и несложно алгоритмизуем. Эти языки находят применение в проверке моделей программных систем.

Библиография

[править | править код]
  • 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.