Омега язык

В формальной теории языка в рамках теоретической информатики бесконечное слово — это последовательность символов бесконечной длины (в частности, последовательность ω-длины) , а ω-язык — это множество бесконечных слов. Здесь ω относится к первому бесконечному порядковому числу , моделирующему множество натуральных чисел .

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

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

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

Операции

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

Пересечение и объединение: Для данных ω-языков L и M оба языка $L \cup M$ и $L \cap M$ являются ω-языками.
Левая конкатенация: Пусть L — ω-язык, а K — язык, состоящий только из конечных слов. Тогда K можно объединить слева и только слева с L , чтобы получить новый ω-язык KL .
Омега (бесконечная итерация): Как намекает обозначение, операция является бесконечной версией оператора звезды Клини на языках конечной длины. Для заданного формального языка L , L ^ω является ω-языком всех бесконечных последовательностей слов из L ; в функциональном представлении, всех функций . $(\cdot)^{\omega}$ $\mathbb {N} \to L$
Префиксы: Пусть w — ω-слово. Тогда формальный язык Pref( w ) содержит каждый конечный префикс w .
Предел: Для языка L конечной длины ω-слово w находится в пределе L тогда и только тогда, когда $Pref($ $w$ $) \cap$ $L$ — бесконечное множество. Другими словами, для произвольно большого натурального числа n всегда можно выбрать некоторое слово в L , длина которого больше n , и которое является префиксом w . Операция предела на L может быть записана как L ^δ или . ${\vec {L}}$

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

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

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

где | x | интерпретируется как «длина x » (количество символов в x ), а inf — это инфимум по множествам действительных чисел . Если то не существует самого длинного префикса x и поэтому . Симметрия очевидна. Транзитивность следует из того факта, что если w и v имеют максимальный общий префикс длины m и v и u имеют максимальный общий префикс длины n , то первые символы w и u должны быть одинаковыми, поэтому . Следовательно, d — метрика. $w=v$ $d(w,v)=0$ $\min\{м,н\}$ $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.
Thomas, W. "Automata on Infinite Objects". В книге Яна ван Леувена , редактора Handbook of Theoretical Computer Science , Volume B: Formal Models and Semantics, страницы 133-192. Elsevier Science Publishers, Амстердам, 1990.