Омега язык

Эта статья включает список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Октябрь 2015 ) ( Узнайте, как и когда удалять это сообщение )

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

Пусть Σ — множество символов (не обязательно конечное). Следуя стандартному определению из формальной теории языков , Σ ^* — множество всех конечных слов над Σ. Каждое конечное слово имеет длину, которая является натуральным числом. Для данного слова 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( w ) содержит каждый конечный префикс w .

Предел

Для языка L конечной длины ω-слово w находится в пределе L тогда и только тогда, когда Pref( w ) ∩ L — бесконечное множество. Другими словами, для произвольно большого натурального числа n всегда можно выбрать некоторое слово в L , длина которого больше n , и которое является префиксом w . Операция предела на L может быть записана как L ^δ или .${\displaystyle {\vec {L}}}$

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

${\displaystyle 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 — метрика.${\displaystyle w=v}$${\displaystyle d(w,v)=0}$${\displaystyle \min\{м,н\}}$${\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.
• Thomas, W. "Automata on Infinite Objects". В книге Яна ван Леувена , редактора Handbook of Theoretical Computer Science , Volume B: Formal Models and Semantics, страницы 133-192. Elsevier Science Publishers, Амстердам, 1990.