Омега язык

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

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

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

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

Операции

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

Пересечение и объединение

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

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

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

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

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

Префиксы

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

Лимит

конечной длины Для языка L ω-слово w находится в пределе языка L тогда и только тогда, когда Pref( w ) ∩ 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 ), а inf — это нижняя грань наборов действительных чисел . Если $w=v$ тогда нет самого длинного префикса x и так $d(w,v)=0$. Симметрия очевидна. Транзитивность следует из того факта, что если w и v имеют максимальный общий префикс длины m , а v и u имеют максимальный общий префикс длины n , то первый $\min\{m,n\}$ символы w и u должны быть одинаковыми, поэтому $d(w,u)\leq 2^{-\min\{m,n\}}\leq 2^{-m}+2^{-n}=d(w,v)+d(v,u)$. Следовательно, d является метрикой.

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

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

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

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

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