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