Язык Омега - Omega language

An ω -язык это набор бесконечной длины последовательностей символы.

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

Пусть Σ - набор символов (не обязательно конечный). Следуя стандартному определению из формальный язык теория, Σ^* это набор всех конечный слова над Σ. Каждое конечное слово имеет длину, которая является натуральным числом. Учитывая слово ш длины п, ш можно рассматривать как функцию из множества {0,1, ...,п-1} → Σ, со значением при я предоставление символа в позиции я. Бесконечные слова, или ω-слова, можно также рассматривать как функции от ${ Displaystyle mathbb {N}}$ в Σ. Множество всех бесконечных слов над Σ обозначается Σ^ω. Множество всех конечных и бесконечные слова над Σ иногда пишут Σ^∞.

Таким образом, ω-язык L над Σ является подмножество из Σ^ω.

Операции

Некоторые общие операции, определенные на ω-языках:

Пересечение и союз. Учитывая ω-языки L и M, обе L ∪ M и L ∩ M являются ω-языками.
Левая конкатенация. Позволять L быть ω-языком, и K быть языком только конечных слов. потом K можно объединить слева Только к L чтобы получить новый ω-язык KL.
Омега (бесконечная итерация). Как следует из обозначений, операция ( ${ displaystyle cdot}$ )^ω это бесконечная версия Клини звезда оператор на языках конечной длины. Учитывая формальный язык L, L^ω является ω-языком всех бесконечных последовательностей слов из L; с функциональной точки зрения, всех функций ${ Displaystyle mathbb {N}}$ →L.
Префиксы. Позволять ш быть ω-словом. Тогда формальный язык Pref (ш) содержит все конечный префикс из ш.
Предел. Для языка конечной длины L, ω-слово ш находится в предел из L тогда и только тогда, когда Pref (ш) ∩ L является бесконечный набор. Другими словами, для сколь угодно большого натурального числа п, всегда можно выбрать слово в L, длина которого больше п, и который является префиксом ш. Ограничение операции на L можно написать L^δ или же ${ displaystyle { vec {L}}}$ .

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

Множество Σ^ω можно превратить в метрическое пространство по определению метрика ${ displaystyle d: Sigma ^ { omega} times Sigma ^ { omega} rightarrow mathbb {R}}$ в качестве:

{ displaystyle d (w, v) = inf {2 ^ {- | x |}: x in Sigma ^ {*} { text {and}} x in { text {Pref} } (ш) cap { text {Pref}} (v) }}

где |Икс| интерпретируется как «длина Икс"(количество символов в Икс), и инф это инфимум над наборами действительные числа. Если ${ displaystyle w = v}$ тогда нет самого длинного префикса Икс и так ${ displaystyle d (w, v) = 0}$ . Симметрия ясна. Транзитивность следует из того, что если ш и v иметь максимальный общий префикс длины м и v и ты иметь максимальный общий префикс длины п затем первый ${ Displaystyle мин {м, п }}$ персонажи ш и ты должно быть так же ${ displaystyle d (w, u) leq 2 ^ {- min {m, n }} leq 2 ^ {- m} +2 ^ {- n} = d (w, v) + d ( v, u)}$ . Следовательно d это метрика.

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

Наиболее широко используемый подкласс ω-языков - это набор ω-регулярные языки, которые обладают полезным свойством узнаваемости Büchi автоматы. Таким образом проблема решения принадлежности ω-регулярного языка разрешима с помощью автомата Бюхи и довольно просто вычислить.

Если язык Σ является набор мощности множества (называемого «атомарными предложениями»), то ω-язык является свойство линейного времени, которые изучаются в проверка модели.

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

Перрин Д. и Пин Дж. Э. "Бесконечные слова: автоматы, полугруппы, логика и игры ". Чистая и прикладная математика, том 141, Elsevier, 2004.
Штайгер, Л. "ω-языки ». У Г. Розенберга и А. Саломаа, редакторы, Справочник формальных языков, Том 3, страницы 339-387. Springer-Verlag, Берлин, 1997.
Томас, В. "Автоматы на бесконечных объектах". В Ян ван Леувен, редактор, Справочник по теоретической информатике, Том B: Формальные модели и семантика, страницы 133–192. Издательство Elsevier Science Publishers, Амстердам, 1990 г.