オメガ言語

理論計算機科学における形式言語理論において、無限語とは記号の無限長列（具体的にはω長列）であり、ω言語とは無限語の集合である。ここで、ωは自然数の集合をモデル化する最初の無限順序数を指す。

正式な定義

Σ を記号の集合（必ずしも有限である必要はない）とする。形式言語理論の標準的な定義に従うと、 Σ ^{*は Σ 上のすべての}有限語の集合である。すべての有限語には長さがあり、これは自然数である。長さnの単語wが与えられたとき、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\{m,n\}$ $d(w,u)\leq 2^{-\min\{m,n\}}\leq 2^{-m}+2^{-n}=d(w,v)+d(v,u)$

重要なサブクラス

ω-言語の最も広く用いられているサブクラスは、 ω-正規言語の集合であり、これはビュッヒ・オートマトンによって認識可能という有用な性質を持つ。したがって、 ω-正規言語の帰属判定問題はビュッヒ・オートマトンを用いて決定可能であり、計算も比較的容易である。

言語 Σ が集合のべき集合（「原子命題」と呼ばれる）である場合、ω 言語は線形時間特性を持ち、モデル検査で研究されます。

参考文献

Perrin, D.とPin, J.-E.「無限語：オートマトン、半群、論理、ゲーム」。純粋数学と応用数学第141巻、エルゼビア、2004年。
Staiger, L.「ω-言語」. G. RozenbergとA. Salomaa編『形式言語ハンドブック』第3巻、339-387ページ。Springer-Verlag、ベルリン、1997年。
Thomas, W.「無限オブジェクト上のオートマトン」Jan van Leeuwen編『理論計算機科学ハンドブック』第B巻：形式モデルと意味論、133-192ページ。Elsevier Science Publishers、アムステルダム、1990年。