欧米茄语言

假设Σ是一组符号(不一定是有限的)。从形式语言理论上来讲它遵循以下标准定义，Σ^*是在Σ上的所有有限字的集合。每个有限字组都有一个长度（可以用自然数描述的量级）。给定一个长度为n的字组w, w 可以看作集合{0，1，...,n-1 }→ Σ的函数，在值为 i 的位置给出其相应的符号。无限字或ω字同样可以看作是从N 到Σ的函数。Σ上所有无限字的集合被表示为Σ^ω。所有有限字集合和无限字集合有时被写成Σ^∞。

因此，一个在Σ上的ω语言L是 Σ^ω的一个子集。

ω语言中定义的一些常见操作有：

• 交集和并集。给定ω语言 L 和 M，L 和 M 的交集和并集都是ω语言。
• 左拼接。让 L 成为ω语言，并且 K 只是一种有限字语言。然后 K 可以从左边连接L 产生新的ω语言KL。
• ω(无限迭代)。如符号所示，（·）^ω 是克林星号算子（Kleene star operator）在有限长度语言上的无限版本。给定一种正式的语言 L, L^ω 是来自L的所有无限字序列的ω语言；函数表示可以表示为N→L。
• 前缀。让 w 为一个ω字。那么形式语言Pref(w)包含w的每个有限前缀。
• 限制。给定一种有限长的语言 L，当且仅当Pref(w)与L的交集是一个无限序列，则一个ω字w 就是关于语言L的限制 。换句话说，对于任意大的自然数n，总是可以在L中选择一些长度大于n且是w字前缀的字 。在L上的限制算子可以表示为 L^δ或者向量L。

集合Σ^ω可以根据度量标准制成一个度量空间d：σ^ω ×σ^ω → R 如下:

d( w, v)= inf {2 ^−|x| ； x 属于集合Σ ^*， x 也属于Pref( w)和Pref( v)}。

此处|x|被解释为“x的长度 ”(x中的符号数量)，inf是实数集的下确界。如果w=v，它们没有最长的有限前缀，并且d(w,v)=0；则可以证明d满足度量标准的所有其他必要性质。

ω语言最广泛使用的子类是ω-正则语言，它具有可被Büchi automata识别的有用属性；因此判定ω-正则语言成员可以使用Büchi automata来决定，并且计算起来相当简单。

• 佩兰，d .和宾，J-E . "Infinite Words: Automata, Semigroups, Logic and Games“。《纯数学和应用数学》，第141卷，埃尔塞维尔，2004年。
• 史泰格，洛杉矶。”ω-Languages“。在G. Rozenberg和 A.Salomaa，编辑， 正式语言手册，第3卷，第339-387页。斯普林格-弗拉格，柏林，1997年。
• 无限物体上的自动机。在 Jan van Leeuwen，编辑， 理论计算机科学手册，第二卷:形式模型和语义学，第133-192页。埃尔塞维尔科学出版社，阿姆斯特丹，1990年。