Омега-язык (Kbyig-x[dt)
Омега-язык (ω-язык) — это множество бесконечно длинных последовательностей символов.
Формальное определение
[править | править код]Пусть — множество символов (необязательно конечное), называемое алфавитом. По стандартной теории формальных языков, — это множество всех конечных слов над . У каждого слова есть длина, являющаяся, очевидно, натуральным числом. Следует заметить, что слово длины можно рассматривать как функцию из множества в . Аналогично, бесконечные слова, или ω-слова, могут рассматриваться как функции из в , у которых значением в является -й символ слова. Множество всех бесконечных слов над обозначается . Множество всех конечных и бесконечных слов над иногда записывается .
Таким образом, ω-язык над — это подмножество .
Операции
[править | править код]Некоторыми общими операциями над ω-языками являются:
- Пересечение и объединение. Если и это ω-языки, то и тоже являются ω-языками.
- Левая конкатенация. Пусть ω-язык, а язык из конечных слов. Тогда можно конкатенировать с и получить новый ω-язык .
- Омега (бесконечная итерация). Как подсказывает запись, операция является бесконечным вариантом оператора звезда Клини над языками конечной длины. Если это формальный язык, то есть ω-язык всех бесконечных последовательностей слов из , или, в функциональном представлении, всех функций .
- Префиксы. Пусть — ω-слово. Тогда формальный язык содержит все конечные префиксы .
- Предел. Пусть дан язык конечных слов . Тогда ω-слово является пределом тогда и только тогда, когда является бесконечным множеством. Иначе говоря, для сколь угодно большого натурального числа можно всегда найти слово из длиной больше , которое является префиксом . Предел записывается как или .
Расстояние между ω-словами
[править | править код]На множестве можно ввести метрику следующим образом:
где обозначает длину (число символов в ), а — точную нижнюю грань вещественного множества.
Так, если и совпадают, то ; если и имеют общий конечный префикс, то , где — длиннейший общий префикс и ; а иначе ( и различаются уже в первом символе, то есть длина общего префикса 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.
На эту статью не ссылаются другие статьи Википедии. |