オメガ言語

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

Σ を記号の集合 (必ずしも有限ではない) とする。形式言語理論の標準的な定義に従って、Σ ^{*は Σ 上のすべての}有限語の集合である。すべての有限語は長さを持ち、それは自然数である。長さnの語wが与えられた場合、w は集合 {0,1,..., n − 1} → Σ からの関数と見なすことができ、 iにおける値は位置iの記号を与える。無限語、または ω 語も同様に関数と見なすことができ、${\displaystyle \mathbb {N} }$Σ について。Σ 上のすべての無限語の集合は Σ ^{ωと表記される。Σ 上のすべての有限語}と無限語の集合は、Σ ^∞または Σ ^≤ωと表記されることもある。

したがって、 Σ 上のω 言語Lは Σ ^ωの部分集合です。

ω言語で定義されている一般的な操作には、以下のようなものがあります。

交差と結合

ω言語LとMが与えられたとき、L ∪ MとL ∩ Mはどちらもω言語である。

左連結

L をω 言語とし、Kを有限語のみからなる言語とする。このとき、 K はLに左側のみ連結され、新しい ω 言語KLが得られる。

オメガ（無限反復）

表記が示唆するように、この操作は$\displaystyle (\cdot )^{\omega }}$は、有限長言語におけるクリーネスター演算子の無限バージョンです。形式言語Lが与えられたとき、L ^ωはLからのすべての無限語列の ω 言語です。関数的な観点からは、すべての関数のω 言語です。${\displaystyle \mathbb {N} \to L}$。

接頭辞

w をω 語とする。このとき、形式言語 Pref( w )はwのすべての有限接頭辞を含む。

制限

有限長の言語Lが与えられたとき、ω 語wがLの極限に含まれるのは、 Pref( w ) ∩ Lが無限集合である場合に限る。言い換えれば、任意の大きな自然数nに対して、長さがnより大きく、かつwの接頭辞となるL内の語を常に選択できる。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 は実数の集合の下限です。${\displaystyle w=v}$すると最長の接頭辞xが存在しない。${\displaystyle d(w,v)=0}$対称性は明らかです。推移性は、wとvが長さmの最大共通接頭辞を持ち、vとu が長さnの最大共通接頭辞を持つ場合、最初の${\displaystyle \min\{m,n\}}$wとuの文字は同じでなければならないので$\displaystyle d(w,u)\leq 2^{-\min\{m,n\}}\leq 2^{-m}+2^{-n}=d(w,v)+d(v,u)}$したがって、dは距離関数である。

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

言語Σが集合の冪集合（「原子命題」と呼ばれる）である場合、ω言語は線形時間特性であり、これはモデル検査で研究されている。

• Perrin, D.およびPin, J.-E.「無限の言葉：オートマタ、半群、論理、ゲーム」純粋応用数学第 141 巻、Elsevier、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 年。