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

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

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

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

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

Операции

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

Пересечение и союз

Для ω-языков L и M оба L ∪ M и L ∩ M являются ω-языками.

Левая конкатенация

Пусть L - ω-язык, а K - язык только конечных слов. Тогда K можно объединить слева и только слева с L, чтобы получить новый ω-язык KL .

Омега (бесконечная итерация)

Как следует из обозначений, эта операция представляет собой бесконечную версию звездного оператора Клини на языках конечной длины. Для формального языка L , L ^ω является ω-языком всех бесконечных последовательностей слов из L ; с функциональной точки зрения всех функций .${\ Displaystyle (\ cdot) ^ {\ omega}}$${\ displaystyle \ mathbb {N} \ to L}$

Префиксы

Пусть w - ω-слово. Тогда формальный язык Pref ( ш ) содержит каждый конечный префикс из ш .

Предел

Для языка L конечной длины ω-слово w находится в пределе языка L тогда и только тогда, когда Pref ( w ) ∩ 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) \}}$

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

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

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

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

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

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