Оглавление
Омега-язык
-
Определение ω-языка
- ω-язык – это множество бесконечных слов над заданным набором символов Σ.
- ω-слово – это функция от множества натуральных чисел к Σ.
-
Операции в ω-языках
- Расстояние между ω-словами определяется как метрика в метрическом пространстве Σω × Σω.
- Транзитивность метрики следует из свойства максимальных общих префиксов.
-
Важность ω-регулярных языков
- ω-регулярные языки распознаваемы автоматами Бюхи и имеют важное значение в теории формальных языков.
-
Примеры и литература
- ω-языки могут быть связаны с линейным временем проверки моделей.
- В статье Перрина и Пина “Бесконечные слова” рассматриваются автоматы, полугруппы, логика и игры.
- Стайгер в “ω-языках” обсуждает их свойства и место в справочнике по официальным языкам.
- Томас в “Автоматах на бесконечных объектах” описывает применение автоматов к бесконечным объектам.