限定語

数学、より正確には形式言語理論 において、前有限語は有限語の概念を完全な位相空間に一般化したものである。この概念により、位相を使って言語や有限半群を研究することができる。例えば、前有限語は、さまざまな有限半群の代数的概念の別の特徴づけを与えるために使用される。

A をアルファベットとします。A 上の profinite 単語の集合は、A上の単語の集合を定義域とする距離空間の完備化で構成されます。距離を定義するために使用される距離は、単語の分離の概念を使用して与えられます。これらの概念が定義されました。 ${\displaystyle A^{*}}$

MとN をモノイドとし、pとq をモノイドMの要素とします。φ をMからNへのモノイドの射とします。 φの射がpとq を分離するとは、次の場合をいいます。 たとえば、単語をその長さの偶奇に送る射は、単語ababaとabaa を分離します。 確かにそうです。 ${\displaystyle \phi (p)\neq \phi (q)}$${\displaystyle \phi :A^{*}\to \mathbb {Z} /2\mathbb {Z} ,w\mapsto |w|(\operatorname {mod} 2)}$${\displaystyle \phi (ababa)=1\neq 0=\phi (abaa)}$

N がpとq を分離するとは、 MからNへのモノイドφの射が存在し、それがpとq を分離する場合を言います。前の例を使用すると、 はababaとabaa を分離します。より一般的には、はサイズがnを法として一致しない単語を分離します。一般に、 pの因数と新しい要素 0 を要素とするモノイドを使用して、任意の 2 つの異なる単語を分離できます。射は、 pのプレフィックスをそれ自身に送り、その他すべてを 0 に送ります。 ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

2 つの異なる単語pとq の間の距離は、 pとq を分ける最小のモノイドNのサイズの逆数として定義されます。したがって、ababaとabaaの距離は です。 p自体からの距離は0 と定義されます。 ${\displaystyle {\frac {1}{2}}}$

この距離dは超距離、つまり です。さらに、および を満たします。任意の単語pは、|p|+1個の要素を持つモノイドを使用して他の任意の単語から分離できるため ( |p|はpの長さ)、 pと他の任意の単語間の距離は少なくとも になります。したがって、この距離によって定義されるトポロジーは離散的です。 ${\displaystyle d(x,z)\leq \max \left\{d(x,y),d(y,z)\right\}}$${\displaystyle d(uw,vw)\leq d(u,v)}$${\displaystyle d(wu,wv)\leq d(u,v)}$${\displaystyle {\frac {1}{|p|}}}$

の profinite 完備化( と表記)は、上で定義された距離の下での有限語の集合の 完備化です。この完備化はモノイド構造を保存します。${\displaystyle A^{*}}$${\displaystyle {\ワイドハット {A^{*}}}}$

上のトポロジーはコンパクトです。 ${\displaystyle {\ワイドハット {A^{*}}}}$

Mが有限である任意のモノイド射 は、モノイド射 に一意に拡張でき、この射は一様連続です( 上の任意の距離を使用して、離散位相と互換性があります)。さらに、はこの性質を持つ最小の位相空間です。 ${\displaystyle \phi :A^{*}\to M}$${\displaystyle {\widehat {\phi }}:{\widehat {A^{*}}}\to M}$${\displaystyle M}$${\displaystyle {\ワイドハット {A^{*}}}}$

未有限語は の要素です。そして未有限言語は未有限語の集合です。すべての有限語は未有限語です。ここでは、有限ではない未有限語の例をいくつか示します。 ${\displaystyle {\ワイドハット {A^{*}}}}$

m が任意の単語である場合、がコーシー列であるために存在する を表します。直感的に、と を分離するには、モノイドは少なくとも まで数えられる必要があり、したがって少なくとも個の要素が必要です。はコーシー列であるため、は確かに前限定単語です。 ${\displaystyle m^{\omega}}$${\displaystyle \lim _{i\to \infty }m^{i!}}$${\displaystyle m^{i!}}$${\displaystyle m^{i!}}$${\displaystyle m^{i'!}}$${\displaystyle \min(i,i')}$${\displaystyle \min(i,i')}$${\displaystyle m^{i!}}$${\displaystyle m^{\omega}}$

さらに、この語はべき等です。これは、 Nが有限である任意の射に対して、 という事実によるものです。N は有限なので、 i が十分に大きい場合、はべき等であり、シーケンスは定数です。 ${\displaystyle m^{\omega}}$${\displaystyle \phi :A^{*}\to N}$${\displaystyle \phi (m^{i!})=\phi (m)^{i!}}$${\displaystyle \phi (m)^{i!}}$

同様に、およびはそれぞれおよびとして定義されます。 ${\displaystyle m^{\omega +1}}$${\displaystyle m^{\omega -1}}$${\displaystyle \lim _{n\to \infty }m^{n!+1}}$${\displaystyle \lim _{n\to \infty }m^{n!-1}}$

部分有限言語の概念により、半群論の概念を位相の概念に関連付けることができます。より正確には、 部分有限言語Pが与えられた場合、次のステートメントは同等です。

• P は閉じています。
• Pは認識可能であり、
• Pの統語的合同はのサブセットとして clopen です。${\displaystyle {\widehat {A^{*}}}\times {\widehat {A^{*}}}}$

同様の記述は有限語の言語Pにも当てはまります。以下の条件は同等です。

• ${\displaystyle P}$は認識可能である（のサブセットとして）、${\displaystyle A^{*}}$
• Pの閉包、は（のサブセットとして）認識可能である。${\displaystyle {\overline {P}}}$${\displaystyle {\widehat {A^{*}}}}$
• ${\displaystyle P=K\cap A^{*}}$、ある閉じたKに対して、
• ${\displaystyle {\overline {P}}}$クローズです。

これらの特徴付けは、有限語の言語の閉包を取ることと、前有限語の言語を有限語に制限することは、認識可能な言語に適用された場合、逆の操作であるという、より一般的な事実によるものです。

Pin, Jean-Éric (2016-11-30). オートマトン理論の数学的基礎(PDF) . pp. 130–139.

アルメイダ、ホルヘ (1994)。有限半群と普遍代数。リバーエッジ、ニュージャージー州: World Scientific Publishing Co. Inc. ISBN 981-02-1895-8。